"環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてN組のメッセージを生成するメッセージ生成部と、1組の入力情報に対してk通りk≧3の第1情報の中から1個の第1情報を選択する一方向性関数に対し、文書MとN組の前記メッセージとを入力して、N個の第1情報を選択する第1情報選択部と、N個の前記第1情報にそれぞれ対応するN個の第2情報を生成する第2情報生成部と、N個の前記第1情報及びN個の前記第2情報を電子署名として、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に提供する署名提供部と、を備え、前記ベクトルsは署名鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記第2情報を利用して、当該第2情報に対応する第1情報の種類に応じて選択される所定の演算を実行することで得られる情報である、情報処理装置。前記多次多変数多項式の組Fは、Fbx,y=Fxy-Fx-Fyで定義されるFbx,yがx及びyに関して双線形となるように設定される、請求項1に記載の情報処理装置。前記多次多変数多項式の組Fは、前記公開鍵を生成するユーザ毎に異なる情報を用いて生成される、請求項1に記載の情報処理装置。前記多次多変数多項式の組Fは、Fbx,y=FAxy-FAx-FAyで定義されるFbx,yがx及びyに関して双線形となる2次多項式FAと、3次以上の次数を有する項との和で表現される、請求項1に記載の情報処理装置。環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報保持部と、前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたN組のメッセージを取得するメッセージ取得部と、1組の入力情報に対してk通りk≧3の第1情報の中から1個の第1情報を選択する一方向性関数に対し、文書MとN組の前記メッセージとを入力することで選択されたN個の第1情報と、N個の前記第1情報にそれぞれ対応するN個の第2情報とで構成される電子署名を取得する署名取得部と、前記メッセージ、前記多次多変数多項式の組F、前記ベクトルy、及び前記電子署名に基づいて前記文書Mの正当性を検証する署名検証部と、を備え、前記ベクトルsは署名鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記第2情報を利用して、当該第2情報に対応する第1情報の種類に応じて選択される所定の演算を実行することで得られる情報である、情報処理装置。前記多次多変数多項式の組Fは、Fbx,y=Fxy-Fx-Fyで定義されるFbx,yがx及びyに関して双線形となるように設定される、請求項5に記載の情報処理装置。前記多次多変数多項式の組Fは、前記公開鍵を生成するユーザ毎に異なる情報を用いて生成される、請求項5に記載の情報処理装置。前記多次多変数多項式の組Fは、Fbx,y=FAxy-FAx-FAyで定義されるFbx,yがx及びyに関して双線形となる2次多項式FAと、3次以上の次数を有する項との和で表現される、請求項5に記載の情報処理装置。環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてN組のメッセージを生成するステップと、1組の入力情報に対してk通りk≧3の第1情報の中から1個の第1情報を選択する一方向性関数に対し、文書MとN組の前記メッセージとを入力して、N個の第1情報を選択するステップと、N個の前記第1情報にそれぞれ対応するN個の第2情報を生成するステップと、N個の前記第1情報及びN個の前記第2情報を電子署名として、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に提供するステップと、を含み、前記ベクトルsは署名鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記第2情報を利用して、当該第2情報に対応する第1情報の種類に応じて選択される所定の演算を実行することで得られる情報である、署名提供方法。環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持するステップと、前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたN組のメッセージを取得するステップと、1組の入力情報に対してk通りk≧3の第1情報の中から1個の第1情報を選択する一方向性関数に対し、文書MとN組の前記メッセージとを入力することで選択されたN個の第1情報と、N個の前記第1情報にそれぞれ対応するN個の第2情報とで構成される電子署名を取得するステップと、前記メッセージ、前記多次多変数多項式の組F、前記ベクトルy、及び前記電子署名に基づいて前記文書Mの正当性を検証するステップと、を含み、前記ベクトルsは署名鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記第2情報を利用して、当該第2情報に対応する第1情報の種類に応じて選択される所定の演算を実行することで得られる情報である、署名検証方法。環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてN組のメッセージを生成するメッセージ生成機能と、1組の入力情報に対してk通りk≧3の第1情報の中から1個の第1情報を選択する一方向性関数に対し、文書MとN組の前記メッセージとを入力して、N個の第1情報を選択する第1情報選択機能と、N個の前記第1情報にそれぞれ対応するN個の第2情報を生成する第2情報生成機能と、N個の前記第1情報及びN個の前記第2情報を電子署名として、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に提供する署名提供機能と、をコンピュータに実現させるためのプログラムであり、前記ベクトルsは署名鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記第2情報を利用して、当該第2情報に対応する第1情報の種類に応じて選択される所定の演算を実行することで得られる情報である、プログラム。環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報保持機能と、前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたN組のメッセージを取得するメッセージ取得機能と、1組の入力情報に対してk通りk≧3の第1情報の中から1個の第1情報を選択する一方向性関数に対し、文書MとN組の前記メッセージとを入力することで選択されたN個の第1情報と、N個の前記第1情報にそれぞれ対応するN個の第2情報とで構成される電子署名を取得する署名取得機能と、前記メッセージ、前記多次多変数多項式の組F、前記ベクトルy、及び前記電子署名に基づいて前記文書Mの正当性を検証する署名検証機能と、をコンピュータに実現させるためのプログラムであり、前記ベクトルsは署名鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記第2情報を利用して、当該第2情報に対応する第1情報の種類に応じて選択される所定の演算を実行することで得られる情報である、プログラム。環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてN組のメッセージを生成するメッセージ生成機能と、1組の入力情報に対してk通りk≧3の第1情報の中から1個の第1情報を選択する一方向性関数に対し、文書MとN組の前記メッセージとを入力して、N個の第1情報を選択する第1情報選択機能と、N個の前記第1情報にそれぞれ対応するN個の第2情報を生成する第2情報生成機能と、N個の前記第1情報及びN個の前記第2情報を電子署名として、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に提供する署名提供機能と、をコンピュータに実現させるためのプログラムが記録された、コンピュータにより読み取り可能な記録媒体であり、前記ベクトルsは署名鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記第2情報を利用して、当該第2情報に対応する第1情報の種類に応じて選択される所定の演算を実行することで得られる情報である、記録媒体。環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報保持機能と、前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたN組のメッセージを取得するメッセージ取得機能と、1組の入力情報に対してk通りk≧3の第1情報の中から1個の第1情報を選択する一方向性関数に対し、文書MとN組の前記メッセージとを入力することで選択されたN個の第1情報と、N個の前記第1情報にそれぞれ対応するN個の第2情報とで構成される電子署名を取得する署名取得機能と、前記メッセージ、前記多次多変数多項式の組F、前記ベクトルy、及び前記電子署名に基づいて前記文書Mの正当性を検証する署名検証機能と、をコンピュータに実現させるためのプログラムが記録された、コンピュータにより読み取り可能な記録媒体であり、前記ベクトルsは署名鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記第2情報を利用して、当該第2情報に対応する第1情報の種類に応じて選択される所定の演算を実行することで得られる情報である、記録媒体。上記の通り、多変数多項式問題は、量子コンピュータを用いても解くことが困難な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に基づいてN組のメッセージを生成するメッセージ生成部と、1組の入力情報に対してk通りk≧3の第1情報の中から1個の第1情報を選択する一方向性関数に対し、文書MとN組の前記メッセージとを入力して、N個の第1情報を選択する第1情報選択部と、N個の前記第1情報にそれぞれ対応するN個の第2情報を生成する第2情報生成部と、N個の前記第1情報及びN個の前記第2情報を電子署名として、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に提供する署名提供部と、を備え、前記ベクトルsは署名鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記第2情報を利用して、当該第2情報に対応する第1情報の種類に応じて選択される所定の演算を実行することで得られる情報である、情報処理装置が提供される。また、本技術の別の観点によれば、環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報保持部と、前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたN組のメッセージを取得するメッセージ取得部と、1組の入力情報に対してk通りk≧3の第1情報の中から1個の第1情報を選択する一方向性関数に対し、文書MとN組の前記メッセージとを入力することで選択されたN個の第1情報と、N個の前記第1情報にそれぞれ対応するN個の第2情報とで構成される電子署名を取得する署名取得部と、前記メッセージ、前記多次多変数多項式の組F、前記ベクトルy、及び前記電子署名に基づいて前記文書Mの正当性を検証する署名検証部と、を備え、前記ベクトルsは署名鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記第2情報を利用して、当該第2情報に対応する第1情報の種類に応じて選択される所定の演算を実行することで得られる情報である、情報処理装置が提供される。また、本技術の別の観点によれば、環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてN組のメッセージを生成するステップと、1組の入力情報に対してk通りk≧3の第1情報の中から1個の第1情報を選択する一方向性関数に対し、文書MとN組の前記メッセージとを入力して、N個の第1情報を選択するステップと、N個の前記第1情報にそれぞれ対応するN個の第2情報を生成するステップと、N個の前記第1情報及びN個の前記第2情報を電子署名として、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に提供するステップと、を含み、前記ベクトルsは署名鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記第2情報を利用して、当該第2情報に対応する第1情報の種類に応じて選択される所定の演算を実行することで得られる情報である、署名提供方法が提供される。また、本技術の別の観点によれば、環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持するステップと、前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたN組のメッセージを取得するステップと、1組の入力情報に対してk通りk≧3の第1情報の中から1個の第1情報を選択する一方向性関数に対し、文書MとN組の前記メッセージとを入力することで選択されたN個の第1情報と、N個の前記第1情報にそれぞれ対応するN個の第2情報とで構成される電子署名を取得するステップと、前記メッセージ、前記多次多変数多項式の組F、前記ベクトルy、及び前記電子署名に基づいて前記文書Mの正当性を検証するステップと、を含み、前記ベクトルsは署名鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記第2情報を利用して、当該第2情報に対応する第1情報の種類に応じて選択される所定の演算を実行することで得られる情報である、署名検証方法が提供される。また、本技術の別の観点によれば、環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてN組のメッセージを生成するメッセージ生成機能と、1組の入力情報に対してk通りk≧3の第1情報の中から1個の第1情報を選択する一方向性関数に対し、文書MとN組の前記メッセージとを入力して、N個の第1情報を選択する第1情報選択機能と、N個の前記第1情報にそれぞれ対応するN個の第2情報を生成する第2情報生成機能と、N個の前記第1情報及びN個の前記第2情報を電子署名として、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に提供する署名提供機能と、をコンピュータに実現させるためのプログラムであり、前記ベクトルsは署名鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記第2情報を利用して、当該第2情報に対応する第1情報の種類に応じて選択される所定の演算を実行することで得られる情報である、プログラムが提供される。また、本技術の別の観点によれば、環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報保持機能と、前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたN組のメッセージを取得するメッセージ取得機能と、1組の入力情報に対してk通りk≧3の第1情報の中から1個の第1情報を選択する一方向性関数に対し、文書MとN組の前記メッセージとを入力することで選択されたN個の第1情報と、N個の前記第1情報にそれぞれ対応するN個の第2情報とで構成される電子署名を取得する署名取得機能と、前記メッセージ、前記多次多変数多項式の組F、前記ベクトルy、及び前記電子署名に基づいて前記文書Mの正当性を検証する署名検証機能と、をコンピュータに実現させるためのプログラムであり、前記ベクトルsは署名鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記第2情報を利用して、当該第2情報に対応する第1情報の種類に応じて選択される所定の演算を実行することで得られる情報である、プログラムが提供される。また、本技術の別の観点によれば、環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてN組のメッセージを生成するメッセージ生成機能と、1組の入力情報に対してk通りk≧3の第1情報の中から1個の第1情報を選択する一方向性関数に対し、文書MとN組の前記メッセージとを入力して、N個の第1情報を選択する第1情報選択機能と、N個の前記第1情報にそれぞれ対応するN個の第2情報を生成する第2情報生成機能と、N個の前記第1情報及びN個の前記第2情報を電子署名として、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に提供する署名提供機能と、をコンピュータに実現させるためのプログラムが記録された、コンピュータにより読み取り可能な記録媒体であり、前記ベクトルsは署名鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記第2情報を利用して、当該第2情報に対応する第1情報の種類に応じて選択される所定の演算を実行することで得られる情報である、記録媒体が提供される。また、本技術の別の観点によれば、環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報保持機能と、前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたN組のメッセージを取得するメッセージ取得機能と、1組の入力情報に対してk通りk≧3の第1情報の中から1個の第1情報を選択する一方向性関数に対し、文書MとN組の前記メッセージとを入力することで選択されたN個の第1情報と、N個の前記第1情報にそれぞれ対応するN個の第2情報とで構成される電子署名を取得する署名取得機能と、前記メッセージ、前記多次多変数多項式の組F、前記ベクトルy、及び前記電子署名に基づいて前記文書Mの正当性を検証する署名検証機能と、をコンピュータに実現させるためのプログラムが記録された、コンピュータにより読み取り可能な記録媒体であり、前記ベクトルsは署名鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記第2情報を利用して、当該第2情報に対応する第1情報の種類に応じて選択される所定の演算を実行することで得られる情報である、記録媒体が提供される。以上説明したように本技術によれば、効率的に解く手段トラップドアが知られていない多次多変数連立方程式を用いて、高い安全性及び高い効率を有する公開鍵認証方式又は電子署名方式を実現することが可能になる。以下に添付図面を参照しながら、本技術の好適な実施の形態について詳細に説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。[説明の流れについて]ここで、以下に記載する本技術の実施形態に関する説明の流れについて簡単に述べる。まず、図1を参照しながら、公開鍵認証方式のアルゴリズム構成について説明する。次いで、図2を参照しながら、電子署名方式のアルゴリズム構成について説明する。次いで、図3を参照しながら、nパスの公開鍵認証方式について説明する。次いで、図4を参照しながら、本技術の第1実施形態3パスに係る公開鍵認証方式のアルゴリズムについて説明する。次いで、図5を参照しながら、同実施形態に係る公開鍵認証方式の拡張アルゴリズムについて説明する。次いで、図6を参照しながら、同実施形態に係る公開鍵認証方式の並列化アルゴリズムについて説明する。次いで、図7を参照しながら、同実施形態に係る公開鍵認証方式の具体的なアルゴリズムについて説明する。次いで、図8~図15を参照しながら、同実施形態に係る公開鍵認証方式の効率的なアルゴリズム及びその変形例などについて説明する。次いで、図16を参照しながら、本技術の第2実施形態5パスに係る公開鍵認証方式のアルゴリズムについて説明する。次いで、図17を参照しながら、同実施形態に係る公開鍵認証方式の拡張アルゴリズムについて説明する。次いで、図18及び図19を参照しながら、同実施形態に係る公開鍵認証方式の並列化アルゴリズムについて説明する。次いで、図20を参照しながら、同実施形態に係る公開鍵認証方式の具体的なアルゴリズムについて説明する。次いで、図21~図35を参照しながら、同実施形態に係る公開鍵認証方式の効率的なアルゴリズム及びその変形例などについて説明する。次いで、本技術の第1及び第2実施形態に係る効率的なアルゴリズムを2次以上の多変数多項式に適用するための拡張手法について説明する。次いで、本技術の第1及び第2実施形態に係る対話プロトコルの頑強性を高める仕組みについて説明する。また、図36及び図37を参照しながら、イレギュラーな要求に起因する秘密鍵の漏洩を回避する仕組み及び偽証の機会をなくす仕組みについて述べる。次いで、図38を参照しながら、本技術の第1及び第2実施形態に係る各アルゴリズムを実現することが可能な情報処理装置のハードウェア構成例について説明する。最後に、本実施形態の技術的思想について纏め、当該技術的思想から得られる作用効果について簡単に説明する。説明項目1:はじめに1-1:公開鍵認証方式のアルゴリズム1-2:電子署名方式のアルゴリズム1-3:nパスの公開鍵認証方式2:第1実施形態2-1:公開鍵認証方式のアルゴリズム2-2:拡張アルゴリズム2-3:並列化アルゴリズム2-4:具体例2次多項式を利用する場合2-5:効率的なアルゴリズム2-6:電子署名方式への変形2-6-1:変形方法2-6-2:電子署名アルゴリズムの効率化2-7:多次多変数連立方程式の形式2-7-1:共通鍵ブロック暗号に関する形式2-7-2:ハッシュ関数に関する形式2-7-3:ストリーム暗号に関する形式2-8:直列並列ハイブリッドアルゴリズム3:第2実施形態3-1:公開鍵認証方式のアルゴリズム3-2:拡張アルゴリズム3-3:並列化アルゴリズム3-4:具体例2次多項式を利用する場合3-5:効率的なアルゴリズム3-6:直列並列ハイブリッドアルゴリズム4:効率的なアルゴリズムの拡張4-1:多変数多項式の高次化について4-2:拡張方式高次項の追加5:頑強性を高める仕組み5-1:システムパラメータの設定方法5-2:イレギュラーな要求に対する応答方法5-2-1:証明者による応答方法について5-2-2:検証者による応答方法について6:ハードウェア構成例7:まとめ<1:はじめに>はじめに、本技術に係る実施形態について詳細に説明するに先立ち、公開鍵認証方式のアルゴリズム、電子署名方式のアルゴリズム、及び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を実行する主体は、情報処理装置である。これら情報処理装置のハードウェア構成は、例えば、図38に示した通りである。つまり、鍵生成アルゴリズム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を実行する主体は、情報処理装置である。これら情報処理装置のハードウェア構成は、例えば、図38に示した通りである。つまり、鍵生成アルゴリズム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:第1実施形態>以下、本技術の第1実施形態について説明する。本実施形態は、多次多変数連立方程式に対する求解問題の困難性に安全性の根拠をおく公開鍵認証方式及び電子署名方式に関する。但し、本実施形態は、HFE電子署名方式などの従来手法とは異なり、効率的に解く手段トラップドアを持たない多次多変数連立方程式を利用する公開鍵認証方式及び電子署名方式に関する。[2-1:公開鍵認証方式のアルゴリズム]まず、図4を参照しながら、本実施形態に係る公開鍵認証方式以下、本手法のアルゴリズムについて説明する。図4は、本手法のアルゴリズムについて説明するための説明図である。なお、本手法は、鍵生成アルゴリズム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は、任意に数wを選択する。次いで、証明者アルゴリズムPは、擬似乱数生成器G1に数wを適用してベクトルr∈Kn及び数wAを生成する。つまり、証明者アルゴリズムPは、r,wA←G1wを計算する。次いで、証明者アルゴリズムPは、擬似乱数生成器G2に数wAを適用して多変数多項式FAx=fA1x,...,fAmxを生成する。つまり、証明者アルゴリズムPは、FA←G2wAを計算する。工程1続き:次いで、証明者アルゴリズムPは、z←s-rを計算する。この計算は、秘密鍵sをベクトルrによりマスクする操作に相当する。さらに、証明者アルゴリズムPは、FBx←FxrFAxを計算する。この計算は、xに関して多変数多項式Fxrを多変数多項式FAxによりマスクする操作に相当する。工程1続き:次いで、証明者アルゴリズムPは、FAz及びzのハッシュ値c1を生成する。つまり、証明者アルゴリズムPは、c1←H1FAz,zを計算する。また、証明者アルゴリズムPは、数wAのハッシュ値c2を生成する。つまり、証明者アルゴリズムPは、c2←H2wAを計算する。さらに、証明者アルゴリズムPは、多変数多項式FBのハッシュ値c3を生成する。つまり、証明者アルゴリズムPは、c3←H3FBxを計算する。なお、上記のH1...、H2...、H3...は、ハッシュ関数である。このハッシュ値c1,c2,c3は、メッセージとして検証者アルゴリズムVに送られる。このとき、sに関する情報、rに関する情報、zに関する情報が検証者に一切漏れない点に注意されたい。工程2:メッセージc1,c2,c3を受け取った検証者アルゴリズムVは、3つの検証パターンのうち、どの検証パターンを利用するかを選択する。例えば、検証者アルゴリズムVは、検証パターンの種類を表す3つの数値{0,1,2}の中から1つの数値を選択し、選択した数値を要求dに設定する。この要求dは証明者アルゴリズムPに送られる。工程3:要求dを受け取った証明者アルゴリズムPは、受け取った要求dに応じて検証者アルゴリズムVに送る返答σを生成する。d=0の場合、証明者アルゴリズムPは、返答σ=wを生成する。d=1の場合、証明者アルゴリズムPは、返答σ=wA,zを生成する。d=2の場合、証明者アルゴリズムPは、返答σ=FBz,zを生成する。工程3で生成された返答σは、検証者アルゴリズムVに送られる。このとき、d=0の場合にはzに関する情報が検証者に一切漏れておらず、d=1又は2の場合にはrに関する情報が検証者に一切漏れない点に注意されたい。工程4:返答σを受け取った検証者アルゴリズムVは、受け取った返答σを利用して以下の検証処理を実行する。d=0の場合、検証者アルゴリズムVは、rA,wB←G1σを計算する。さらに、検証者アルゴリズムVは、FC←G2wBを計算する。そして、検証者アルゴリズムVは、c2=H2wBの等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、c3=H3FxrAFCxの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。d=1の場合、検証者アルゴリズムVは、wB,zA←σとする。さらに、検証者アルゴリズムVは、FC←G2wBを計算する。そして、検証者アルゴリズムVは、c1=H1FCzA,zAの等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、c2=H2wBの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。d=2の場合、検証者アルゴリズムVは、FD,zA←σとする。そして、検証者アルゴリズムVは、c1=H1FDzA-y,zAの等号が成り立つか否かを検証する。さらに、検証者アルゴリズムVは、c3=H3FDの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、本手法に係る各アルゴリズムの構成について説明した。本手法の健全性についてここで、本手法の健全性について説明を補足する。本手法の健全性は、検証者アルゴリズムVが選択可能な要求d=0,1,2の全てについて、証明者アルゴリズムPが正しい返答σを返したならば、下記の式6及び式7を満たすFD、FC、rA、zAが計算可能になるという論理に基づいて保証されている。上記の健全性が保証されることにより、多次多変数連立方程式の求解問題を解かない限りにおいて2/3より高い確率で偽証が成功することは不可能であると保証される。つまり、検証者の要求d=0,1,2の全てに正しく回答するためには、偽証者が上記の式6及び式7を満たすFD、FC、rA、zAを計算できる必要がある。言い換えると、偽証者はFs=yを満たすsを計算できる必要がある。但し、検証者の要求d=0,1,2の高々2つについて偽証者が正しく回答できてしまう可能性は残る。そのため、偽証の成功確率は2/3となる。なお、上記の対話プロトコルを十分な回数実行することで、偽証の成功確率は無視できるほど小さくなる。以上、本手法の健全性について説明した。変形例ここで、上記アルゴリズムの一変形例を紹介する。上記の鍵生成アルゴリズムGenは、y←Fsを計算し、公開鍵をF,yに設定していた。一方、本変形例において、鍵生成アルゴリズムGenは、y1,...,ym←Fs及びf1x,...,fmx←f1x-y1,...,fmx-ymを計算し、公開鍵をf1,...,fmに設定する。このように変形すると、y=0として対話プロトコルを実行することが可能になる。また、上記の証明者アルゴリズムPは、FBz及びzからメッセージc1を生成していた。しかし、FBz=FAzの関係があることにより、FAz及びzからメッセージc1を生成するように変形しても、同様の対話プロトコルが実現される。また、FBzのハッシュ値とzのハッシュ値とを別々に計算し、それぞれをメッセージとして検証者アルゴリズムVに送るように証明者アルゴリズムPの構成を変形してもよい。また、上記の証明者アルゴリズムPは、数wに擬似乱数生成器G1を適用してベクトルr及び数wAを生成していた。また、上記の証明者アルゴリズムPは、数wAを擬似乱数生成器G2に適用して多変数多項式FAxを生成していた。しかし、G1を恒等写像とし、最初からw=r,FAを算出するように証明者アルゴリズムPの構成を変形してもよい。この場合には、数wをG1に適用する必要はない。なお、G2についても同様である。また、上記の対話プロトコルにおいては公開鍵をF,yとしている。公開鍵に含まれる多変数多項式Fは秘密鍵skに依らないパラメータである。そのため、証明者毎に多変数多項式Fを設定せず、システム全体で共通の多変数多項式Fを利用するように構成されていてもよい。この場合、証明者毎に設定される公開鍵はyだけで済むことになり、公開鍵のサイズを小さくすることが可能になる。但し、安全性の観点から、証明者毎に多変数多項式Fを設定する方が好ましいケースも考えられる。このようなケースにおける多変数多項式Fの設定方法については後段において詳述する。また、上記の対話プロトコルにおいては公開鍵をf1,...,fm,yとしているが、F=f1,...,fmは適当に選択してもよいパラメータである。そのため、証明者及び検証者は、例えば、乱数のシードwpkを用意し、擬似乱数生成器Gを利用してF←Gwpkを計算してもよい。この場合、公開鍵はwpk,yとなり、F,yを公開鍵として公開する場合よりも、公開鍵のサイズを小さくすることが可能になる。上記のアルゴリズムでは、ハッシュ関数H1,H2,H3を用いてc1,c2,c3を計算しているが、ハッシュ関数の代わりにコミットメント関数COMを用いてもよい。コミットメント関数COMは、文字列Sと乱数ρの2つを引数にとる関数である。コミットメント関数の例としては、ShaiHaleviとSilvioMicaliによって国際会議CRYPTO1996で発表された方式などがある。このコミットメント関数を用いる場合、c1,c2,c3を計算する前に、乱数ρ1,ρ2,ρ3を用意し、ハッシュ関数H1,H2,H3を適用する代わりにコミットメント関数COM,ρ1,COM,ρ2,COM,ρ2を適用してc1,c2,c3を生成する。但し、検証者がciを生成するために必要なρiは、返答σに含めて送られる。なお、これらの変形は、後述する全てのアルゴリズムに適用可能である。以上、本手法の変形例について説明した。[2-2:拡張アルゴリズム]次に、図5を参照しながら、本手法を拡張した公開鍵認証方式以下、拡張手法のアルゴリズムについて説明する。図5は、拡張手法に基づく対話プロトコルの流れについて説明するための説明図である。ここで説明する拡張手法は、1パス目に送信するメッセージc1,c2,c3を1つのハッシュ値cに変換して検証者に送るというものである。但し、3パス目で送る返答σを用いても復元できないメッセージについては、返答σと共に検証者に送られる。この拡張手法を適用すると、対話プロトコルの中で検証者に送る情報量を減らすことが可能になる。以下、拡張手法に係る各アルゴリズムの構成について詳細に説明する。鍵生成アルゴリズム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次に、図5を参照しながら、対話プロトコルの中で証明者アルゴリズムPが実行する処理及び検証者アルゴリズムVが実行する処理について説明する。上記の対話プロトコルの中で、証明者は、秘密鍵sの情報を検証者に一切漏らさずに、自身がy=Fsを満たすsを知っていることを検証者に示す。一方、検証者は、証明者がy=Fsを満たすsを知っているか否かを検証する。なお、公開鍵pkは、検証者に公開されているものとする。また、秘密鍵sは、証明者により秘密に管理されているものとする。以下、図5に示したフローチャートに沿って説明を進める。工程1:まず、証明者アルゴリズムPは、任意に数wを選択する。次いで、証明者アルゴリズムPは、擬似乱数生成器G1に数wを適用してベクトルr∈Knと数wAを生成する。つまり、証明者アルゴリズムPは、r,wA←G1wを計算する。次いで、証明者アルゴリズムPは、擬似乱数生成器G2に数wAを適用して多変数多項式FAx=fA1x,...,fAmxを生成する。つまり、証明者アルゴリズムPは、FA←G2wAを計算する。工程1続き:次いで、証明者アルゴリズムPは、z←s-rを計算する。この計算は、秘密鍵sをベクトルrによりマスクする操作に相当する。さらに、証明者アルゴリズムPは、FBx←FxrFAxを計算する。この計算は、xについての多項式の組Fxrを多項式の組FAxによりマスクする操作に相当する。工程1続き:次いで、証明者アルゴリズムPは、FBzとzのハッシュ値c1を生成する。つまり、証明者アルゴリズムPは、c1←H1FBz,zを計算する。また、証明者アルゴリズムPは、数wAのハッシュ値c2を生成する。つまり、証明者アルゴリズムPは、c2←H2wAを計算する。さらに、証明者アルゴリズムPは、多項式の組FBのハッシュ値c3を生成する。つまり、証明者アルゴリズムPは、c3←H3FBを計算する。なお、上記のH1...、H2...、H3...は、ハッシュ関数である。拡張方式の場合、証明者アルゴリズムPは、ハッシュ値の組c1,c2,c3をハッシュ関数Hに適用してハッシュ値cを生成し、生成したハッシュ値cを検証者アルゴリズムVに送る。工程2:ハッシュ値cを受け取った検証者アルゴリズムVは、3つの検証パターンのうち、どの検証パターンを利用するかを選択する。例えば、検証者アルゴリズムVは、検証パターンの種類を表す3つの数値{0,1,2}の中から1つの数値を選択し、選択した数値を要求dに設定する。この要求dは証明者アルゴリズムPに送られる。工程3:要求dを受け取った証明者アルゴリズムPは、受け取った要求dに応じて検証者アルゴリズムVに送る返答σを生成する。d=0の場合、証明者アルゴリズムPは、返答σ,c=w,c1を生成する。d=1の場合、証明者アルゴリズムPは、返答σ,c=wA,z,c3を生成する。d=2の場合、証明者アルゴリズムPは、返答σ,c=FB,z,c2を生成する。工程3で生成された返答σ,cは、検証者アルゴリズムVに送られる。工程4:返答σを受け取った検証者アルゴリズムVは、受け取った返答σ,cを利用して以下の検証処理を実行する。d=0の場合、検証者アルゴリズムVは、rA,wB←G1σを計算する。次いで、検証者アルゴリズムVは、FC←G2wBを計算する。次いで、検証者アルゴリズムVは、c2A=H2wBを計算する。次いで、検証者アルゴリズムVは、c3A=H3FxrAFCxを計算する。その後、検証者アルゴリズムVは、c=Hc,c2A,c3Aの等号が成り立つか否かを検証する。そして、検証者アルゴリズムVは、検証が成功した場合に認証成功を示す値1を出力し、検証が失敗した場合に認証失敗を示す値0を出力する。d=1の場合、検証者アルゴリズムVは、wB,zA←σとする。次いで、検証者アルゴリズムVは、FC←G2wBを計算する。次いで、検証者アルゴリズムVは、c1A=H1FCzA,zAを計算する。次いで、検証者アルゴリズムVは、c2A=H2wBを計算する。その後、検証者アルゴリズムVは、c=Hc1A,c2A,cの等号が成り立つか否かを検証する。そして、検証者アルゴリズムVは、検証が成功した場合に認証成功を示す値1を出力し、検証が失敗した場合に認証失敗を示す値0を出力する。d=2の場合、検証者アルゴリズムVは、FD,zA←σとする。次いで、検証者アルゴリズムVは、c1A=H1FDzA-y,zAを計算する。次いで、検証者アルゴリズムVは、c3A=H3FDを計算する。その後、検証者アルゴリズムVは、c=Hc1A,c,c3Aの等号が成り立つか否かを検証する。そして、検証者アルゴリズムVは、検証が成功した場合に認証成功を示す値1を出力し、検証が失敗した場合に認証失敗を示す値0を出力する。以上、拡張手法に係る各アルゴリズムの構成について説明した。拡張手法を適用することにより、対話プロトコルの中で送受信される情報量を削減することが可能になる。[2-3:並列化アルゴリズム]先に述べた通り、本手法又は拡張手法に係る対話プロトコルを適用すれば、偽証が成功する確率を2/3以下に抑制することができる。従って、この対話プロトコルを2回実行すれば、偽証が成功する確率を2/32以下に抑制することができる。さらに、この対話プロトコルをN回実行すると、偽証が成功する確率は2/3Nとなり、Nを十分に大きい数例えば、N=140にすれば、偽証が成功する確率は無視できる程度に小さくなる。対話プロトコルを複数回実行する方法としては、例えば、メッセージ、要求、返答のやり取りを逐次的に複数回繰り返す直列的な方法と、1回分のやり取りで複数回分のメッセージ、要求、返答のやり取りを行う並列的な方法とが考えられる。ここでは、本手法に係る対話プロトコルを並列的な方法に係る対話プロトコル以下、並列化アルゴリズムに拡張する方法について説明する。例えば、並列化アルゴリズムは図6のようになる。以下、図6を参照しながら、並列化アルゴリズムの内容について説明する。鍵生成アルゴリズム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次に、図6を参照しながら、対話プロトコルの中で証明者アルゴリズムPが実行する処理及び検証者アルゴリズムVが実行する処理について説明する。上記の対話プロトコルの中で、証明者は、秘密鍵sの情報を検証者に一切漏らさずに、自身がy=Fsを満たすsを知っていることを検証者に示す。一方、検証者は、証明者がy=Fsを満たすsを知っているか否かを検証する。なお、公開鍵pkは、検証者に公開されているものとする。また、秘密鍵sは、証明者により秘密に管理されているものとする。以下、図6に示したフローチャートに沿って説明を進める。工程1:まず、証明者アルゴリズムPは、i=1~Nについて、以下の処理1~処理8を実行する。処理1:証明者アルゴリズムPは、任意に数wiを選択する。処理2:証明者アルゴリズムPは、擬似乱数生成器G1に数wiを適用してベクトルri∈Knと数wiAを生成する。つまり、証明者アルゴリズムPは、ri,wiA←G1wiを計算する。処理3:証明者アルゴリズムPは、擬似乱数生成器G2に数wiAを適用して多変数多項式の組FiAxを生成する。つまり、証明者アルゴリズムPは、FiA←G2wiAを計算する。処理4:証明者アルゴリズムPは、zi←si-riを計算する。この計算は、秘密鍵siをベクトルriによりマスクする操作に相当する。処理5:証明者アルゴリズムPは、FiBx←FxriFiAxを計算する。この計算は、xについての多項式の組Fxriを多項式の組FiAxによりマスクする操作に相当する。処理6:証明者アルゴリズムPは、FiBzi及びziのハッシュ値c1,iを生成する。つまり、証明者アルゴリズムPは、c1,i←H1FiBzi,ziを計算する。処理7:証明者アルゴリズムPは、数wiAのハッシュ値c2,iを生成する。つまり、証明者アルゴリズムPは、c2,i←H2wiAを計算する。処理8:証明者アルゴリズムPは、多項式の組FiBのハッシュ値c3,iを生成する。つまり、証明者アルゴリズムPは、c3,i←H3FiBを計算する。なお、上記のH1...、H2...、H3...は、ハッシュ関数である。また、ハッシュ値c1,i,c2,i,c3,iはメッセージである。i=1~Nについて、上記の処理1~処理8が実行された後、工程1で生成されたメッセージc1,i,c2,i,c3,ii=1~Nは、検証者アルゴリズムVに送られる。工程2:メッセージc1,i,c2,i,c3,ii=1~Nを受け取った検証者アルゴリズムVは、i=1~Nのそれぞれについて、3つの検証パターンのうち、どの検証パターンを利用するかを選択する。例えば、検証者アルゴリズムVは、i=1~Nのそれぞれについて、検証パターンの種類を表す3つの数値{0,1,2}の中から1つの数値を選択し、選択した数値を要求diに設定する。この要求diは証明者アルゴリズムPに送られる。工程3:要求dii=1~Nを受け取った証明者アルゴリズムPは、受け取った要求diに応じて検証者アルゴリズムVに送る返答σiを生成する。このとき、証明者アルゴリズムPは、i=1~Nについて、以下の処理1~処理3を実行する。処理1:di=0の場合、証明者アルゴリズムPは、返答σi=wiを生成する。処理2:di=1の場合、証明者アルゴリズムPは、返答σi=wiA,ziを生成する。処理3:di=2の場合、証明者アルゴリズムPは、返答σi=FiB,ziを生成する。上記の処理1~処理3の処理が実行された後、返答σii=1~Nは、検証者アルゴリズムVに送られる。工程4:返答σii=1~Nを受け取った検証者アルゴリズムVは、受け取った返答σii=1~Nを利用して以下の検証処理を実行する。なお、以下の処理は、i=1~Nについて実行される。di=0の場合、検証者アルゴリズムVは、riA,wiB←G1σiを計算する。さらに、検証者アルゴリズムVは、FiC←G2wiBを計算する。そして、検証者アルゴリズムVは、c2,i=H2wiBの等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、c3,i=H3FxriAFiCxの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。di=1の場合、検証者アルゴリズムVは、wiB,ziA←σiとする。さらに、検証者アルゴリズムVは、FiC←G2wiBを計算する。そして、検証者アルゴリズムVは、c1,i=H1FiCziA,ziAの等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、c2=H2wiBの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。di=2の場合、検証者アルゴリズムVは、FiD,ziA←σiとする。そして、検証者アルゴリズムVは、c1,i=H1FiDziA-y,ziAの等号が成り立つか否かを検証する。さらに、検証者アルゴリズムVは、c3,i=H3FiDxの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、本手法の対話プロトコルを並列的に実行する方法について説明した。上記のように、本手法の対話プロトコルを繰り返し実行することにより、偽証が成功する確率を無視できる程度まで低減させることが可能になる。なお、工程1の後でc1,1,c1,2,c1,3,...,cN,1,cN,2,cN,3を検証者に送信する代わりに、ハッシュ値c=Hc1,1,c1,2,c1,3,...,cN,1,cN,2,cN,3を送信するように変形してもよい。但し、返答から復元できないメッセージの存在を考慮し、このようなメッセージが返答と共に証明者から検証者へと送られるように対話プロトコルを変形する必要がある。この変形を適用すると、1パス目で送るメッセージが1つのハッシュ値cだけとなり、大幅に通信量が削減される。例えば、N回の並列的繰り返し構成の場合、送るべき情報の数を2N-1個削減することが可能になる。好適なパラメータの設定方法についてさて、本実施形態に係る対話プロトコルは、受動的攻撃に対する安全性が保証されている。しかし、この対話プロトコルを並列的に繰り返し実行する上記の方法を適用した場合、能動的攻撃に対する安全性が確実に保証されていることを証明できるようにするには、以下に示すような条件が必要になる。上記の対話プロトコルは、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を用いたという情報を検証者に知られないようにすることが可能になる。つまり、この保証が成り立てば、対話プロトコルを並列的に繰り返し実行する場合においても、能動的攻撃に対する安全性を保証することが可能になる。図40を参照しながら、m本のn変数多次多項式で構成される関数F:Kn→Kmについて考えると但し、n>m、2つ目の原像を持たない定義域の要素数は、最大で|K|m-1個しか存在しない。そのため、|K|m-nを十分に小さくすると、2つ目の原像を持たない定義域の要素が選択される確率を無視できる程度にまで小さくすることができる。つまり、n変数多次多項式f1,...,fmの数mがその変数の数nよりも十分に小さな値に設定されていれば、公開鍵pkに対して2つ以上の秘密鍵sが存在することを保証できる。その結果、検証で受理される対話を行った場合においても、対話の際に証明者がsを用いたという情報を検証者に知られないようにすることが可能になり、対話プロトコルを並列的に繰り返し実行する場合においても、能動的攻撃に対する安全性が保証される。以上説明したように、n変数多次多項式f1,...,fmの数mがその変数の数nよりも小さな値n>m;好ましくは2m-n≪1に設定する設定条件を課すことで、対話プロトコルを並列的に繰り返し実行する場合の安全性を保証することが可能になる。[2-4:具体例2次多項式を利用する場合]次に、図7を参照しながら、多変数多項式Fとしてn変数2次多項式を利用する場合について説明する。図7は、本手法の一具体例について説明するための説明図である。鍵生成アルゴリズムGen鍵生成アルゴリズムGenは、環K上で定義されるm本の2次多項式f1x1,...,xn,...,fmx1,...,xn、及びベクトルs=s1,...,sn∈Knを生成する。次に、鍵生成アルゴリズムGenは、y=y1,...,ym←f1s,...,fmsを計算する。そして、鍵生成アルゴリズムGenは、f1,...,fm,yを公開鍵pkに設定し、sを秘密鍵に設定する。なお、以下では、ベクトルx1,...,xnをxと表記し、2次多項式の組f1x,...,fmxをFxと表記する。但し、2次多項式fixは、下記の式8のように表現されるものとする。証明者アルゴリズムP、検証者アルゴリズムV次に、図7を参照しながら、対話プロトコルの中で証明者アルゴリズムP及び検証者アルゴリズムVにより実行される処理について説明する。工程1:まず、証明者アルゴリズムPは、任意に数wを選択する。次いで、証明者アルゴリズムPは、擬似乱数生成器G1に数wを適用してベクトルr∈Knと数wAを生成する。つまり、証明者アルゴリズムPは、r,wA←G1wを計算する。次いで、証明者アルゴリズムPは、擬似乱数生成器G2に数wAを適用して1次多項式の組f1Ax,...,fmAxを生成する。つまり、証明者アルゴリズムPは、f1A,...,fmA←G2wAを計算する。但し、1次多項式fiAxは、下記の式9のように表現される。また、1次多項式の組f1Ax,...,fmAxをFAxと表記する。工程1続き:次いで、証明者アルゴリズムPは、z←s-rを計算する。この計算は、秘密鍵sをベクトルrによりマスクする操作に相当する。さらに、証明者アルゴリズムPは、FBx←FxrFAxを計算する。この計算は、xに関して2次多項式Fxrを1次多項式FAxによりマスクする操作に相当する。Fxrの中においてrに関する情報はxの1次の項にしか現れない。そのため、rに関する情報は全てFAxによりマスクされる。工程1続き:次いで、証明者アルゴリズムPは、FAz及びzのハッシュ値c1を生成する。つまり、証明者アルゴリズムPは、c1←H1FAz,zを計算する。また、証明者アルゴリズムPは、数wAのハッシュ値c2を生成する。つまり、証明者アルゴリズムPは、c2←H2wAを計算する。さらに、証明者アルゴリズムPは、多変数多項式FBのハッシュ値c3を生成する。つまり、証明者アルゴリズムPは、c3←H3FBを計算する。なお、上記のH1...、H2...、H3...は、ハッシュ関数である。工程1で生成されたメッセージc1,c2,c3は、検証者アルゴリズムVに送られる。工程2:メッセージc1,c2,c3を受け取った検証者アルゴリズムVは、3つの検証パターンのうち、どの検証パターンを利用するかを選択する。例えば、検証者アルゴリズムVは、検証パターンの種類を表す3つの数値{0,1,2}の中から1つの数値を選択し、選択した数値を要求dに設定する。この要求dは証明者アルゴリズムPに送られる。工程3:要求dを受け取った証明者アルゴリズムPは、受け取った要求dに応じて検証者アルゴリズムVに送る返答σを生成する。d=0の場合、証明者アルゴリズムPは、返答σ=wを生成する。d=1の場合、証明者アルゴリズムPは、返答σ=wA,zを生成する。d=2の場合、証明者アルゴリズムPは、返答σ=FBz,zを生成する。工程3で生成された返答σは、検証者アルゴリズムVに送られる。工程4:返答σを受け取った検証者アルゴリズムVは、受け取った返答σを利用して以下の検証処理を実行する。d=0の場合、検証者アルゴリズムVは、rA,wB←G1σを計算する。さらに、検証者アルゴリズムVは、FC←G2wBを計算する。そして、検証者アルゴリズムVは、c2=H2wBの等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、c3=H3FxrAFCxの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。d=1の場合、検証者アルゴリズムVは、wB,zA←σとする。さらに、検証者アルゴリズムVは、FC←G2wBを計算する。そして、検証者アルゴリズムVは、c1=H1FCzA,zAの等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、c2=H2wBの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。d=2の場合、検証者アルゴリズムVは、FD,zA←σとする。そして、検証者アルゴリズムVは、c1=H1FDzA-y,zAの等号が成り立つか否かを検証する。さらに、検証者アルゴリズムVは、c3=H3FDの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、本手法の一具体例について説明した。[2-5:効率的なアルゴリズム]次に、本手法に係るアルゴリズムを効率化する方法について述べる。2次多項式の組f1x,...,fmxは、下記の式10のように表現することができる。但し、x=x1,...,xnである。また、A1,...,Amは、n×n行列である。さらに、b1,...,bmはそれぞれn×1ベクトルである。この表現を用いると、多変数多項式Fは、下記の式11及び式12のように表現することができる。この表現が成り立つことは、下記の式13から容易に確認することができる。このようにFxyをxに依存する第1の部分と、yに依存する第2の部分と、x及びyの両方に依存する第3の部分とに分けたとき、第3の部分に対応する項Fbx,yは、x及びyについて双線形になる。この性質を利用すると、効率的なアルゴリズムを構築することが可能になる。例えば、ベクトルt∈Kn、e∈Kmを用いて、多変数多項式Fxrのマスクに利用する多変数多項式FAxをFAx=Fbx,teと表現する。この場合、多変数多項式FxrとFAxとの和は、下記の式14のように表現される。ここで、tA=rt、eA=Freとおけば、多変数多項式FBx=FxrFAxは、ベクトルtA∈Kn、eA∈Kmにより表現することができる。そのため、FAx=Fbx,teに設定すれば、Kn上のベクトル及びKm上のベクトルを用いてFA及びFBを表現できるようになり、通信に必要なデータサイズを大幅に減らすことが可能になる。具体的には、数千~数万倍程度、通信効率が向上する。なお、上記の変形により、FB或いはFAからrに関する情報が一切漏れることはない。例えば、eA及びtA或いはe及びtを与えられても、e及びt或いはeA及びtAを知らない限り、rの情報を一切知ることはできない。従って、上記の変形を本手法に施したとしても、零知識性は担保される。以下、図8~図10を参照しながら、本手法に係る効率的なアルゴリズムについて説明する。なお、鍵生成アルゴリズムGenの構成は変わらないため、ここでは詳細な説明を省略する。効率的なアルゴリズムの構成例1:図8まず、図8に示した効率的なアルゴリズムの構成について説明する。工程1:証明者アルゴリズムPは、任意に数wを選択する。次いで、証明者アルゴリズムPは、擬似乱数生成器G1に数wを適用してベクトルr∈Knと数wAを生成する。つまり、証明者アルゴリズムPは、r,wA←G1wを計算する。次いで、証明者アルゴリズムPは、擬似乱数生成器G2に数wAを適用して2つのベクトルt∈Kn、e∈Kmを生成する。つまり、証明者アルゴリズムPは、t,e←G2wAを計算する。次いで、証明者アルゴリズムPは、z←s-rを計算する。この計算は、秘密鍵sをベクトルrによりマスクする操作に相当する。さらに、証明者アルゴリズムPは、tA←rtを計算する。次いで、証明者アルゴリズムPは、eA←Freを計算する。工程1続き:次いで、証明者アルゴリズムPは、上記の式14に基づいてFbz,tを算出し、Fbz,te及びzのハッシュ値c1を生成する。つまり、証明者アルゴリズムPは、c1←H1Fbz,te,zを計算する。また、証明者アルゴリズムPは、数wAのハッシュ値c2を生成する。つまり、証明者アルゴリズムPは、c2←H2wAを計算する。さらに、証明者アルゴリズムPは、2つのベクトルtA及びeAのハッシュ値c3を生成する。つまり、証明者アルゴリズムPは、c3←H3tA,eAを計算する。なお、上記のH1...、H2...、H3...は、ハッシュ関数である。工程1で生成されたメッセージc1,c2,c3は、検証者アルゴリズムVに送られる。工程2:メッセージc1,c2,c3を受け取った検証者アルゴリズムVは、3つの検証パターンのうち、どの検証パターンを利用するかを選択する。例えば、検証者アルゴリズムVは、検証パターンの種類を表す3つの数値{0,1,2}の中から1つの数値を選択し、選択した数値を要求dに設定する。この要求dは証明者アルゴリズムPに送られる。工程3:要求dを受け取った証明者アルゴリズムPは、受け取った要求dに応じて検証者アルゴリズムVに送る返答σを生成する。d=0の場合、証明者アルゴリズムPは、返答σ=wを生成する。d=1の場合、証明者アルゴリズムPは、返答σ=wA,zを生成する。d=2の場合、証明者アルゴリズムPは、返答σ=tA,eA,zを生成する。工程3で生成された返答σは、検証者アルゴリズムVに送られる。工程4:返答σを受け取った検証者アルゴリズムVは、受け取った返答σを利用して以下の検証処理を実行する。d=0の場合、検証者アルゴリズムVは、rA,wB←G1σを計算する。さらに、検証者アルゴリズムVは、tB,eB←G2wBを計算する。そして、検証者アルゴリズムVは、c2=H2wBの等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、c3=H3rAtB,FrAeBの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。d=1の場合、検証者アルゴリズムVは、wB,zA←σとする。さらに、検証者アルゴリズムVは、tB,eB←G2wBを計算する。そして、検証者アルゴリズムVは、c1=H1FbzA,tBeB,zAの等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、c2=H2wBの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。d=2の場合、検証者アルゴリズムVは、tC,eC,zA←σとする。そして、検証者アルゴリズムVは、c1=H1FzAFbzA,tCeC-y,zAの等号が成り立つか否かを検証する。さらに、検証者アルゴリズムVは、c3=H3tC,eCの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、効率的なアルゴリズムの構成例1について説明した。この効率的なアルゴリズムを利用することにより、通信に必要なデータサイズが大幅に削減される。また、Fxrの計算が必要なくなるため、計算効率も向上する。効率的なアルゴリズムの構成例2:図9次に、図9に示した効率的なアルゴリズムの構成について説明する。図9に示した構成を適用した場合も、図8に示した構成を適用した場合と同様に、通信効率及び計算効率の向上効果が得られる。但し、ここでは図8に示した構成との差分について述べる。図8に示したアルゴリズムの工程3において、d=0の場合にσをwに設定しているが、d=0の場合に設定されるσは、r,t,eが復元できる情報であればどのような情報でもよい。例えば、図9に示すように、工程3においてd=0の場合に設定されるσの内容をwA,tAにしてもよい。但し、この変形を行う場合には、工程4において検証者アルゴリズムVが行う検証内容の一部を変形する必要がある。具体的には、工程4においてd=0の場合に検証者アルゴリズムVが行う検証内容のうち、c3=H3rAtB,FrAeBの検証がc3=H3tA,FtA-tBeBの検証に置き換えられる。以上、効率的なアルゴリズムの構成例2について説明した。効率的なアルゴリズムの構成例3:図10次に、図10に示した効率的なアルゴリズムの構成について説明する。工程1:証明者アルゴリズムPは、任意にベクトルr,t∈Kn及びe∈Kmを生成する。次いで、証明者アルゴリズムPは、rA←s-rを計算する。この計算は、秘密鍵sをベクトルrによりマスクする操作に相当する。さらに、証明者アルゴリズムPは、tA←rtを計算する。次いで、証明者アルゴリズムPは、eA←Fr-eを計算する。工程1続き:次いで、証明者アルゴリズムPは、c1←H1FbrA,te,rAを計算する。次いで、証明者アルゴリズムPは、c2←H2t,eを計算する。次いで、証明者アルゴリズムPは、c3←H3tA,eAを計算する。なお、上記のH1...、H2...、H3...は、ハッシュ関数である。工程1で生成されたメッセージc1,c2,c3は、検証者アルゴリズムVに送られる。工程2:メッセージc1,c2,c3を受け取った検証者アルゴリズムVは、3つの検証パターンのうち、どの検証パターンを利用するかを選択する。例えば、検証者アルゴリズムVは、検証パターンの種類を表す3つの数値{0,1,2}の中から1つの数値を選択し、選択した数値を要求dに設定する。この要求dは証明者アルゴリズムPに送られる。工程3:要求dを受け取った証明者アルゴリズムPは、受け取った要求dに応じて検証者アルゴリズムVに送る返答σを生成する。d=0の場合、証明者アルゴリズムPは、返答σ=r,tA,eAを生成する。d=1の場合、証明者アルゴリズムPは、返答σ=rA,t,eを生成する。d=2の場合、証明者アルゴリズムPは、返答σ=rA,tA,eAを生成する。工程3で生成された返答σは、検証者アルゴリズムVに送られる。工程4:返答σを受け取った検証者アルゴリズムVは、受け取った返答σを利用して以下の検証処理を実行する。d=0の場合、検証者アルゴリズムVは、c2=H2r-tA,Fr-eAの等号が成り立つか否かを検証する。さらに、検証者アルゴリズムVは、c3=H3tA,eAの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。d=1の場合、検証者アルゴリズムVは、c1=H1FbrA,te,rAの等号が成り立つか否かを検証する。さらに、検証者アルゴリズムVは、c2=H2t,eの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。d=2の場合、検証者アルゴリズムVは、c1=H1y-FrA-FbtA,rA-eA,rAの等号が成り立つか否かを検証する。さらに、検証者アルゴリズムVは、c3=H3tA,eAの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、効率的なアルゴリズムの構成例3について説明した。この効率的なアルゴリズムを利用することにより、通信に必要なデータサイズが大幅に削減される。また、Fxrの計算が必要なくなるため、計算効率も向上する。効率的なアルゴリズムの並列化:図11次に、図11を参照しながら、効率的なアルゴリズムを並列化する方法について説明する。図11に示した構成以下、並列化アルゴリズムは、上記の構成例3に係る効率的なアルゴリズムを並列化したものである。工程1:証明者アルゴリズムPは、i=1~Nについて処理1~処理6を実行する。処理1:証明者アルゴリズムPは、任意にベクトルri,ti∈Kn及びei∈Kmを生成する。処理2:証明者アルゴリズムPは、riA←s-riを計算する。この計算は、秘密鍵sをベクトルriによりマスクする操作に相当する。さらに、証明者アルゴリズムPは、tiA←ritiを計算する。処理3:証明者アルゴリズムPは、eiA←Fri-eiを計算する。処理4:証明者アルゴリズムPは、c1,i←H1FbriA,tiei,riAを計算する。処理5:証明者アルゴリズムPは、c2,i←H2ti,eiを計算する。処理6:証明者アルゴリズムPは、c3,i←H3tiA,eiAを計算する。工程1続きi=1~Nについて上記の処理1~処理6を実行した後、証明者アルゴリズムPは、Cmt←Hc1,1,c2,1,c3,1,...,c1,N,c2,N,c3,Nを計算する。なお、上記のH...、H1...、H2...、H3...は、ハッシュ関数である。工程1で生成されたハッシュ値Cmtは、検証者アルゴリズムVに送られる。このように、メッセージc1,1,c2,1,c3,1,...,c1,N,c2,N,c3,Nをハッシュ値に変換してから検証者アルゴリズムVに送ることで、通信量を削減することが可能になる。工程2:ハッシュ値Cmtを受け取った検証者アルゴリズムVは、i=1~Nのそれぞれについて、3つの検証パターンのうち、どの検証パターンを利用するかを選択する。例えば、検証者アルゴリズムVは、i=1~Nのそれぞれについて、検証パターンの種類を表す3つの数値{0,1,2}の中から1つの数値を選択し、選択した数値を要求diに設定する。これらの要求d1,...,dNは、証明者アルゴリズムPに送られる。工程3:要求d1,...,dNを受け取った証明者アルゴリズムPは、受け取った要求d1,...,dNのそれぞれ応じて検証者アルゴリズムVに送る返答Rsp1,...,RspNを生成する。di=0の場合、証明者アルゴリズムPは、σi=ri,tiA,eiAを生成する。さらに、証明者アルゴリズムPは、Rspi=σi,c1,iを生成する。di=1の場合、証明者アルゴリズムPは、σi=riA,ti,eiを生成する。さらに、証明者アルゴリズムPは、Rspi=σi,c3,iを生成する。di=2の場合、証明者アルゴリズムPは、σi=riA,tiA,eiAを生成する。さらに、証明者アルゴリズムPは、Rspi=σi,c2,iを生成する。工程3で生成された返答Rsp1,...,RspNは、検証者アルゴリズムVに送られる。工程4:返答Rsp1,...,RspNを受け取った検証者アルゴリズムVは、受け取った返答Rsp1,...,RspNを利用して以下の処理1~処理3をi=1~Nについて実行する。但し、検証者アルゴリズムVは、di=0の場合に処理1を実行し、di=1の場合に処理2を実行し、di=2の場合に処理3を実行する。処理1:di=0の場合、検証者アルゴリズムVは、Rspiからri,tiA,eiA,c1,iを取り出す。次いで、検証者アルゴリズムVは、c2,i=H2ri-tiA,Fri-eiAを計算する。さらに、検証者アルゴリズムVは、c3,i=H3tiA,eiAを計算する。そして、検証者アルゴリズムVは、c1,i,c2,i,c3,iを保持する。処理2:di=1の場合、検証者アルゴリズムVは、RspiからriA,ti,ei,c3,iを取り出す。次いで、検証者アルゴリズムVは、c1,i=H1FbriA,tiei,riAを計算する。さらに、検証者アルゴリズムVは、c2,i=H2ti,eiを計算する。そして、検証者アルゴリズムVは、c1,i,c2,i,c3,iを保持する。処理3:di=2の場合、検証者アルゴリズムVは、RspiからriA,tiA,eiA,c2,iを取り出す。次いで、検証者アルゴリズムVは、c1,i=H1y-FriA-FbtiA,riA-eiA,riAを計算する。さらに、検証者アルゴリズムVは、c3,i=H3tiA,eiAを計算する。そして、検証者アルゴリズムVは、c1,i,c2,i,c3,iを保持する。処理1~処理3をi=1~Nについて実行した後、検証者アルゴリズムVは、Cmt=Hc1,1,c2,1,c3,1,...,c1,N,c2,N,c3,Nの等号が成り立つか否かを検証する。検証者アルゴリズムVは、この検証が成功した場合に認証成功を示す値1を出力し、検証に失敗した場合に認証失敗を示す値0を出力する。以上、効率的なアルゴリズムの並列化について説明した。なお、図11に示した並列化アルゴリズムには、メッセージをハッシュ値に変換してから送信する工夫を盛り込んだ。この工夫により、通信効率が向上する。[2-6:電子署名方式への変形]ここで、本手法に係る公開鍵認証方式を電子署名方式へと変形する方法を紹介する。なお、公開鍵認証方式のモデルにおける証明者を電子署名方式における署名者に対応させると、証明者のみが検証者を納得させられるという点において、電子署名方式のモデルと近似していることが容易に理解されよう。こうした考えに基づき、本手法に係る公開鍵認証方式を電子署名方式へと変形する方法について説明する。2-6-1:変形方法ここでは、上記の効率的なアルゴリズムの構成例3を電子署名方式のアルゴリズムに変形する方法を例に挙げて説明する。構成例3に係るアルゴリズムは、図12に示すように、おおまかに以下の4つの工程1~工程4で表現される。工程1は、ai=ri,ti,ei,riA,tiA,eiA,c1,i,c2,i,c3,iを生成する処理1と、Cmt←Hc1,1,c2,1,c3,1,...,c1,N,c2,N,c3,Nを計算する処理2とで構成される。工程1で証明者アルゴリズムPにより生成されたCmtは、検証者アルゴリズムVへと送られる。工程2は、d1,...,dNを選択する処理で構成される。工程2で検証者アルゴリズムVにより選択されたd1,...,dNは、証明者アルゴリズムPへと送られる。工程3は、d1,...,dN及びa1,...,aNを用いてRsp1,...,RspNを生成する処理で構成される。この処理をRspi←Selectdi,aiと表現する。工程3で証明者アルゴリズムPにより生成されたRsp1,...,RspNは、検証者アルゴリズムVへと送られる。工程4は、d1,...,dN及びRsp1,...,RspNを用いてc1,1,c2,1,c3,1,...,c1,N,c2,N,c3,Nを再生する処理1と、再生したc1,1,c2,2,c3,3,...,c1,N,c2,N,c3,Nを用いてCmt=Hc1,1,c2,1,c3,1,...,c1,N,c2,N,c3,Nを検証する処理2とで構成される。上記の工程1~工程4で表現される公開鍵認証方式のアルゴリズムは、図12に示すような署名生成アルゴリズムSig及び署名検証アルゴリズムVerに変形される。署名生成アルゴリズムSigまず、署名生成アルゴリズムSigの構成について述べる。署名生成アルゴリズムSigは、以下の処理1~処理5で構成される。処理1:署名生成アルゴリズムSigは、ai=ri,ti,ei,riA,tiA,eiA,c1,i,c2,i,c3,iを生成する。処理2:署名生成アルゴリズムSigは、Cmt←Hc1,1,c2,1,c3,1,...,c1,N,c2,N,c3,Nを計算する。処理3:署名生成アルゴリズムSigは、d1,...,dN←HM,Cmtを計算する。このMは、署名を付与する文書である。処理4:署名生成アルゴリズムSigは、Rspi←Selectdi,aiを計算する。処理5:署名生成アルゴリズムSigは、Cmt,Rsp1,...,RspNを署名に設定する。署名検証アルゴリズムVer次に、署名検証アルゴリズムVerの構成について述べる。署名検証アルゴリズムVerは、以下の処理1~処理3で構成される。処理1:署名検証アルゴリズムVerは、d1,...,dN←HM,Cmtを計算する。処理2:署名検証アルゴリズムVerは、d1,...,dN及びRsp1,...,RspNを用いてc1,1,c2,1,c3,1,...,c1,N,c2,N,c3,Nを生成する。処理3:署名検証アルゴリズムVerは、再生したc1,1,c2,1,c3,1,...,c1,N,c2,N,c3,Nを用いてCmt=Hc1,1,c2,1,c3,1,...,c1,N,c2,N,c3,Nを検証する。以上説明したように、公開鍵認証方式のモデルにおける証明者を電子署名方式における署名者に対応させることで、公開鍵認証方式のアルゴリズムを電子署名方式のアルゴリズムに変形することができる。2-6-2:電子署名アルゴリズムの効率化さて、図13に示した署名生成アルゴリズムSigの構成に注目すると、処理2及び処理3でハッシュ値の計算を行っていることに気づくであろう。また、署名検証アルゴリズムVerの構成に注目すると、処理1において、署名生成アルゴリズムSigの処理3と同じハッシュ値の計算を行っていることに気づくであろう。これらの処理に注目し、図13に示すように署名生成アルゴリズムSig及び署名検証アルゴリズムVerの構成を改良することで、さらに計算効率を向上させることができる。署名生成アルゴリズムSigまず、改良後の署名生成アルゴリズムSigの構成について述べる。署名生成アルゴリズムSigは、以下の処理1~処理4で構成される。処理1:署名生成アルゴリズムSigは、ai=ri,ti,ei,riA,tiA,eiA,c1,i,c2,i,c3,iを生成する。処理2:署名生成アルゴリズムSigは、d1,...,dN←HM,c1,1,c2,2,c3,3,...,c1,N,c2,N,c3,Nを計算する。このMは、署名を付与する文書である。処理3:署名生成アルゴリズムSigは、Rspi←Selectdi,aiを計算する。処理4:署名生成アルゴリズムSigは、d1,...,dN,Rsp1,...,RspNを署名に設定する。署名検証アルゴリズムVer次に、改良後の署名検証アルゴリズムVerの構成について述べる。署名検証アルゴリズムVerは、以下の処理1及び処理2で構成される。処理1:署名検証アルゴリズムVerは、d1,...,dN及びRsp1,...,RspNを用いてc1,1,c2,2,c3,3,...,c1,N,c2,N,c3,Nを生成する。処理2:署名検証アルゴリズムVerは、再生したc1,1,c2,1,c3,1,...,c1,N,c2,N,c3,Nを用いてd1,...,dN=HM,c1,1,c2,1,c3,1,...,c1,N,c2,N,c3,Nを検証する。上記のように署名生成アルゴリズムSig及び署名検証アルゴリズムVerの構成を改良することにより、各アルゴリズムにおいてハッシュ値の計算が1回ずつ削減される。その結果、さらに計算効率を向上させることができる。[2-7:多次多変数連立方程式の形式]これまで説明してきたように、本手法は、多次多変数連立方程式の求解問題に対する解答の困難性に安全性の根拠をおく方式である。また、本手法は、複雑な多次多変数連立方程式を利用可能な点に特徴がある。ここまでの説明においては多次多変数連立方程式の形式に特別な限定を行ってこなかったが、例えば、十分に困難性が補償されている暗号要素技術を表現に含む多次多変数連立方程式を利用することが好ましい。以下、本手法に適用可能な多次多変数連立方程式の具体例を紹介する。2-7-1:共通鍵ブロック暗号に関する形式AES、DES、KATANなどの共通鍵ブロック暗号技術は、よく解析され、安全性及び信頼性が高い要素技術である。これらの共通鍵ブロック暗号は、共通鍵ブロック暗号の鍵、平文、暗号文を変数とする多次多変数連立方程式により表現することができる。この多次多変数連立方程式において平文と暗号文を表現する変数に値を与えると、この多次多変数連立方程式は、鍵を表現する変数だけを変数に持つ方程式になる。このような共通鍵ブロック暗号を表現した多次多変数連立方程式の解を求めることは、平文と暗号文から共通鍵ブロック暗号の鍵を復元することに相当する。つまり、その共通鍵ブロック暗号の安全性が維持されている限りにおいて、その共通鍵ブロック暗号を表現した多次多変数連立方程式の求解困難性は担保される。そのため、ある共通鍵ブロック暗号方式を表現する多次多変数連立方程式を本手法に適用するならば、共通鍵ブロック暗号方式の安全性と同等の安全性を具備した公開鍵認証方式が実現される。但し、共通鍵ブロック暗号を、鍵、平文、暗号文を変数とする多次多変数連立方程式で表現した場合、多項式の次数が大きくなるため、連立方程式を表現するためのデータサイズが増大してしまう。そこで、鍵、平文、暗号文に加え、それぞれのラウンドにおける内部状態を表現するための変数を導入する。この変数を導入すれば、共通鍵ブロック暗号を表現する多次多変数連立方程式の次数を小さくすることができる。例えば、平文と暗号文を表現する変数に適当な値を代入し、鍵と内部状態を表現するための変数に関する連立方程式を導入する。このような方法を採用することにより、変数の数は増加するが、次数が下がるため、連立方程式の表現はコンパクトになる。2-7-2:ハッシュ関数に関する形式同様に、SHA-1、SHA-256などのハッシュ関数に関する多次多変数連立方程式を本手法に適用することも可能である。これらのハッシュ関数は、ハッシュ関数の入力となるメッセージと出力となるハッシュ値を変数とする多次多変数連立方程式で表現することができる。この多次多変数連立方程式において、ハッシュ値を表現する変数に適当な値を与えると、対応する入力を表現した変数に関する多次多変数連立方程式が得られる。このような多次多変数連立方程式の解を求めることは、ハッシュ値から、元になるメッセージの値を復元することに相当する。つまり、そのハッシュ関数の安全性一方向性が維持されている限りにおいて、そのハッシュ関数を表現した多次多変数連立方程式の求解問題に対する解答の困難性は担保される。そのため、あるハッシュ関数を表現した多次多変数連立方程式を本手法に適用すれば、ハッシュ関数の安全性に基づく公開鍵認証方式が実現される。但し、入力メッセージ及びハッシュ値を変数とする多次多変数連立方程式でハッシュ関数を表現した場合には多項式の次数が大きくなるため、連立方程式を表現するためのデータサイズが増大してしまう。そこで、入力メッセージとハッシュ値に加え、内部状態を表現するための変数を導入する。この変数を導入すれば、ハッシュ関数を表現する多次多変数連立方程式の次数を小さくすることができる。例えば、ハッシュ値を表現する変数に適用な値を代入し、入力メッセージ及び内部状態を表現するための変数に関する連立方程式を導入する。このような方法を採用することにより、変数の数は増加するが、次数が下がるため、連立方程式の表現はコンパクトになる。2-7-3:ストリーム暗号に関する形式同様に、Triviumなどのストリーム暗号に関する多次多変数連立方程式を本手法に適用することも可能である。これらのストリーム暗号は、ストリーム暗号の初期の内部状態を表現する変数及び出力されるストリームを表現する変数に関する多次多変数連立方程式で表現することが可能である。この場合、出力ストリームを表現する変数に適当な値を与えると、対応する初期の内部状態を表現するための変数に関する多次多変数連立方程式が得られる。このような多次多変数連立方程式の解を求めることは、出力されたストリームの値から、元になった初期の内部状態を表現する変数を復元することに相当する。つまり、そのストリーム暗号の安全性が確保されている限りにおいて、そのストリーム暗号を表現した多次多変数連立方程式の求解問題に対する解答の困難性は担保されている。そのため、あるストリーム暗号を表現した多次多変数連立方程式を本手法に適用すれば、ストリーム暗号の安全性に基づく公開鍵認証方式が実現される。但し、初期の内部状態と出力ストリームを変数とする多次多変数連立方程式でストリーム暗号を表現した場合、多項式の次数が大きくなり、連立方程式を表現するサイズが増大してしまう。そこで、初期の内部状態と出力ストリームに加え、それぞれのラウンドにおける内部状態を表現するための変数を導入する。この変数を導入すれば、ストリーム暗号を表現するための多次多変数連立方程式の次数を小さくすることが可能になる。例えば、出力ストリームを表現する変数に適当な値を代入し、初期の内部状態とラウンドにおける内部状態を表現するための変数に関する連立方程式を導入する。このような方法を採用することにより、変数の数は増加するが、次数が下がるため、連立方程式の表現はコンパクトになる。以上、本手法に適用可能な多次多変数連立方程式の具体例について説明した。[2-8:直列並列ハイブリッドアルゴリズム]偽証が成功する確率を無視できる程度にまで小さくするために、対話プロトコルを複数回実行する必要性については既に説明した通りである。また、対話プロトコルを複数回実行する方法として、直列的な方法と並列的な方法とを紹介した。特に、並列的な方法については、具体的な並列化アルゴリズムを示して説明した。ここでは、直列的な方法と並列的な方法とを組み合わせたハイブリッドタイプのアルゴリズムを紹介する。ハイブリッド構成1図14を参照しながら、ハイブリッドタイプのアルゴリズム以下、並直列アルゴリズムについて説明する。図14には、本手法に係る基本構成、この基本構成を直列化した直列化アルゴリズム、並列化した並列化アルゴリズム、及び並直列アルゴリズムを示した。基本構成では、1パス目にメッセージc1,c2,c3が証明者から検証者へと送られる。2パス目では、検証者から証明者へと要求dが送られる。3パス目では、証明者から検証者へと返答σが送られる。上記の基本構成を並列化した場合、1パス目では、N回分のメッセージc1,1,c2,1,c3,1,...,c1,N,c2,N,c3,Nが証明者から検証者へと送られる。2パス目では、検証者から証明者へとN回分の要求d1,...,dNが送られる。3パス目では、証明者から検証者へとN回分の返答σ1,...,σNが送られる。本手法に係る並列化アルゴリズムは、受動的攻撃に対する安全性が保証される。また、対話の回数が3回で済む。さらに、1パス目で送信されるN回分のメッセージを1つのハッシュ値に纏めることにより、通信効率を向上させることができる。一方、上記の基本構成を直列化した場合、1パス目では、1回分のメッセージc1,1,c2,1,c3,1が証明者から検証者へと送られる。2パス目では、検証者から証明者へと1回分の要求d1が送られる。3パス目では、証明者から検証者へと1回分の返答σ1が送られる。4パス目では、1回分のメッセージc1,2,c2,2,c3,2が証明者から検証者へと送られる。5パス目では、検証者から証明者へと1回分の要求d2が送られる。6パス目では、証明者から検証者へと1回分の返答σ2が送られる。同様にして、証明者から検証者へと返答σNが送られるまで対話が繰り返し実行される。直列化アルゴリズムは、能動的攻撃に対する安全性が保証される。また、偽証確率が確実に削減されることを証明することが可能である。さて、並直列アルゴリズムは、並列化アルゴリズムの性質と直列化アルゴリズムの性質とを併せ持つアルゴリズムである。図14に示した並直列アルゴリズムでは、1パス目で、N回分のメッセージc1,1,c2,1,c3,1,...,c1,N,c2,N,c3,Nが証明者から検証者へと送られる。2パス目では、検証者から証明者へと1回分の要求d1が送られる。3パス目では、証明者から検証者へと1回分の返答σ1が送られる。その後、証明者と検証者との間で要求d2,...,dN及び返答σ2,...,σNのやり取りが行われる。本手法に基づく並直列アルゴリズムの場合、受動的攻撃に対する安全性が保証される。また、対話の回数が2N1回で済む。さらに、1パス目で送信されるN回分のメッセージを1つのハッシュ値に纏めることにより、通信効率を向上させることができる。ハイブリッド構成2図15を参照しながら、他のハイブリッドタイプのアルゴリズム以下、直並列アルゴリズムについて説明する。図15には、本手法に係る基本構成、この基本構成を直列化した直列化アルゴリズム、並列化した並列化アルゴリズム、及び直並列アルゴリズムを示した。なお、基本構成、直列化アルゴリズム、並列化アルゴリズムの構成及び性質については、上記の通りである。図15に示した直並列アルゴリズムは、並列化アルゴリズムの性質と直列化アルゴリズムの性質とを併せ持つアルゴリズムである。図15に示した直並列アルゴリズムでは、1パス目で、1回分のメッセージc1,1,c2,1,c3,1が証明者から検証者へと送られる。2パス目では、検証者から証明者へと1回分の要求d1が送られる。その後、証明者と検証者との間でメッセージc1,2,c2,2,c3,2,...,c1,N,c2,N,c3,N及び要求d2,...,dNのやり取りが行われる。要求dNが検証者から証明者へと送られた後、証明者から検証者へとN回分の返答σ1,...,σNが送られる。本手法に基づく直並列アルゴリズムの場合、能動的攻撃に対する安全性が保証される。また、対話の回数が2N1回で済む。以上、本手法に基づくハイブリッドタイプのアルゴリズムについて説明した。以上、本技術の第1実施形態について説明した。<3:第2実施形態>次に、本技術の第2実施形態について説明する。これまで3パスの公開鍵認証方式について説明してきた。本実施形態では、5パスの公開鍵認証方式以下、本手法について説明する。本手法は、検証者の検証パターンを2q通りにすることにより、公開鍵認証方式の健全性を確保する方式である。なお、上記の第1実施形態に係る3パスの公開鍵認証方式は、対話プロトコル1回当たりの偽証確率が2/3であったが、本手法では、後述するように対話プロトコル1回当たりの偽証確率は1/21/qとなる。但し、qは、利用する環の位数である。従って、環の位数が十分に大きい場合、図39に示すように、本手法の方が1回当たりの偽証確率を低減することが可能になり、少ない対話プロトコルの実行回数で、偽証確率を十分に小さくすることができる。5パスの公開鍵認証方式に係る対話プロトコルは、3パスの公開鍵認証方式に係る対話プロトコルよりも効率が低いように思われるかもしれない。しかし、5パスの公開鍵認証方式においては、環の位数を十分に大きくとった場合、対話プロトコル1回当たりの偽証確率が1/2に近くなるため、同じセキュリティレベルを達成するために必要な対話プロトコルの実行回数が少なくて済む。例えば、偽証確率を1/2n以下にしたい場合、3パスの公開鍵認証方式においては、n/log3-1=1.701n回以上、対話プロトコルを実行する必要がある。一方、5パスの公開鍵認証方式においては、n/1-log11/q回以上、対話プロトコルを実行する必要がある。図39に示すように、例えば、q=24にすれば、同じセキュリティレベルを実現するのに必要な通信量は、3パスの公開鍵認証方式に比べ、5パスの公開鍵認証方式の方が少なくなる。[3-1:公開鍵認証方式のアルゴリズム]以下、図16を参照しながら、5パスの公開鍵認証方式本手法に係るアルゴリズム構成について説明する。図16は、本手法に係るアルゴリズムの構成について説明するための説明図である。鍵生成アルゴリズムGen鍵生成アルゴリズムGenは、環K上で定義されるm本の多変数多次多項式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次に、図16を参照しながら、対話プロトコルの中で証明者アルゴリズムP及び検証者アルゴリズムVが実行する処理について説明する。この対話プロトコルの中で、証明者は、秘密鍵sの情報を検証者に一切漏らさずに、自身がy=Fsを満たすsを知っていることを検証者に示す。一方、検証者は、証明者がy=Fsを満たすsを知っているか否かを検証する。なお、公開鍵pkは、検証者に公開されているものとする。また、秘密鍵sは、証明者により秘密に管理されているものとする。以下、図16に示したフローチャートに沿って説明を進める。工程1:まず、証明者アルゴリズムPは、任意に数wを選択する。次いで、証明者アルゴリズムPは、擬似乱数生成器Gに数wを適用してベクトルr∈Knと、n変数多項式の組FAx=f1Ax,...,fmAxを生成する。つまり、証明者アルゴリズムPは、r,FA←Gwを計算する。次いで、証明者アルゴリズムPは、z←s-rを計算する。この計算は、秘密鍵sをベクトルrによりマスクする操作に相当する。工程1続き:次いで、証明者アルゴリズムPは、FAz及びzのハッシュ値c1を生成する。つまり、証明者アルゴリズムPは、c1←H1FAz,zを計算する。また、証明者アルゴリズムPは、数wのハッシュ値c2を生成する。つまり、証明者アルゴリズムPは、c2←H2wを計算する。なお、上記のH1...、H2...は、ハッシュ関数である。工程1で生成されたメッセージc1,c2は、検証者に送られる。このとき、sに関する情報、rに関する情報、zに関する情報が検証者に一切漏れない点に注意されたい。工程2:検証者アルゴリズムVは、q通り存在する環Kの元からランダムに1つの数αを選択し、選択した数αを証明者アルゴリズムPに送る。工程3:数αを受け取った証明者アルゴリズムPは、FBx←αFxrFAxを計算する。この計算は、xに関して多変数多項式Fxrを多変数多項式FAxによりマスクする操作に相当する。工程3で生成された多変数多項式FBは、検証者アルゴリズムVに送られる。このとき、d=0の場合にはzに関する情報が検証者に一切漏れておらず、d=1の場合にはrに関する情報が検証者に一切漏れない点に注意されたい。工程4:多変数多項式FBを受け取った検証者アルゴリズムVは、2つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。例えば、検証者アルゴリズムVは、検証パターンの種類を表す2つの数値{0,1}の中から1つの数値を選択し、選択した数値を要求dに設定する。この要求dは証明者アルゴリズムPに送られる。工程5:要求dを受け取った証明者アルゴリズムPは、受け取った要求dに応じて検証者アルゴリズムVに送り返す返答σを生成する。d=0の場合、証明者アルゴリズムPは、返答σ=wを生成する。d=1の場合、証明者アルゴリズムPは、返答σ=zを生成する。工程5で生成された返答σは、検証者アルゴリズムVに送られる。工程6:返答σを受け取った検証者アルゴリズムVは、受け取った返答σを利用して以下の検証処理を実行する。d=0の場合、検証者アルゴリズムVは、rA,FC←Gσを計算する。そして、検証者アルゴリズムVは、c2=H2σの等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、FBx=αFxrAFCxの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。d=1の場合、検証者アルゴリズムVは、zA←σを計算する。そして、検証者アルゴリズムVは、c1=H1FCzA-αy,zAの等号が成り立つか否かを検証する。検証者アルゴリズムVは、この検証が成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、本手法に係る各アルゴリズムの構成について説明した。本手法における健全性について本手法の健全性は、証明者アルゴリズムPがc1,c2、及び、検証者アルゴリズムVが選択する2通りのα1,α2について、要求d=0及び1に正しく回答した場合に、その回答内容から下記の式15~式17を満たすF1D、F2D、FC、rA、zAを計算できるということから保証されている。本手法の健全性が保証されることにより、多次多変数連立方程式の求解問題を解かない限りにおいて1/21/qより高い確率で偽証することは不可能であることが保証される。つまり、検証者の要求d=0及び1の全てに正しく回答するためには、偽証者が上記の式15~式17を満たすF1D、F2D、FC、rA、zAを計算できる必要がある。言い換えると、偽証者はFs=yを満たすsを計算できる必要がある。従って、多次多変数連立方程式の求解問題を解かない限り、偽証者は、1/21/qより高い確率で偽証を成功させることができないのである。なお、上記の対話プロトコルを十分に多くの回数実行することにより、偽証の成功確率を無視できるほど小さくすることができる。変形例上記の鍵生成アルゴリズムGenは、y←Fsを計算し、公開鍵をF,yに設定している。しかし、鍵生成アルゴリズムGenは、y1,...,ym←Fsとして、f1x,...,fmx←f1x-y1,...,fmx-ymを計算し、公開鍵をf1,...,fmに設定するように構成されていてもよい。このように変形すると、証明者アルゴリズムPと検証者アルゴリズムVとの間でy=0として対話プロトコルを実行することが可能になる。また、証明者アルゴリズムPは、FBzのハッシュ値と、zのハッシュ値とを別々に計算し、それぞれをメッセージとして検証者に送るようにしてもよい。また、上記の証明者アルゴリズムPは、数wに擬似乱数生成器G1を適用してベクトルr及び数wAを生成していた。さらに、上記の証明者アルゴリズムPは、数wAを擬似乱数生成器G2に適用して多変数多項式FAxを生成していた。しかし、証明者アルゴリズムPは、G1を恒等写像とし、最初からw=r,FAを算出するように構成されていてもよい。この場合、数wをG1に適用する必要はない。G2についても同様である。以上、本手法の変形例について説明した。[3-2:拡張アルゴリズム]次に、図17を参照しながら、本手法を拡張した公開鍵認証方式以下、拡張手法のアルゴリズムについて説明する。図17は、拡張手法に基づく対話プロトコルの流れについて説明するための説明図である。ここで説明する拡張手法は、3パス目に送信する多変数多項式FBを1つのハッシュ値c3に変換して検証者に送る方式である。このように拡張することで、対話プロトコルの中で表現サイズの大きい多変数多項式FBを検証者アルゴリズムVに送る際の通信量を半減することが可能になり、やり取りすべき平均的なデータサイズを削減することができる。以下、拡張方式における各アルゴリズムの構成について詳細に説明する。鍵生成アルゴリズムGen鍵生成アルゴリズムGenは、環K上で定義されるm本の多変数多次多項式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次に、図17を参照しながら、対話プロトコルの中で証明者アルゴリズムP及び検証者アルゴリズムVが実行する処理について説明する。この対話プロトコルの中で、証明者は、秘密鍵sの情報を検証者に一切漏らさずに、自身がy=Fsを満たすsを知っていることを検証者に示す。一方、検証者は、証明者がy=Fsを満たすsを知っているか否かを検証する。なお、公開鍵pkは、検証者に公開されているものとする。また、秘密鍵sは、証明者により秘密に管理されているものとする。以下、図17に示したフローチャートに沿って説明を進める。工程1:まず、証明者アルゴリズムPは、任意に数wを選択する。次いで、証明者アルゴリズムPは、擬似乱数生成器Gに数wを適用してベクトルr∈Kn及び多変数多項式FAxを生成する。つまり、証明者アルゴリズムPは、r,FA←Gwを計算する。次いで、証明者アルゴリズムPは、z←s-rを計算する。この計算は、秘密鍵sをベクトルrによりマスクする操作に相当する。工程1続き:次いで、証明者アルゴリズムPは、FAz及びzのハッシュ値c1を生成する。つまり、証明者アルゴリズムPは、c1←H1FAz,zを計算する。また、証明者アルゴリズムPは、数wのハッシュ値c2を生成する。つまり、証明者アルゴリズムPは、c2←H2wを計算する。なお、上記のH1...、H2...は、ハッシュ関数である。工程1で生成されたメッセージc1,c2は、検証者アルゴリズムVに送られる。工程2:メッセージc1,c2を受け取った検証者アルゴリズムVは、q通り存在する環Kの元からランダムに1つの数αを選択し、選択した数αを証明者アルゴリズムPに送る。工程3:数αを受け取った証明者アルゴリズムPは、FBx←αFxrFAxを計算する。この計算は、xについて多変数多項式Fxrを多変数多項式FAxによりマスクする操作に相当する。さらに、証明者アルゴリズムPは、多変数多項式の組FBのハッシュ値c3を生成する。つまり、証明者アルゴリズムPは、c3←H3FBxを計算する。なお、上記のH3...は、ハッシュ関数である。工程3で生成されたメッセージc3は、検証者に送られる。工程4:メッセージc3を受け取った検証者アルゴリズムVは、2つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。例えば、検証者アルゴリズムVは、検証パターンの種類を表す2つの数値{0,1}の中から1つの数値を選択し、選択した数値を要求dに設定する。この要求dは証明者アルゴリズムPに送られる。工程5:要求dを受け取った証明者アルゴリズムPは、受け取った要求dに応じて検証者アルゴリズムVに送り返す返答σを生成する。d=0の場合、証明者アルゴリズムPは、返答σ=wを生成する。d=1の場合、証明者アルゴリズムPは、返答σ=z,FBを生成する。工程5で生成された返答σは、検証者アルゴリズムVに送られる。工程6:返答σを受け取った検証者アルゴリズムVは、受け取った返答σを利用して以下の検証処理を実行する。d=0の場合、検証者アルゴリズムVは、rA,FC←Gσを計算する。そして、検証者アルゴリズムVは、c2=H2σの等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、c3=H3αFxrAFCxの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。d=1の場合、検証者アルゴリズムVは、zA,FC←σを計算する。そして、検証者アルゴリズムVは、c1=H1FCzA-αy,zAの等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、c2=H2FCxの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、拡張方式の対話プロトコルの中で各アルゴリズムが実行する処理について説明した。このように拡張することで、対話プロトコルの中で表現サイズの大きい多変数多項式FBを検証者アルゴリズムVに送る際の通信量を半減することが可能になり、やり取りすべき平均的なデータサイズを削減することができる。[3-3:並列化アルゴリズム]さて、先に述べた通り、本手法又は拡張手法に係る対話プロトコルを適用すれば、偽証が成功する確率を1/21/q以下に抑制することができる。従って、この対話プロトコルを2回実行すれば、偽証が成功する確率を1/21/q2以下に抑制することができる。さらに、この対話プロトコルをN回実行すると、偽証が成功する確率は1/21/qNとなり、Nを十分に大きい数例えば、N=80にすれば、偽証が成功する確率は無視できる程度に小さくなる。対話プロトコルを複数回実行する方法としては、例えば、メッセージ、要求、返答のやり取りを逐次的に複数回繰り返す直列的な方法と、1回分のやり取りで複数回分のメッセージ、要求、返答のやり取りを行う並列的な方法とが考えられる。ここでは、本手法に係る対話プロトコルを並列的な方法に係る対話プロトコル以下、並列化アルゴリズムに拡張する方法について説明する。例えば、並列化アルゴリズムは図18のようになる。以下、図18を参照しながら、並列化アルゴリズムの内容について説明する。鍵生成アルゴリズムGen鍵生成アルゴリズムGenは、環K上で定義されるm本の多変数多次多項式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次に、図18を参照しながら、対話プロトコルの中で証明者アルゴリズムPが実行する処理及び検証者アルゴリズムVが実行する処理について説明する。上記の対話プロトコルの中で、証明者は、秘密鍵sの情報を検証者に一切漏らさずに、自身がy=Fsを満たすsを知っていることを検証者に示す。一方、検証者は、証明者がy=Fsを満たすsを知っているか否かを検証する。なお、公開鍵pkは、検証者に公開されているものとする。また、秘密鍵sは、証明者により秘密に管理されているものとする。以下、図18に示したフローチャートに沿って説明を進める。工程1:まず、証明者アルゴリズムPは、i=1~Nについて、以下の処理1~処理5を実行する。処理1:証明者アルゴリズムPは、任意に数wiを選択する。処理2:証明者アルゴリズムPは、擬似乱数生成器Gに数wiを適用してベクトルri∈Kn及び多項式の組FiAxを生成する。つまり、証明者アルゴリズムPは、ri,FiA←Gwiを計算する。処理3:証明者アルゴリズムPは、zi←s-riを計算する。この計算は、秘密鍵sをベクトルriによりマスクする操作に相当する。処理4:証明者アルゴリズムPは、FiAzi及びziのハッシュ値c1,iを生成する。つまり、証明者アルゴリズムPは、c1,i←H1FiAzi,ziを計算する。処理5:証明者アルゴリズムPは、数wiAのハッシュ値c2,iを生成する。つまり、証明者アルゴリズムPは、c2,i←H2wiAを計算する。i=1~Nについて、上記の処理1~処理5が実行された後、工程1で生成されたメッセージc1,i,c2,ii=1~Nは、検証者アルゴリズムVに送られる。工程2:メッセージc1,i,c2,ii=1~Nを受け取った検証者アルゴリズムVは、q通り存在する環Kの元からランダムにN個の数α1,...,αNを選択する。そして、検証者アルゴリズムVは、選択した数α1,...,αNを証明者アルゴリズムPに送る。工程3:数α1,...,αNを受け取った証明者アルゴリズムPは、i=1~Nについて、FiBx←αiFxriFiAxを計算する。この計算は、xに関して多変数多項式Fxriを多変数多項式FiAxによりマスクする操作に相当する。そして、証明者アルゴリズムPは、多変数多項式F1B,...,FNBを検証者アルゴリズムVに送る。工程4:多変数多項式F1B,...,FNBを受け取った検証者アルゴリズムVは、i=1~Nのそれぞれについて、2つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。例えば、検証者アルゴリズムVは、i=1~Nのそれぞれについて、検証パターンの種類を表す2つの数値{0,1}の中から1つの数値を選択し、選択した数値を要求diに設定する。この要求diは証明者アルゴリズムPに送られる。工程5:要求dii=1~Nを受け取った証明者アルゴリズムPは、受け取った要求diに応じて検証者アルゴリズムVに送り返す返答σiを生成する。ここで、証明者アルゴリズムPは、i=1~Nについて、以下の処理1及び処理2を実行する。処理1:di=0の場合、証明者アルゴリズムPは、返答σi=wiを生成する。処理2:di=1の場合、証明者アルゴリズムPは、返答σi=ziを生成する。上記の処理1及び処理2の処理が実行された後、返答σii=1~Nは、検証者アルゴリズムVに送られる。工程6:返答σii=1~Nを受け取った検証者アルゴリズムVは、受け取った返答σii=1~Nを利用して以下の検証処理を実行する。なお、以下の処理は、i=1~Nについて実行される。di=0の場合、検証者アルゴリズムVは、riA,FiC←Gσiを計算する。そして、検証者アルゴリズムVは、c2,i=H2σiの等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、FiBx=αiFxriAFiCxの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。di=1の場合、検証者アルゴリズムVは、ziA←σiを計算する。そして、検証者アルゴリズムVは、c1,i=H1FiCziA-αiy,ziの等号が成り立つか否かを検証する。検証者アルゴリズムVは、この検証が成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、本手法の対話プロトコルを並列的に実行する方法について説明した。上記のように、本手法の対話プロトコルを繰り返し実行することにより、偽証が成功する確率を無視できる程度まで低減させることが可能になる。なお、拡張方式についても同様にして並列化することが可能である。変形例上記の工程1の後、メッセージc1,1,c1,2,...,cN,1,cN,2を検証者アルゴリズムVに送信する代わりに、メッセージをハッシュ値Hc1,1,c1,2,...,cN,1,cN,2にまとめて送信するように対話プロトコルの構成を変形してもよい。この変形を適用すると、1パス目で送るメッセージが1つのハッシュ値だけとなり、大幅に通信量を削減することが可能になる。但し、証明者アルゴリズムPから送られる情報を用いても検証者アルゴリズムVにより復元できないメッセージが存在するため、返答が送られる際に、そのメッセージも送られるようにする必要がある。なお、この構成によると、N回の並列的繰り返し構成の場合、送るべき情報の数をN-1個削減することが可能になる。拡張方式に係る並列化アルゴリズムについてここで、図19を参照しながら、拡張方式に係る並列化アルゴリズムの構成について説明する。なお、鍵生成アルゴリズムGenの構成については本手法に係る並列化アルゴリズムと同じであるため、詳細な説明を省略する。工程1:まず、証明者アルゴリズムPは、i=1~Nについて、以下の処理1~処理5を実行する。処理1:証明者アルゴリズムPは、任意に数wiを選択する。処理2:証明者アルゴリズムPは、擬似乱数生成器Gに数wiを適用してベクトルri∈Kn及び多変数多項式の組FiAxを生成する。つまり、証明者アルゴリズムPは、ri,FiA←Gwiを計算する。処理3:証明者アルゴリズムPは、zi←s-riを計算する。この計算は、秘密鍵sをベクトルriによりマスクする操作に相当する。処理4:証明者アルゴリズムPは、FiAzi及びziのハッシュ値c1,iを生成する。つまり、証明者アルゴリズムPは、c1,i←H1FiAzi,ziを計算する。処理5:証明者アルゴリズムPは、数wiのハッシュ値c2,iを生成する。つまり、証明者アルゴリズムPは、c2,i←H2wiを計算する。i=1~Nについて、上記の処理1~処理5が実行された後、工程1で生成されたメッセージc1,i,c2,ii=1~Nは、検証者アルゴリズムVに送られる。工程2:メッセージc1,i,c2,ii=1~Nを受け取った検証者アルゴリズムVは、q通り存在する環Kの元からランダムにN個の数α1,...,αNを選択する。そして、検証者アルゴリズムVは、選択した数α1,...,αNを証明者に送る。工程3:数α1,...,αNを受け取った証明者アルゴリズムPは、i=1~Nについて、FiBx←αiFxriFiAxを計算する。この計算は、xに関して多変数多項式Fxriを多変数多項式FiAxによりマスクする操作に相当する。次いで、証明者アルゴリズムPは、多変数多項式F1B,...,FNBのハッシュ値c3を生成する。つまり、証明者アルゴリズムPは、c3←H3F1B,...,FNBを計算する。なお、上記のH3...は、ハッシュ関数である。工程3で生成されたメッセージc3は、検証者アルゴリズムVに送られる。工程4:メッセージc3を受け取った検証者アルゴリズムVは、i=1~Nのそれぞれについて、2つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。例えば、検証者アルゴリズムVは、i=1~Nのそれぞれについて、検証パターンの種類を表す2つの数値{0,1}の中から1つの数値を選択し、選択した数値を要求diに設定する。この要求diは証明者アルゴリズムPに送られる。工程5:要求dii=1~Nを受け取った証明者アルゴリズムPは、受け取った要求diに応じて検証者アルゴリズムVに送り返す返答σiを生成する。ここで、証明者アルゴリズムPは、i=1~Nについて、以下の処理1及び処理2を実行する。処理1:di=0の場合、証明者アルゴリズムPは、返答σi=wiを生成する。処理2:di=1の場合、証明者アルゴリズムPは、返答σi=zi,FiBを生成する。上記の処理1及び処理2の処理が実行された後、返答σii=1~Nは、検証者アルゴリズムVに送られる。工程6:返答σii=1~Nを受け取った検証者アルゴリズムVは、受け取った返答σii=1~Nを利用して以下の検証処理を実行する。なお、以下の処理は、i=1~Nについて実行される。di=0の場合、検証者アルゴリズムVは、riA,FiC←Gσiを計算する。さらに、検証者アルゴリズムVは、FiD←αiFxriAFiCxを計算する。そして、検証者アルゴリズムVは、c2,i=H2σiの等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、c3=H3F1D,...,FNDの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。di=1の場合、検証者アルゴリズムVは、ziA,FiD←σiとする。そして、検証者アルゴリズムVは、c1,i=H1FiDziA-αiy,ziAの等号が成り立つか否かを検証する。さらに、検証者アルゴリズムVは、c3=H3F1D,...,FNDの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、拡張方式に係る並列化アルゴリズムの構成について説明した。好適なパラメータの設定方法についてさて、上記の第1実施形態に係る対話プロトコルと同様、本実施形態に係る対話プロトコルは、受動的攻撃に対する安全性レベルを保証している。しかし、この対話プロトコルを並列的に繰り返し実行する上記の方法を適用した場合、能動的攻撃に対する安全性レベルが確実に保証されているということを証明するには、以下で説明するような条件が必要になる。上記の対話プロトコルは、1組の鍵ペア公開鍵y、秘密鍵sを用い、秘密鍵sの情報を検証者に一切漏らさず、証明者がy=Fsとなるsを知っていることを対話を通じて証明者が検証者に証明するというものである。そのため、検証で受理される対話を行った場合、対話の際に証明者がsを用いたという情報を検証者に知られてしまう可能性が否定できない。また、多変数多項式Fには衝突困難性が保証されてない。そのため、上記の対話プロトコルを並列的に繰り返し実行する場合、能動的攻撃に対する安全性が確実に保証されているということを無条件で証明することは難しい。そこで、本件発明者は、検証で受理される対話を行った場合においても、対話の際に証明者がsを用いたという情報を検証者に知られないようにする方法について検討した。そして、本件発明者は、上記の対話プロトコルを並列的に繰り返し実行する場合でも、能動的攻撃に対する安全性が確実に保証されていることを証明できるようにする方法を考案した。この方法は、公開鍵として用いるn変数多次多項式f1,...,fmの本数mを変数の数nよりも十分に小さな値に設定するという設定条件を課す方法である。例えば、2m-n≪1となるようにm及びnが設定される例えば、n=160、m=80の場合2-80≪1である。。上記のような多次多変数方程式の求解問題に対する解答の困難性に安全性の根拠をおく方式において、秘密鍵s1と、それに対応する公開鍵pkとが与えられても、その公開鍵pkに対応する別の秘密鍵s2を生成することは難しい。そのため、公開鍵pkに対する秘密鍵sが2つ以上存在することを保証すれば、検証で受理される対話を行った場合においても、対話の際に証明者がsを用いたという情報を検証者に知られないようにすることが可能になる。つまり、この保証が可能になれば、対話プロトコルを並列的に繰り返し実行する場合においても、能動的攻撃に対する安全性を保証することが可能になる。図40を参照しながら、m本のn変数多次多項式で構成される関数F:Kn→Kmについて考えると但し、n>m、2つ目の原像を持たない定義域の要素数は、最大で|K|m-1個しか存在しない。そのため、|K|m-nを十分に小さくすると、2つ目の原像を持たない定義域の要素が選択される確率を無視できる程度まで小さくすることができる。つまり、n変数多次多項式f1,...,fmの数mがその変数の数nよりも十分に小さな値に設定されていれば、公開鍵pkに対して2つ以上の秘密鍵sが存在することを保証できる。その結果、検証で受理される対話を行った場合においても、対話の際に証明者がsを用いたという情報を検証者に知られないようにすることが可能になり、対話プロトコルを並列的に繰り返し実行する場合においても、能動的攻撃に対する安全性が保証される。以上説明したように、n変数多次多項式f1,...,fmの数mがその変数の数nよりも小さな値n>m;好ましくは2m-n≪1に設定する設定条件を課すことで、対話プロトコルを並列的に繰り返し実行する場合の安全性を保証することが可能になる。[3-4:具体例2次多項式を利用する場合]次に、図20を参照しながら、多変数多項式Fとしてn変数2次多項式を利用する場合について説明する。図20は、本手法の一具体例について説明するための説明図である。鍵生成アルゴリズムGen鍵生成アルゴリズムGenは、環K上で定義されるm本の2次多項式f1x1,...,xn,...,fmx1,...,xn、及びベクトルs=s1,...,sn∈Knを生成する。次に、鍵生成アルゴリズムGenは、y=y1,...,ym←f1s,...,fmsを計算する。そして、鍵生成アルゴリズムGenは、f1,...,fm,yを公開鍵pkに設定し、sを秘密鍵に設定する。なお、以下では、ベクトルx1,...,xnをxと表記し、2次多項式の組f1x,...,fmxをFxと表記する。証明者アルゴリズムP、検証者アルゴリズムV次に、図20を参照しながら、対話プロトコルの中で証明者アルゴリズムP及び検証者アルゴリズムVにより実行される処理について説明する。工程1:まず、証明者アルゴリズムPは、任意に数wを選択する。次いで、証明者アルゴリズムPは、擬似乱数生成器Gに数wを適用してベクトルr∈Kn、及び多変数多項式の組FAx=f1Ax,...,fmAxを生成する。つまり、証明者アルゴリズムPは、r,FA←Gwを計算する。次いで、証明者アルゴリズムPは、z←s-rを計算する。この計算は、秘密鍵sをベクトルrによりマスクする操作に相当する。但し、2次多項式fiAxは、下記の式18のように表現される。工程1続き:次いで、証明者アルゴリズムPは、FAz及びzのハッシュ値c1を生成する。つまり、証明者アルゴリズムPは、c1←H1FAz,zを計算する。また、証明者アルゴリズムPは、数wのハッシュ値c2を生成する。つまり、証明者アルゴリズムPは、c2←H2wを計算する。なお、上記のH1...、H2...は、ハッシュ関数である。工程1で生成されたメッセージc1,c2は、検証者アルゴリズムVに送られる。工程2:メッセージc1,c2を受け取った検証者アルゴリズムVは、q通り存在する環Kの元からランダムに1つの数αを選択し、選択した数αを証明者アルゴリズムPに送る。工程3:数αを受け取った証明者アルゴリズムPは、FBx←αFxrFAxを計算する。この計算は、xに関して多変数多項式Fxrを多変数多項式FAxによりマスクする操作に相当する。工程3で生成された多変数多項式FBは、検証者アルゴリズムVに送られる。工程4:多変数多項式FBを受け取った検証者アルゴリズムVは、2つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。例えば、検証者アルゴリズムVは、検証パターンの種類を表す2つの数値{0,1}の中から1つの数値を選択し、選択した数値を要求dに設定する。この要求dは証明者アルゴリズムPに送られる。工程5:要求dを受け取った証明者アルゴリズムPは、受け取った要求dに応じて検証者アルゴリズムVに送り返す返答σを生成する。d=0の場合、証明者アルゴリズムPは、返答σ=wを生成する。d=1の場合、証明者アルゴリズムPは、返答σ=zを生成する。工程5で生成された返答σは、検証者アルゴリズムVに送られる。工程6:返答σを受け取った検証者アルゴリズムVは、受け取った返答σを利用して以下の検証処理を実行する。d=0の場合、検証者アルゴリズムVは、rA,FC←Gσを計算する。そして、検証者アルゴリズムVは、c2=H2σの等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、FBx=αFxrAFCxの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。d=1の場合、検証者アルゴリズムVは、zA←σとする。そして、検証者アルゴリズムVは、c1=H1FBzA-αy,zAの等号が成り立つか否かを検証する。検証者アルゴリズムVは、この検証が成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、本手法の一具体例について説明した。[3-5:効率的なアルゴリズム]次に、本手法に係るアルゴリズムを効率化する方法について述べる。上記の第1実施形態において考察した効率化方法と同様、2つのベクトルt∈Kn、e∈Kmを用いて、多変数多項式Fxrをマスクするために用いた多変数多項式FAxをFAx=Fbx、teのように表現する。この表現を用いると、多変数多項式Fxrについて、下記の式19で表現される関係が得られる。そのため、tA=αrt,eA=αFreとすれば、マスク後の多変数多項式FBx=αFxrFAxも、2つのベクトルtA∈Kn、eA∈Kmにより表現することができる。これらの理由から、FAx=Fbx,teと設定すれば、Kn上のベクトル及びKm上のベクトルを用いてFA及びFBを表現できるようになり、通信に必要なデータサイズを大幅に減らすことが可能になる。具体的には、数千~数万倍程度、通信コストが削減される。また、上記の変形により、FB或いはFAからrに関する情報が一切漏れることはない。例えば、eA及びtA或いはe及びtを与えられても、e及びt或いはeA及びtAを知らない限り、rの情報を一切知ることはできない。従って、上記の変形を施したとしても、零知識性は担保される。以下、図21~図27を参照しながら、本手法に係る効率的なアルゴリズムについて説明する。なお、鍵生成アルゴリズムGenの構成は変わらないため、ここでは詳細な説明を省略する。効率的なアルゴリズムの構成例1:図21まず、図21に示した効率的なアルゴリズムの構成について説明する。工程1:まず、証明者アルゴリズムPは、任意に数wを選択する。次いで、証明者アルゴリズムPは、擬似乱数生成器Gに数wを適用してベクトルr∈Kn、t∈Kn、e∈Kmを生成する。つまり、証明者アルゴリズムPは、r,t,e←Gwを計算する。次いで、証明者アルゴリズムPは、z←s-rを計算する。この計算は、秘密鍵sをベクトルrによりマスクする操作に相当する。工程1続き:次いで、証明者アルゴリズムPは、Fbz,te及びzのハッシュ値c1を生成する。つまり、証明者アルゴリズムPは、c1←H1Fbz,te,zを計算する。また、証明者アルゴリズムPは、数wのハッシュ値c2を生成する。つまり、証明者アルゴリズムPは、c2←H2wを計算する。なお、上記のH1...、H2...は、ハッシュ関数である。工程1で生成されたメッセージc1,c2は、検証者アルゴリズムVに送られる。工程2:メッセージc1,c2を受け取った検証者アルゴリズムVは、q通り存在する環Kの元からランダムに1つの数αを選択し、選択した数αを証明者アルゴリズムPに送る。工程3:数αを受け取った証明者アルゴリズムPは、tA←αrtを計算する。さらに、証明者アルゴリズムPは、eA←αFreを計算する。そして、証明者アルゴリズムPは、tA及びeAを検証者アルゴリズムVに送る。工程4:tA及びeAを受け取った検証者アルゴリズムVは、2つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。例えば、検証者アルゴリズムVは、検証パターンの種類を表す2つの数値{0,1}の中から1つの数値を選択し、選択した数値を要求dに設定する。この要求dは証明者アルゴリズムPに送られる。工程5:要求dを受け取った証明者アルゴリズムPは、受け取った要求dに応じて検証者アルゴリズムVに送り返す返答σを生成する。d=0の場合、証明者アルゴリズムPは、返答σ=wを生成する。d=1の場合、証明者アルゴリズムPは、返答σ=zを生成する。工程5で生成された返答σは、検証者アルゴリズムVに送られる。工程6:返答σを受け取った検証者アルゴリズムVは、受け取った返答σを利用して以下の検証処理を実行する。d=0の場合、検証者アルゴリズムVは、rA,tB,eB←Gσを計算する。そして、検証者アルゴリズムVは、c2=H2σの等号が成り立つか否かを検証する。また、検証者アルゴリズムVは、tA=αrAtBの等号が成り立つか否かを検証する。さらに、検証者アルゴリズムVは、eA=αFrAeBの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。d=1の場合、検証者アルゴリズムVは、zA←σを実行する。そして、検証者アルゴリズムVは、c1=H1αFzA-yFbzA,tAeA,zAの等号が成り立つか否かを検証する。検証者アルゴリズムVは、この検証が成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、効率的なアルゴリズムの構成例1について説明した。この効率的なアルゴリズムを利用することにより、通信に必要なデータサイズが大幅に削減される。また、Fxrの計算が必要なくなるため、計算効率も向上する。効率的なアルゴリズムの構成例2:図22次に、図22に示した効率的なアルゴリズムの構成について説明する。図22に示した構成を適用した場合も、図20に示した構成を適用した場合と同様に、通信効率及び計算効率の向上効果が得られる。但し、ここでは図20に示した構成との差分について述べる。図20に示したアルゴリズムの工程5において、d=0の場合にσをwに設定しているが、d=0の場合に設定されるσは、tA,eBに併せて用いることでr,t,eが復元できるような情報であればどのような情報でもよい。例えば、図22に示すように、工程5においてd=0の場合に設定されるσの内容をrにしてもよい。但し、この変形を行う場合には、工程1における計算c2←H2wをc2←H2r,t,eに変形する必要がある。また、工程6においてd=0の場合に検証者アルゴリズムVにより実行される検証内容がc2=H2r,tA-αr,eA-αFrの検証に置き換えられる。以上、効率的なアルゴリズムの構成例2について説明した。効率的なアルゴリズムの構成例3:図23次に、図23に示した効率的なアルゴリズムの構成について説明する。図23に示した構成を適用した場合も、図20に示した構成を適用した場合と同様に、通信効率及び計算効率の向上効果が得られる。但し、ここでは図22に示した構成との差分について述べる。図22に示したアルゴリズムの工程3において、tA←αrtという計算を行っているが、この計算を図23に示すようにtA←αrtという計算に変形してもよい。但し、この変形を行う場合には、工程6においてd=0の場合に検証者アルゴリズムVにより実行される検証内容がc2=H2r,α-1tA-r,eA-αFrの検証に置き換えられる。以上、効率的なアルゴリズムの構成例3について説明した。効率的なアルゴリズムの構成例4:図24次に、図24に示した効率的なアルゴリズムの構成について説明する。図24に示した構成を適用した場合も、図20に示した構成を適用した場合と同様に、通信効率及び計算効率の向上効果が得られる。但し、ここでは図22に示した構成との差分について述べる。図22に示したアルゴリズムの工程3において、eA←αFreという計算を行っているが、この計算を図24に示すようにeA←αFreという計算に変形してもよい。但し、この変形を行う場合には、工程6においてd=0の場合に検証者アルゴリズムVにより実行される検証内容がc2=H2r,tA-αr,eA-α-1eA-Frの検証に置き換えられる。以上、効率的なアルゴリズムの構成例4について説明した。効率的なアルゴリズムの構成例5:図25次に、図25に示した効率的なアルゴリズムの構成について説明する。図25に示した構成を適用した場合も、図20に示した構成を適用した場合と同様に、通信効率及び計算効率の向上効果が得られる。但し、ここでは図22に示した構成との差分について述べる。図22に示したアルゴリズムの工程5において、d=0の場合にσをrに設定しているが、d=0の場合に設定されるσは、tA,eBに併せて用いることでr,t,eが復元できるような情報であればどのような情報でもよい。例えば、図25に示すように、工程5においてd=0の場合に設定されるσの内容をtにしてもよい。但し、この変形を行う場合には、工程2においてαがα∈RK\{0}から選ばれるようにする。また、工程6においてd=0の場合に検証者アルゴリズムVにより実行される検証内容がc2=H2α-1tA-t,t,eA-αFα-1tA-tの検証に置き換えられる。以上、効率的なアルゴリズムの構成例5について説明した。効率的なアルゴリズムの構成例6:図26次に、図26に示した効率的なアルゴリズムの構成について説明する。図26に示した構成を適用した場合も、図20に示した構成を適用した場合と同様に、通信効率及び計算効率の向上効果が得られる。但し、ここでは図25に示した構成との差分について述べる。図25に示したアルゴリズムの工程3において、tA←αrtという計算を行っているが、この計算を図26に示すようにtA←αrtという計算に変形してもよい。但し、この変形を行う場合には、工程6においてd=0の場合に検証者アルゴリズムVにより実行される検証内容がc2=H2α-1tA-t,t,eA-αFα-1tA-tの検証に置き換えられる。以上、効率的なアルゴリズムの構成例6について説明した。効率的なアルゴリズムの構成例7:図27次に、図27に示した効率的なアルゴリズムの構成について説明する。図27に示した構成を適用した場合も、図20に示した構成を適用した場合と同様に、通信効率及び計算効率の向上効果が得られる。但し、ここでは図25に示した構成との差分について述べる。図25に示したアルゴリズムの工程3において、eA←αFreという計算を行っているが、この計算を図27に示すようにeA←αFreという計算に変形してもよい。但し、この変形を行う場合には、工程6においてd=0の場合に検証者アルゴリズムVにより実行される検証内容がc2=H2α-1tA-t,t,α-1eA-αFα-1tA-tの検証に置き換えられる。以上、効率的なアルゴリズムの構成例7について説明した。効率的なアルゴリズムの並列化:図29次に、図29を参照しながら、効率的なアルゴリズムを並列化する方法について説明する。図29に示した構成以下、並列化アルゴリズムは、図28に示した効率的なアルゴリズムを並列化したものである。なお、図28に示した効率的なアルゴリズムは、図22に示した効率的なアルゴリズムと実質的に同じ構成を有するアルゴリズムである。以下、図29に示したフローチャートに沿って説明を進める。工程1:証明者アルゴリズムPは、i=1~Nについて処理1~処理4を実行する。処理1:証明者アルゴリズムPは、任意にベクトルri,ti∈Kn及びei∈Kmを生成する。処理2:証明者アルゴリズムPは、riA←s-riを計算する。この計算は、秘密鍵sをベクトルriによりマスクする操作に相当する。処理3:証明者アルゴリズムPは、c1,i←H1ri,ti,eiを計算する。処理4:証明者アルゴリズムPは、c2,i←H2riA,FbriA,tieiを計算する。工程1で生成されたメッセージc1,1,c2,1,...,c1,N,c2,Nは、検証者アルゴリズムVに送られる。工程2:メッセージc1,1,c2,1,...,c1,N,c2,Nを受け取った検証者アルゴリズムVは、i=1~Nのそれぞれについて、q通り存在する環Kの元からランダムに1つの数αiを選択し、選択した数αiを証明者アルゴリズムPに送る。工程3:数αiを受け取った証明者アルゴリズムPは、i=1~Nのそれぞれについて、tiA←αiri-tiを計算する。さらに、証明者アルゴリズムPは、i=1~Nのそれぞれについて、eiA←αiFri-eiを計算する。そして、証明者アルゴリズムPは、t1A,...,tNA及びe1A,...,eNAを検証者アルゴリズムVに送る。工程4:t1A,...,tNA及びe1A,...,eNAを受け取った検証者アルゴリズムVは、i=1~Nのそれぞれについて、2つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。例えば、検証者アルゴリズムVは、検証パターンの種類を表す2つの数値{0,1}の中から1つの数値を選択し、選択した数値を要求diに設定する。この要求dii=1~Nは証明者アルゴリズムPに送られる。工程5:要求dii=1~Nを受け取った証明者アルゴリズムPは、i=1~Nについて、受け取った要求diに応じて検証者アルゴリズムVに送り返す返答σiを生成する。di=0の場合、証明者アルゴリズムPは、返答σi=riを生成する。di=1の場合、証明者アルゴリズムPは、返答σi=riAを生成する。工程5で生成された返答σiは、検証者アルゴリズムVに送られる。工程6:返答σii=1~Nを受け取った検証者アルゴリズムVは、受け取った返答σii=1~Nを利用して以下の検証処理を実行する。di=0の場合、検証者アルゴリズムVは、ri←σiを実行する。そして、検証者アルゴリズムVは、c1,i=H1ri,αiri-tiA,αiFri-eiAの等号が成り立つか否かを検証する。検証者アルゴリズムVは、この検証が成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。di=1の場合、検証者アルゴリズムVは、riA←σiを実行する。そして、検証者アルゴリズムVは、c2,i=H2riA,αiy-FriA-FbtiA,riA-eiAの等号が成り立つか否かを検証する。検証者アルゴリズムVは、この検証が成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、効率的なアルゴリズムの並列化について説明した。並列化アルゴリズムの効率化:図30図29に示した並列化アルゴリズムは、図30に示すように効率化することができる。図30に示すように、この並列化アルゴリズムは、工程1において、メッセージc1,1,c2,1,...,c1,N,c2,Nをハッシュ値cに変換し、そのハッシュ値cを1パス目で証明者アルゴリズムPから検証者アルゴリズムVへと送るように構成されている。また、この並列化アルゴリズムは、工程5において、di=0の場合に返答σi=ri,c2,iを生成し、di=1の場合に返答σi=riA,c1,iを生成するように構成されている。さらに、この並列化アルゴリズムは、工程6において、次のような処理を実行するように構成されている。工程6:まず、検証者アルゴリズムVは、i=1~Nについて、処理1及び処理2を実行する。但し、実際には、di=0の場合に処理1が実行され、di=1の場合に処理2が実行される。処理1:di=0の場合、検証者アルゴリズムVは、ri,c2,i←σiを実行する。さらに、検証者アルゴリズムVは、c1,i=H1ri,αiri-tiA,αiFri-eiAを計算する。そして、検証者アルゴリズムVは、c1,i,c2,iを保持する。処理2:di=1の場合、検証者アルゴリズムVは、riA,c1,i←σiを実行する。さらに、検証者アルゴリズムVは、c2,i=H2riA,αiy-FriA-FbtiA,riA-eiAを計算する。そして、検証者アルゴリズムVは、c1,i,c2,iを保持する。i=1~Nについて、上記の処理1及び処理2を実行した後、検証者アルゴリズムVは、c=Hc1,1,c2,1,...,c1,N,c2,Nの等号が成り立つか否かを検証する。検証者アルゴリズムVは、この検証が成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、並列化アルゴリズムの効率化について説明した。並列化アルゴリズムの更なる効率化:図31図30に示した並列化アルゴリズムは、図31に示すように更に効率化することができる。図31に示すように、この並列化アルゴリズムは、工程3において、t1A,e1A,...,tNA,eNAをハッシュ値vに変換し、そのハッシュ値vを3パス目で証明者アルゴリズムPから検証者アルゴリズムVへと送るように構成されている。また、この並列化アルゴリズムは、工程5において、di=0の場合に返答σi=ri,ti,ei,c2,iを生成し、di=1の場合に返答σi=riA,tiA,eiA,c1,iを生成するように構成されている。さらに、この並列化アルゴリズムは、工程6において、次のような処理を実行するように構成されている。工程6:まず、検証者アルゴリズムVは、i=1~Nについて、処理1及び処理2を実行する。但し、実際には、di=0の場合に処理1が実行され、di=1の場合に処理2が実行される。処理1:di=0の場合、検証者アルゴリズムVは、ri,ti,ei,c2,i←σiを実行する。そして、検証者アルゴリズムVは、c1,i=H1ri,ti,eiを計算する。さらに、検証者アルゴリズムVは、tiA←αiri-ti、eiA←αiFri-eiを計算する。そして、検証者アルゴリズムVは、c1,i,c2,i及びtiA,eiAを保持する。処理2:di=1の場合、検証者アルゴリズムVは、riA,tiA,eiA,c1,i←σiを実行する。そして、検証者アルゴリズムVは、c2,i=H2riA,αiy-FriA-FbriA,tiA-eiAを計算する。そして、検証者アルゴリズムVは、c1,i,c2,i及びtiA,eiAを保持する。i=1~Nについて、上記の処理1及び処理2を実行した後、検証者アルゴリズムVは、c=Hc1,1,c2,1,...,c1,N,c2,Nの等号が成り立つか否かを検証する。さらに、検証者アルゴリズムVは、v=Ht1A,e1A,...,tNA,eNAの等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。以上、並列化アルゴリズムの更なる効率化を図れる構造について説明した。上記のように、証明者アルゴリズムPと検証者アルゴリズムVとの間でやり取りされる複数の情報をハッシュ値にまとめることで、3パス目の通信データのサイズを低減することが可能になる。さらに、上記のアルゴリズムの中で、ri,ti,eiを1つの乱数シードから生成するようにアルゴリズムの構成を変形することで、通信データサイズの期待値が削減される。また、要求diとして、0が選択された数と1が選択された数とが等しくなるように制限を加えると、確実に通信データサイズが削減される。例えば、q,n,m,N=24,45,30,88に設定すると、図30に示したアルゴリズムの場合、公開鍵が120ビット、秘密鍵が180ビット、通信データサイズが42840ビットとなる。一方、図31に示したアルゴリズムの場合、q,n,m,N=24,45,30,88に設定すると、公開鍵が120ビット、秘密鍵が180ビット、通信データサイズが27512ビットとなる。このように、上述した並列化アルゴリズムの更なる効率化を行うことにより、通信データサイズを顕著に削減することが可能になる。[3-6:直列並列ハイブリッドアルゴリズム]偽証が成功する確率を無視できる程度にまで小さくするために、対話プロトコルを複数回実行する必要性については既に説明した通りである。また、対話プロトコルを複数回実行する方法として、直列的な方法と並列的な方法とを紹介した。特に、並列的な方法については、具体的な並列化アルゴリズムを示して説明した。ここでは、直列的な方法と並列的な方法とを組み合わせたハイブリッドタイプのアルゴリズムを紹介する。ハイブリッド構成1図32を参照しながら、ハイブリッドタイプのアルゴリズム以下、並直列アルゴリズムについて説明する。図32には、本手法に係る基本構成、この基本構成を直列化した直列化アルゴリズム、並列化した並列化アルゴリズム、及び並直列アルゴリズムを示した。基本構成では、1パス目にメッセージc1,c2が証明者から検証者へと送られる。2パス目では、検証者から証明者へと数αが送られる。3パス目では、証明者から検証者へとベクトルtA及びeAが送られる。4パス目では、検証者から証明者へと要求dが送られる。5パス目では、証明者から検証者へと返答σが送られる。上記の基本構成を並列化した場合、1パス目では、N回分のメッセージc1,1,c2,1,...,c1,N,c2,Nが証明者から検証者へと送られる。2パス目では、検証者から証明者へとN回分の数α1,...,αNが送られる。3パス目では、証明者から検証者へとN回分のベクトルt1A,...,tNA,e1A,...,eNAが送られる。4パス目では、検証者から証明者へとN回分の要求d1,...,dNが送られる。5パス目では、証明者から検証者へとN回分の返答σ1,...,σNが送られる。本手法に係る並列化アルゴリズムは、受動的攻撃に対する安全性が保証される。また、対話の回数が5回で済む。さらに、1パス目で送信されるN回分のメッセージや3パス目で送信されるN回分のベクトルなどをそれぞれ1つのハッシュ値に纏めることにより、通信効率を向上させることができる。一方、上記の基本構成を直列化した場合、1パス目では、1回分のメッセージc1,1,c2,1が証明者から検証者へと送られる。2パス目では、検証者から証明者へと1回分の数α1が送られる。3パス目では、証明者から検証者へと1回分のベクトルt1A,e1Aが送られる。4パス目では、検証者から証明者へと1回分の要求d1が送られる。5パス目では、証明者から検証者へと1回分の返答σ1が送られる。同様にして、証明者から検証者へと返答σNが送られるまで対話が繰り返し実行される。直列化アルゴリズムは、能動的攻撃に対する安全性が保証される。また、偽証確率が確実に削減されることを証明することが可能である。さて、並直列アルゴリズムは、並列化アルゴリズムの性質と直列化アルゴリズムの性質とを併せ持つアルゴリズムである。図32に示した並直列アルゴリズムでは、1パス目で、N回分のメッセージc1,1,c2,1,...,c1,N,c2,Nが証明者から検証者へと送られる。2パス目では、検証者から証明者へと1回分の数α1が送られる。3パス目では、証明者から検証者へと1回分のベクトルt1A,e1Aが送られる。4パス目では、検証者から証明者へと1回分の要求d1が送られる。5パス目では、証明者から検証者へと1回分の返答σ1が送られる。その後、証明者と検証者との間で、α2,...,αN,t2A,e2A,...,tNA,eNA,d2,...,dN,σ2,...,σNのやり取りが行われる。本手法に基づく並直列アルゴリズムの場合、受動的攻撃に対する安全性が保証される。また、対話の回数が4N1回で済む。さらに、1パス目で送信されるN回分のメッセージを1つのハッシュ値に纏めることにより、通信効率を向上させることができる。ハイブリッド構成2図33を参照しながら、他の並直列アルゴリズムについて説明する。図33には、本手法に係る基本構成、この基本構成を直列化した直列化アルゴリズム、並列化した並列化アルゴリズム、及び並直列アルゴリズムを示した。なお、基本構成、直列化アルゴリズム、並列化アルゴリズムの構成及び性質については、上記の通りである。図33に示した並直列アルゴリズムは、並列化アルゴリズムの性質と直列化アルゴリズムの性質とを併せ持つアルゴリズムである。この並直列アルゴリズムでは、1パス目で、N回分のメッセージc1,1,c2,1,...,c1,N,c2,Nが証明者から検証者へと送られる。2パス目では、検証者から証明者へとN回分の数α1,...,αNが送られる。3パス目では、証明者から検証者へとN回分のベクトルt1A,e1A,...,tNA,eNAが送られる。4パス目では、検証者から証明者へと1回分の要求d1が送られる。5パス目では、証明者から検証者へと1回分の返答σ1が送られる。その後、証明者と検証者との間で、d2,...,dN,σ2,...,σNのやり取りが行われる。本手法に基づく並直列アルゴリズムの場合、受動的攻撃に対する安全性が保証される。また、対話の回数が2N3回で済む。さらに、1パス目で送信されるN回分のメッセージや3パス目で送信されるN回分のベクトルなどを1つのハッシュ値に纏めることにより、通信効率を向上させることができる。ハイブリッド構成3図34を参照しながら、他のハイブリッドタイプのアルゴリズム以下、直並列アルゴリズムについて説明する。図34には、本手法に係る基本構成、この基本構成を直列化した直列化アルゴリズム、並列化した並列化アルゴリズム、及び直並列アルゴリズムを示した。なお、基本構成、直列化アルゴリズム、並列化アルゴリズムの構成及び性質については、上記の通りである。図34に示した直並列アルゴリズムは、並列化アルゴリズムの性質と直列化アルゴリズムの性質とを併せ持つアルゴリズムである。この直並列アルゴリズムでは、1パス目で、1回分のメッセージc1,1,c2,1が証明者から検証者へと送られる。2パス目では、検証者から証明者へと1回分の数α1が送られる。3パス目では、証明者から検証者へと1回分のベクトルt1A,e1Aが送られる。4パス目では、検証者から証明者へと1回分の要求d1が送られる。その後、証明者と検証者との間で、c1,2,c2,2,...,c1,N,c2,N,α2,...,αN,t2A,e2A,...,tNA,eNA,d2,...,dNのやり取りが行われる。最後に、証明者から検証者へとN回分の返答σ1...,σNが送られる。本手法に基づく直並列アルゴリズムの場合、能動的攻撃に対する安全性が保証される。また、対話の回数が4N1回で済む。ハイブリッド構成4図35を参照しながら、他の直並列アルゴリズムについて説明する。図35には、本手法に係る基本構成、この基本構成を直列化した直列化アルゴリズム、並列化した並列化アルゴリズム、及び直並列アルゴリズムを示した。なお、基本構成、直列化アルゴリズム、並列化アルゴリズムの構成及び性質については、上記の通りである。図35に示した直並列アルゴリズムは、並列化アルゴリズムの性質と直列化アルゴリズムの性質とを併せ持つアルゴリズムである。この直並列アルゴリズムでは、1パス目で、1回分のメッセージc1,1,c2,1が証明者から検証者へと送られる。2パス目では、検証者から証明者へと1回分の数α1が送られる。その後、証明者と検証者との間で、c1,2,c2,2,...,c1,N,c2,N,α2,...,αNのやり取りが行われる。αNのやり取りを終えた後、証明者から検証者へとN回分のベクトルt1A,e1A,...,tNA,eNAが送られる。次いで、検証者から証明者へとN回分の要求d1,...,d1が送られる。最後に、証明者から検証者へとN回分の返答σ1...,σNが送られる。本手法に基づく直並列アルゴリズムの場合、受動的攻撃に対する安全性が保証される。また、対話の回数が2N3回で済む。以上、本手法に基づくハイブリッドタイプのアルゴリズムについて説明した。以上、本技術の第2実施形態について説明した。なお、多変数連立方程式の形式については、上記の第1実施形態と同様である。<4:効率的なアルゴリズムの拡張>ところで、上記の第1及び第2実施形態に係る効率的なアルゴリズムは、下記の式20で表現される2次の多変数多項式を公開鍵又はシステムパラメータとして利用する構成であった。しかし、上記の効率的なアルゴリズムは、3次以上の次数を有する多変数多項式を公開鍵又はシステムパラメータとして利用する構成に拡張することができる。[4-1:多変数多項式の高次化について]例えば、位数q=pkの体上で定義される3次以上の多変数多項式下記の式21を参照を公開鍵又はシステムパラメータとして利用する構成について考えてみよう。上記の第1及び第2実施形態に係る効率的なアルゴリズムにおける公開鍵として多変数多項式flが利用可能となる条件は、下記の式22がx1,...,xn及びy1,...,ynに対して双線形になることである。上記の式20で表現される多変数多項式の場合、下記の式23に示すように容易に双線形性を確認することができる下線部がxi、yiのそれぞれについて線形となっている。また、上記の式21で表現される多変数多項式の場合についても同様にして、下記の式24に示すように双線形性を確認することができる。但し、下記の式24の下線部は、位数pの体GFp上における双線形性を示している。そのため、上記の第2実施形態に係る効率的なアルゴリズムの公開鍵として上記の式21で表現される多変数多項式を利用する場合、当該アルゴリズムの工程2の後に検証者が送信する数αは、GFpの要素に限定する必要がある。このような理由から、上記の第1及び第2実施形態に係る効率的なアルゴリズムを拡張し、上記の式21で表現されるような3次以上の多変数多項式を公開鍵として利用するアルゴリズムを構築することが可能であると言える。ここで、上記の式20で表現される多変数多項式以下、2次多項式と、上記の式21で表現される多変数多項式以下、多次多項式との関係について考察しておきたい。いま、位数q=pの体上で定義されるnk変数の2次多項式、及び位数q=pkの体上で定義されるn変数の多次多項式について考える。この場合、mk本の2次多項式で構成される連立方程式の解答困難性は、m本の多次多項式で構成される連立方程式の解答困難性と等価である。例えば、位数2の体上で定義される80本の80変数2次多項式により構成される連立方程式と、位数28の体上で定義される10本の10変数多次多項式とは、その解答困難性が等価である。つまり、GFpkの要素と、GFpkの要素とを同型写像により同一視した場合、位数q=pの体上で定義されるmk本のnk変数2次多項式の組で表現される関数と等価な、位数q=pkの体上で定義されるm本のn変数多次多項式の組で表現される関数が存在する。例えば、GF28の要素と、GF28の要素とを同型写像により同一視した場合、位数2の体上で定義される80本の80変数2次多項式の組で表現される関数と等価な、位数28の体上で定義される10本の10変数多次多項式の組で表現される関数が存在する。このような理由から、上記の2次多項式を利用するか、上記の多次多項式を利用するかは、任意に選択することが可能である。ここで、上記の2次多項式を利用する場合の計算効率と上記の多次多項式を利用する場合の計算効率とについて考察しておきたい。位数2の体上で定義されるnk変数の2次多項式を利用する場合、アルゴリズムに含まれる演算は、nk個の1ビット変数を対象に実行されることになる。つまり、演算の単位が1ビットとなる。一方、位数2kの体上で定義されるn変数の多次多項式を利用する場合、アルゴリズムに含まれる演算は、n個のkビット変数を対象に実行されることになる。つまり、演算の単位がkビットとなる。このkk=2,3,4,...は任意に設定することができる。そのため、実装上、都合の良い値にkを設定することにより、計算効率を向上させることが可能になる。例えば、32ビットのアーキティクチャ上にアルゴリズムを実装する場合、1ビット単位で演算を実行する構成にするよりも、32ビット単位で演算を実行する構成にする方が高い計算効率を得られる。このように、上記の第1及び第2実施形態に係る効率的なアルゴリズムを、多次多項式を公開鍵として利用できるように拡張することで、演算の単位を実装するアーキティクチャに合わせることが可能になる。その結果、計算効率を向上させることが可能になる。[4-2:拡張方式高次項の追加]ところで、3次以上の多次多項式を利用する方法として、2次多項式に3次以上の項を追加する方法も考えられる。例えば、下記の式25に示すように、上記の式20で表現される2次多項式に4次の項を追加する方法が考えられる。多次多項式flを下記の式25のように定義すると、下記の式26で定義される項glx,yは、下記の式27のように表現される。なお、以下では、項glx,yのことをpolarformと呼ぶことがある。上記の式27に示すように、項glx,yは双線形にならない。そこで、4つの変数x1,x2,x3,x4から2つ選んだ6通りの項xixj、及び4つの変数x1,x2,x3,x4から3つ選んだ4通りの項xixjxkを下記の式28及び式29のように4つの変数tij、tijA、tijk、tijkAで表現する。この表現を用いると、3次以上の多変数多項式を用いて、上記の効率的なアルゴリズムを実現することができる。なお、上記の式25に示した例では、2次多項式に4次の項を追加しているが、4次の項に代えて3次の項例えば、x1x2x3又は5次以上の項例えば、x1x2x3x4x5を追加してもよい。このように、3次以上の項を追加することにより、方程式の頑強性を向上させることが可能になる。<5:頑強性を高める仕組み>ここで、上記の第1及び第2実施形態に係るアルゴリズムの頑強性を更に高めるための仕組みについて紹介する。[5-1:システムパラメータの設定方法]これまで、多変数多項式の係数又はその係数の生成に利用する乱数シード以下、多変数多項式の係数等をどのように設定するかについては詳しく言及してこなかった。多変数多項式の係数等は、システムに共通のパラメータとしてもよいし、ユーザ毎に異なるパラメータとしてもよい。しかし、多変数多項式の係数等をシステムに共通のパラメータとすると、その多変数多項式に脆弱性が見つかった場合、システム全体について設定を更新する必要が生じてしまう。また、ランダムに選んだ係数を持つ多変数多項式について、平均的な頑強性解くことの難しさは解析されているが、ある特定の係数を持つ多変数多項式について十分な頑強性を有することを保証することは難しい。そこで、本件発明者は、各ユーザが選択した文字列などを擬似乱数生成器のシードに利用して多変数多項式の係数を生成する仕組みを考案した。例えば、ユーザのe-mailアドレスをシードに利用したり、e-mailアドレスと更新日時などとを結合した文字列をシードに利用したりする方法などが考えられる。このような方法を用いると、万が一、ある文字列から生成された係数を持つ多変数多項式に脆弱性が見つかった場合でも、その係数を持つ多変数多項式を利用しているユーザのみに影響が限定される。また、文字列を変えるだけで多変数多項式が変更されるため、容易に脆弱性を解消することができる。以上、システムパラメータの設定方法について説明した。なお、上記の説明では文字列を例に挙げたが、ユーザ毎に異なる数字の列や記号の列を利用してもよい。[5-2:イレギュラーな要求に対する応答方法]次に、イレギュラーな要求に対する応答方法について説明する。5-2-1:証明者による応答方法について図36に示すように、対話プロトコルの中で、検証者が偽りの要求を投げかけてくる可能性が考えられる。図36の例では、証明者が検証者へとメッセージc1,c2,c3を送り、検証者が証明者へと要求d=0を送った後、証明者から検証者へと要求d=0に対応する返答σが送られている。ここまでは正常な対話である。しかし、図36の例において、検証者は、証明者に要求d=1に対応する返答σをさらに要求している。もし、この要求に応じ、証明者が要求d=1に対応する返答σを検証者に送ってしまうと、秘密鍵が検証者に漏洩してしまう。このような秘密鍵の漏洩は現実的に起こりうることである。例えば、検証者は、2パス目で要求d=1を送信したのではなく、要求d=0を送信したはずだと偽って、要求d=1に対応する返答σをさらに要求するかもしれない。一方、証明者は、2パス目で送信された要求dのビットが通信エラーにより別のビットになってしまったと勘違いするかもしれない。そこで、本件発明者は、上記のようにして秘密鍵の漏洩が生じるのを避ける方法を考案した。具体的には、1回分のメッセージについて証明者が2通り以上の要求dに対応する返答を求めてきた場合に、対話を終了するか、或いは、新しい乱数を利用して1パス目から対話をやり直す方法が考案された。この方法を適用すれば、検証者が偽って2通り以上の要求dに対応する返答を求めてきても、秘密鍵が漏洩することはなくなる。以上、イレギュラーな要求により秘密鍵が漏洩しないようにする工夫について述べた。なお、ここでは3パスの基本構成を例に挙げたが、直列的な方法、並列的な方法、或いは、ハイブリッドタイプのアルゴリズムについても同様の工夫を加えることにより、安全性を向上させることができる。もちろん、5パスのアルゴリズムについても同様である。5-2-2:検証者による応答方法についてまた、図37に示すように、証明者が偽って要求dの再送を要求してくる可能性もある。図37の例では、証明者が検証者へとメッセージc1,c2,c3を送り、検証者が証明者へと要求d=0を送った後、証明者が要求dの再送を要求している。この要求に応じて、検証者が再びランダムに要求dを選択すると、先に送った要求d=0とは異なる要求d=1が選択される可能性がある。この場合、検証者から証明者へと要求d=1が送られる。図37の例において、証明者は、要求d=1に対応する返答σを検証者に送っている。しかし、証明者は、要求d=1には回答できるが、要求d=0には回答できなかったのかもしれない。つまり、証明者が偽証している可能性が否定できない。例えば、証明者は、要求dを紛失してしまったので要求dを再送して欲しいと検証者に求めるかもしれない。一方、検証者は、通信エラーにより先に送信した要求が紛失したと考え、証明者の求めに応じて要求dを再送してしまうかもしれない。そして、再送した要求dが先に送信した要求dと異なるものである場合、偽証が成功してしまう。図37の例から分かるように、要求dがランダムに選ばれることで、証明者に偽証の機会を与えてしまう。そこで、本件発明者は、偽証の機会を与えないようにする方法を考案した。この方法は、1回分のメッセージについて証明者が要求dの送信を再度求めてきた場合に、検証者が対話を終了するか、或いは、新たな乱数を生成せずに前回と同じ要求dを再送するように対話プロトコルを改良するというものである。この方法を適用すると、要求dの再送要求を利用した偽証の機会をなくすことができる。以上、イレギュラーな要求により偽証が成功する機会をなくす工夫について述べた。なお、ここでは3パスの基本構成を例に挙げたが、直列的な方法、並列的な方法、或いは、ハイブリッドタイプのアルゴリズムについても同様の工夫を加えることにより、安全性を向上させることができる。もちろん、5パスのアルゴリズムについても同様である。<6:ハードウェア構成例>上記の各アルゴリズムは、例えば、図38に示す情報処理装置のハードウェア構成を用いて実行することが可能である。つまり、当該各アルゴリズムの処理は、コンピュータプログラムを用いて図38に示すハードウェアを制御することにより実現される。なお、このハードウェアの形態は任意であり、例えば、パーソナルコンピュータ、携帯電話、PHS、PDA等の携帯情報端末、ゲーム機、接触式又は非接触式のICチップ、接触式又は非接触式のICカード、又は種々の情報家電がこれに含まれる。但し、上記のPHSは、PersonalHandy-phoneSystemの略である。また、上記のPDAは、PersonalDigitalAssistantの略である。図38に示すように、このハードウェアは、主に、CPU902と、ROM904と、RAM906と、ホストバス908と、ブリッジ910と、を有する。さらに、このハードウェアは、外部バス912と、インターフェース914と、入力部916と、出力部918と、記憶部920と、ドライブ922と、接続ポート924と、通信部926と、を有する。但し、上記のCPUは、CentralProcessingUnitの略である。また、上記のROMは、ReadOnlyMemoryの略である。そして、上記のRAMは、RandomAccessMemoryの略である。CPU902は、例えば、演算処理装置又は制御装置として機能し、ROM904、RAM906、記憶部920、又はリムーバブル記録媒体928に記録された各種プログラムに基づいて各構成要素の動作全般又はその一部を制御する。ROM904は、CPU902に読み込まれるプログラムや演算に用いるデータ等を格納する手段である。RAM906には、例えば、CPU902に読み込まれるプログラムや、そのプログラムを実行する際に適宜変化する各種パラメータ等が一時的又は永続的に格納される。これらの構成要素は、例えば、高速なデータ伝送が可能なホストバス908を介して相互に接続される。一方、ホストバス908は、例えば、ブリッジ910を介して比較的データ伝送速度が低速な外部バス912に接続される。また、入力部916としては、例えば、マウス、キーボード、タッチパネル、ボタン、スイッチ、及びレバー等が用いられる。さらに、入力部916としては、赤外線やその他の電波を利用して制御信号を送信することが可能なリモートコントローラ以下、リモコンが用いられることもある。出力部918としては、例えば、CRT、LCD、PDP、又はELD等のディスプレイ装置、スピーカ、ヘッドホン等のオーディオ出力装置、プリンタ、携帯電話、又はファクシミリ等、取得した情報を利用者に対して視覚的又は聴覚的に通知することが可能な装置である。但し、上記のCRTは、CathodeRayTubeの略である。また、上記のLCDは、LiquidCrystalDisplayの略である。そして、上記のPDPは、PlasmaDisplayPanelの略である。さらに、上記のELDは、Electro-LuminescenceDisplayの略である。記憶部920は、各種のデータを格納するための装置である。記憶部920としては、例えば、ハードディスクドライブHDD等の磁気記憶デバイス、半導体記憶デバイス、光記憶デバイス、又は光磁気記憶デバイス等が用いられる。但し、上記のHDDは、HardDiskDriveの略である。ドライブ922は、例えば、磁気ディスク、光ディスク、光磁気ディスク、又は半導体メモリ等のリムーバブル記録媒体928に記録された情報を読み出し、又はリムーバブル記録媒体928に情報を書き込む装置である。リムーバブル記録媒体928は、例えば、DVDメディア、Blu-rayメディア、HDDVDメディア、各種の半導体記憶メディア等である。もちろん、リムーバブル記録媒体928は、例えば、非接触型ICチップを搭載したICカード、又は電子機器等であってもよい。但し、上記のICは、IntegratedCircuitの略である。接続ポート924は、例えば、USBポート、IEEE1394ポート、SCSI、RS-232Cポート、又は光オーディオ端子等のような外部接続機器930を接続するためのポートである。外部接続機器930は、例えば、プリンタ、携帯音楽プレーヤ、デジタルカメラ、デジタルビデオカメラ、又はICレコーダ等である。但し、上記のUSBは、UniversalSerialBusの略である。また、上記のSCSIは、SmallComputerSystemInterfaceの略である。通信部926は、ネットワーク932に接続するための通信デバイスであり、例えば、有線又は無線LAN、Bluetooth登録商標、又はWUSB用の通信カード、光通信用のルータ、ADSL用のルータ、又は接触又は非接触通信用のデバイス等である。また、通信部926に接続されるネットワーク932は、有線又は無線により接続されたネットワークにより構成され、例えば、インターネット、家庭内LAN、赤外線通信、可視光通信、放送、又は衛星通信等である。但し、上記のLANは、LocalAreaNetworkの略である。また、上記のWUSBは、WirelessUSBの略である。そして、上記のADSLは、AsymmetricDigitalSubscriberLineの略である。<7:まとめ>最後に、本技術の実施形態に係る技術内容について簡単に纏める。ここで述べる技術内容は、例えば、PC、携帯電話、ゲーム機、情報端末、情報家電、カーナビゲーションシステム等、種々の情報処理装置に対して適用することができる。なお、以下で述べる情報処理装置の機能は、1台の情報処理装置を利用して実現することも可能であるし、複数台の情報処理装置を利用して実現することも可能である。また、以下で述べる情報処理装置が処理を実行する際に用いるデータ記憶手段及び演算処理手段は、当該情報処理装置に設けられたものであってもよいし、ネットワークを介して接続された機器に設けられたものであってもよい。上記の情報処理装置の機能構成は以下のように表現される。例えば、下記1に記載の情報処理装置は、多次多変数連立方程式の求解困難性に安全性の根拠を置く効率的な電子署名方式の署名提供機能を有する。1環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてN組のメッセージを生成するメッセージ生成部と、1組の入力情報に対してk通りk≧3の第1情報の中から1個の第1情報を選択する一方向性関数に対し、文書MとN組の前記メッセージとを入力して、N個の第1情報を選択する第1情報選択部と、N個の前記第1情報にそれぞれ対応するN個の第2情報を生成する第2情報生成部と、N個の前記第1情報及びN個の前記第2情報を電子署名として、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に提供する署名提供部と、を備え、前記ベクトルsは署名鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記第2情報を利用して、当該第2情報に対応する第1情報の種類に応じて選択される所定の演算を実行することで得られる情報である、情報処理装置。2前記多次多変数多項式の組Fは、Fbx,y=Fxy-Fx-Fyで定義されるFbx,yがx及びyに関して双線形となるように設定される、請求項1に記載の情報処理装置。3前記多次多変数多項式の組Fは、前記公開鍵を生成するユーザ毎に異なる情報を用いて生成される、上記1又は2に記載の情報処理装置。4前記多次多変数多項式の組Fは、Fbx,y=FAxy-FAx-FAyで定義されるFbx,yがx及びyに関して双線形となる2次多項式FAと、3次以上の次数を有する項との和で表現される、上記1~3のいずれか1項に記載の情報処理装置。5環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報保持部と、前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたN組のメッセージを取得するメッセージ取得部と、1組の入力情報に対してk通りk≧3の第1情報の中から1個の第1情報を選択する一方向性関数に対し、文書MとN組の前記メッセージとを入力することで選択されたN個の第1情報と、N個の前記第1情報にそれぞれ対応するN個の第2情報とで構成される電子署名を取得する署名取得部と、前記メッセージ、前記多次多変数多項式の組F、前記ベクトルy、及び前記電子署名に基づいて前記文書Mの正当性を検証する署名検証部と、を備え、前記ベクトルsは署名鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記第2情報を利用して、当該第2情報に対応する第1情報の種類に応じて選択される所定の演算を実行することで得られる情報である、情報処理装置。6前記多次多変数多項式の組Fは、Fbx,y=Fxy-Fx-Fyで定義されるFbx,yがx及びyに関して双線形となるように設定される、上記5に記載の情報処理装置。7前記多次多変数多項式の組Fは、前記公開鍵を生成するユーザ毎に異なる情報を用いて生成される、上記5又は6に記載の情報処理装置。8前記多次多変数多項式の組Fは、Fbx,y=FAxy-FAx-FAyで定義されるFbx,yがx及びyに関して双線形となる2次多項式FAと、3次以上の次数を有する項との和で表現される、上記5~7のいずれか1項に記載の情報処理装置。9環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてN組のメッセージを生成するステップと、1組の入力情報に対してk通りk≧3の第1情報の中から1個の第1情報を選択する一方向性関数に対し、文書MとN組の前記メッセージとを入力して、N個の第1情報を選択するステップと、N個の前記第1情報にそれぞれ対応するN個の第2情報を生成するステップと、N個の前記第1情報及びN個の前記第2情報を電子署名として、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に提供するステップと、を含み、前記ベクトルsは署名鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記第2情報を利用して、当該第2情報に対応する第1情報の種類に応じて選択される所定の演算を実行することで得られる情報である、署名提供方法。10環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持するステップと、前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたN組のメッセージを取得するステップと、1組の入力情報に対してk通りk≧3の第1情報の中から1個の第1情報を選択する一方向性関数に対し、文書MとN組の前記メッセージとを入力することで選択されたN個の第1情報と、N個の前記第1情報にそれぞれ対応するN個の第2情報とで構成される電子署名を取得するステップと、前記メッセージ、前記多次多変数多項式の組F、前記ベクトルy、及び前記電子署名に基づいて前記文書Mの正当性を検証するステップと、を含み、前記ベクトルsは署名鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記第2情報を利用して、当該第2情報に対応する第1情報の種類に応じて選択される所定の演算を実行することで得られる情報である、署名検証方法。11環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてN組のメッセージを生成するメッセージ生成機能と、1組の入力情報に対してk通りk≧3の第1情報の中から1個の第1情報を選択する一方向性関数に対し、文書MとN組の前記メッセージとを入力して、N個の第1情報を選択する第1情報選択機能と、N個の前記第1情報にそれぞれ対応するN個の第2情報を生成する第2情報生成機能と、N個の前記第1情報及びN個の前記第2情報を電子署名として、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に提供する署名提供機能と、をコンピュータに実現させるためのプログラムであり、前記ベクトルsは署名鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記第2情報を利用して、当該第2情報に対応する第1情報の種類に応じて選択される所定の演算を実行することで得られる情報である、プログラム。12環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報保持機能と、前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたN組のメッセージを取得するメッセージ取得機能と、1組の入力情報に対してk通りk≧3の第1情報の中から1個の第1情報を選択する一方向性関数に対し、文書MとN組の前記メッセージとを入力することで選択されたN個の第1情報と、N個の前記第1情報にそれぞれ対応するN個の第2情報とで構成される電子署名を取得する署名取得機能と、前記メッセージ、前記多次多変数多項式の組F、前記ベクトルy、及び前記電子署名に基づいて前記文書Mの正当性を検証する署名検証機能と、をコンピュータに実現させるためのプログラムであり、前記ベクトルsは署名鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記第2情報を利用して、当該第2情報に対応する第1情報の種類に応じて選択される所定の演算を実行することで得られる情報である、プログラム。13環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルs∈Knに基づいてN組のメッセージを生成するメッセージ生成機能と、1組の入力情報に対してk通りk≧3の第1情報の中から1個の第1情報を選択する一方向性関数に対し、文書MとN組の前記メッセージとを入力して、N個の第1情報を選択する第1情報選択機能と、N個の前記第1情報にそれぞれ対応するN個の第2情報を生成する第2情報生成機能と、N個の前記第1情報及びN個の前記第2情報を電子署名として、前記多次多変数多項式の組F及びベクトルy=y1,...,ym=f1s,...,fmsを保持する検証者に提供する署名提供機能と、をコンピュータに実現させるためのプログラムが記録された、コンピュータにより読み取り可能な記録媒体であり、前記ベクトルsは署名鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記第2情報を利用して、当該第2情報に対応する第1情報の種類に応じて選択される所定の演算を実行することで得られる情報である、記録媒体。14環K上で定義される多次多変数多項式の組F=f1,...,fm及びベクトルy=y1,...,ym=f1s,...,fmsを保持する情報保持機能と、前記多次多変数多項式の組F及びベクトルs∈Knに基づいて生成されたN組のメッセージを取得するメッセージ取得機能と、1組の入力情報に対してk通りk≧3の第1情報の中から1個の第1情報を選択する一方向性関数に対し、文書MとN組の前記メッセージとを入力することで選択されたN個の第1情報と、N個の前記第1情報にそれぞれ対応するN個の第2情報とで構成される電子署名を取得する署名取得機能と、前記メッセージ、前記多次多変数多項式の組F、前記ベクトルy、及び前記電子署名に基づいて前記文書Mの正当性を検証する署名検証機能と、をコンピュータに実現させるためのプログラムが記録された、コンピュータにより読み取り可能な記録媒体であり、前記ベクトルsは署名鍵であり、前記多次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記第2情報を利用して、当該第2情報に対応する第1情報の種類に応じて選択される所定の演算を実行することで得られる情報である、記録媒体。15前記m及びnは、m<nの関係を有する、上記1~8のいずれか1項に記載の情報処理装置。16前記m及びnは、2m-n≪1の関係を有する、上記15に記載の情報処理装置。備考上記の署名生成アルゴリズムSigは、メッセージ生成部、第1情報選択部、第2情報生成部、署名提供部の一例である。また、上記の署名検証アルゴリズムVerは、メッセージ取得部、署名取得部、署名検証部の一例である。以上、添付図面を参照しながら本技術の好適な実施形態について説明したが、本技術は係る例に限定されないことは言うまでもない。当業者であれば、特許請求の範囲に記載された範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、それらについても当然に本技術の技術的範囲に属するものと了解される。"