情報処理装置、署名提供方法、署名検証方法、プログラム、及び記録媒体

【課題】高い安全性及び高い効率を有する電子署名方式を実現すること。
【解決手段】環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ_１，…，ｆ_ｍ）及びベクトルｓ∈Ｋ^ｎに基づいてＮ組のメッセージを生成し、一方向性関数に文書ＭとＮ組のメッセージとを入力して、Ｎ個の第１情報を選択し、Ｎ個の第１情報にそれぞれ対応するＮ個の第２情報を生成し、Ｎ個の第１情報及びＮ個の第２情報を電子署名として、多次多変数多項式の組Ｆ及びベクトルｙ＝（ｙ_１，…，ｙ_ｍ）＝（ｆ_１（ｓ），…，ｆ_ｍ（ｓ））を保持する検証者に提供する情報処理装置が提供される。ベクトルｓは署名鍵であり、多次多変数多項式の組Ｆ及びベクトルｙは公開鍵であり、メッセージは、公開鍵及び第２情報を利用して、当該第２情報に対応する第１情報の種類に応じて選択される所定の演算を実行することで得られる情報である。

Notice: Undefined index: DEJ in /mnt/www/gzt_disp.php on line 298

【特許請求の範囲】
【請求項１】
環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ_１，…，ｆ_ｍ）及びベクトルｓ∈Ｋ^ｎに基づいてＮ組のメッセージを生成するメッセージ生成部と、
１組の入力情報に対してｋ通り（ｋ≧３）の第１情報の中から１個の第１情報を選択する一方向性関数に対し、文書ＭとＮ組の前記メッセージとを入力して、Ｎ個の第１情報を選択する第１情報選択部と、
Ｎ個の前記第１情報にそれぞれ対応するＮ個の第２情報を生成する第２情報生成部と、
Ｎ個の前記第１情報及びＮ個の前記第２情報を電子署名として、前記多次多変数多項式の組Ｆ及びベクトルｙ＝（ｙ_１，…，ｙ_ｍ）＝（ｆ_１（ｓ），…，ｆ_ｍ（ｓ））を保持する検証者に提供する署名提供部と、
を備え、
前記ベクトルｓは署名鍵であり、
前記多次多変数多項式の組Ｆ及び前記ベクトルｙは公開鍵であり、
前記メッセージは、前記公開鍵及び前記第２情報を利用して、当該第２情報に対応する第１情報の種類に応じて選択される所定の演算を実行することで得られる情報である、
情報処理装置。
【請求項２】
前記多次多変数多項式の組Ｆは、Ｆ_ｂ（ｘ，ｙ）＝Ｆ（ｘ＋ｙ）−Ｆ（ｘ）−Ｆ（ｙ）で定義されるＦ_ｂ（ｘ，ｙ）がｘ及びｙに関して双線形となるように設定される、
請求項１に記載の情報処理装置。
【請求項３】
前記多次多変数多項式の組Ｆは、前記公開鍵を生成するユーザ毎に異なる情報を用いて生成される、
請求項１に記載の情報処理装置。
【請求項４】
前記多次多変数多項式の組Ｆは、Ｆ_ｂ（ｘ，ｙ）＝Ｆ^Ａ（ｘ＋ｙ）−Ｆ^Ａ（ｘ）−Ｆ^Ａ（ｙ）で定義されるＦ_ｂ（ｘ，ｙ）がｘ及びｙに関して双線形となる２次多項式Ｆ^Ａと、３次以上の次数を有する項との和で表現される、
請求項１に記載の情報処理装置。
【請求項５】
環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ_１，…，ｆ_ｍ）及びベクトルｙ＝（ｙ_１，…，ｙ_ｍ）＝（ｆ_１（ｓ），…，ｆ_ｍ（ｓ））を保持する情報保持部と、
前記多次多変数多項式の組Ｆ及びベクトルｓ∈Ｋ^ｎに基づいて生成されたＮ組のメッセージを取得するメッセージ取得部と、
１組の入力情報に対してｋ通り（ｋ≧３）の第１情報の中から１個の第１情報を選択する一方向性関数に対し、文書ＭとＮ組の前記メッセージとを入力することで選択されたＮ個の第１情報と、Ｎ個の前記第１情報にそれぞれ対応するＮ個の第２情報とで構成される電子署名を取得する署名取得部と、
前記メッセージ、前記多次多変数多項式の組Ｆ、前記ベクトルｙ、及び前記電子署名に基づいて前記文書Ｍの正当性を検証する署名検証部と、
を備え、
前記ベクトルｓは署名鍵であり、
前記多次多変数多項式の組Ｆ及び前記ベクトルｙは公開鍵であり、
前記メッセージは、前記公開鍵及び前記第２情報を利用して、当該第２情報に対応する第１情報の種類に応じて選択される所定の演算を実行することで得られる情報である、
情報処理装置。
【請求項６】
前記多次多変数多項式の組Ｆは、Ｆ_ｂ（ｘ，ｙ）＝Ｆ（ｘ＋ｙ）−Ｆ（ｘ）−Ｆ（ｙ）で定義されるＦ_ｂ（ｘ，ｙ）がｘ及びｙに関して双線形となるように設定される、
請求項５に記載の情報処理装置。
【請求項７】
前記多次多変数多項式の組Ｆは、前記公開鍵を生成するユーザ毎に異なる情報を用いて生成される、
請求項５に記載の情報処理装置。
【請求項８】
前記多次多変数多項式の組Ｆは、Ｆ_ｂ（ｘ，ｙ）＝Ｆ^Ａ（ｘ＋ｙ）−Ｆ^Ａ（ｘ）−Ｆ^Ａ（ｙ）で定義されるＦ_ｂ（ｘ，ｙ）がｘ及びｙに関して双線形となる２次多項式Ｆ^Ａと、３次以上の次数を有する項との和で表現される、
請求項５に記載の情報処理装置。
【請求項９】
環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ_１，…，ｆ_ｍ）及びベクトルｓ∈Ｋ^ｎに基づいてＮ組のメッセージを生成するステップと、
１組の入力情報に対してｋ通り（ｋ≧３）の第１情報の中から１個の第１情報を選択する一方向性関数に対し、文書ＭとＮ組の前記メッセージとを入力して、Ｎ個の第１情報を選択するステップと、
Ｎ個の前記第１情報にそれぞれ対応するＮ個の第２情報を生成するステップと、
Ｎ個の前記第１情報及びＮ個の前記第２情報を電子署名として、前記多次多変数多項式の組Ｆ及びベクトルｙ＝（ｙ_１，…，ｙ_ｍ）＝（ｆ_１（ｓ），…，ｆ_ｍ（ｓ））を保持する検証者に提供するステップと、
を含み、
前記ベクトルｓは署名鍵であり、
前記多次多変数多項式の組Ｆ及び前記ベクトルｙは公開鍵であり、
前記メッセージは、前記公開鍵及び前記第２情報を利用して、当該第２情報に対応する第１情報の種類に応じて選択される所定の演算を実行することで得られる情報である、
署名提供方法。
【請求項１０】
環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ_１，…，ｆ_ｍ）及びベクトルｙ＝（ｙ_１，…，ｙ_ｍ）＝（ｆ_１（ｓ），…，ｆ_ｍ（ｓ））を保持するステップと、
前記多次多変数多項式の組Ｆ及びベクトルｓ∈Ｋ^ｎに基づいて生成されたＮ組のメッセージを取得するステップと、
１組の入力情報に対してｋ通り（ｋ≧３）の第１情報の中から１個の第１情報を選択する一方向性関数に対し、文書ＭとＮ組の前記メッセージとを入力することで選択されたＮ個の第１情報と、Ｎ個の前記第１情報にそれぞれ対応するＮ個の第２情報とで構成される電子署名を取得するステップと、
前記メッセージ、前記多次多変数多項式の組Ｆ、前記ベクトルｙ、及び前記電子署名に基づいて前記文書Ｍの正当性を検証するステップと、
を含み、
前記ベクトルｓは署名鍵であり、
前記多次多変数多項式の組Ｆ及び前記ベクトルｙは公開鍵であり、
前記メッセージは、前記公開鍵及び前記第２情報を利用して、当該第２情報に対応する第１情報の種類に応じて選択される所定の演算を実行することで得られる情報である、
署名検証方法。
【請求項１１】
環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ_１，…，ｆ_ｍ）及びベクトルｓ∈Ｋ^ｎに基づいてＮ組のメッセージを生成するメッセージ生成機能と、
１組の入力情報に対してｋ通り（ｋ≧３）の第１情報の中から１個の第１情報を選択する一方向性関数に対し、文書ＭとＮ組の前記メッセージとを入力して、Ｎ個の第１情報を選択する第１情報選択機能と、
Ｎ個の前記第１情報にそれぞれ対応するＮ個の第２情報を生成する第２情報生成機能と、
Ｎ個の前記第１情報及びＮ個の前記第２情報を電子署名として、前記多次多変数多項式の組Ｆ及びベクトルｙ＝（ｙ_１，…，ｙ_ｍ）＝（ｆ_１（ｓ），…，ｆ_ｍ（ｓ））を保持する検証者に提供する署名提供機能と、
をコンピュータに実現させるためのプログラムであり、
前記ベクトルｓは署名鍵であり、
前記多次多変数多項式の組Ｆ及び前記ベクトルｙは公開鍵であり、
前記メッセージは、前記公開鍵及び前記第２情報を利用して、当該第２情報に対応する第１情報の種類に応じて選択される所定の演算を実行することで得られる情報である、
プログラム。
【請求項１２】
環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ_１，…，ｆ_ｍ）及びベクトルｙ＝（ｙ_１，…，ｙ_ｍ）＝（ｆ_１（ｓ），…，ｆ_ｍ（ｓ））を保持する情報保持機能と、
前記多次多変数多項式の組Ｆ及びベクトルｓ∈Ｋ^ｎに基づいて生成されたＮ組のメッセージを取得するメッセージ取得機能と、
１組の入力情報に対してｋ通り（ｋ≧３）の第１情報の中から１個の第１情報を選択する一方向性関数に対し、文書ＭとＮ組の前記メッセージとを入力することで選択されたＮ個の第１情報と、Ｎ個の前記第１情報にそれぞれ対応するＮ個の第２情報とで構成される電子署名を取得する署名取得機能と、
前記メッセージ、前記多次多変数多項式の組Ｆ、前記ベクトルｙ、及び前記電子署名に基づいて前記文書Ｍの正当性を検証する署名検証機能と、
をコンピュータに実現させるためのプログラムであり、
前記ベクトルｓは署名鍵であり、
前記多次多変数多項式の組Ｆ及び前記ベクトルｙは公開鍵であり、
前記メッセージは、前記公開鍵及び前記第２情報を利用して、当該第２情報に対応する第１情報の種類に応じて選択される所定の演算を実行することで得られる情報である、
プログラム。
【請求項１３】
環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ_１，…，ｆ_ｍ）及びベクトルｓ∈Ｋ^ｎに基づいてＮ組のメッセージを生成するメッセージ生成機能と、
１組の入力情報に対してｋ通り（ｋ≧３）の第１情報の中から１個の第１情報を選択する一方向性関数に対し、文書ＭとＮ組の前記メッセージとを入力して、Ｎ個の第１情報を選択する第１情報選択機能と、
Ｎ個の前記第１情報にそれぞれ対応するＮ個の第２情報を生成する第２情報生成機能と、
Ｎ個の前記第１情報及びＮ個の前記第２情報を電子署名として、前記多次多変数多項式の組Ｆ及びベクトルｙ＝（ｙ_１，…，ｙ_ｍ）＝（ｆ_１（ｓ），…，ｆ_ｍ（ｓ））を保持する検証者に提供する署名提供機能と、
をコンピュータに実現させるためのプログラムが記録された、コンピュータにより読み取り可能な記録媒体であり、
前記ベクトルｓは署名鍵であり、
前記多次多変数多項式の組Ｆ及び前記ベクトルｙは公開鍵であり、
前記メッセージは、前記公開鍵及び前記第２情報を利用して、当該第２情報に対応する第１情報の種類に応じて選択される所定の演算を実行することで得られる情報である、
記録媒体。
【請求項１４】
環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ_１，…，ｆ_ｍ）及びベクトルｙ＝（ｙ_１，…，ｙ_ｍ）＝（ｆ_１（ｓ），…，ｆ_ｍ（ｓ））を保持する情報保持機能と、
前記多次多変数多項式の組Ｆ及びベクトルｓ∈Ｋ^ｎに基づいて生成されたＮ組のメッセージを取得するメッセージ取得機能と、
１組の入力情報に対してｋ通り（ｋ≧３）の第１情報の中から１個の第１情報を選択する一方向性関数に対し、文書ＭとＮ組の前記メッセージとを入力することで選択されたＮ個の第１情報と、Ｎ個の前記第１情報にそれぞれ対応するＮ個の第２情報とで構成される電子署名を取得する署名取得機能と、
前記メッセージ、前記多次多変数多項式の組Ｆ、前記ベクトルｙ、及び前記電子署名に基づいて前記文書Ｍの正当性を検証する署名検証機能と、
をコンピュータに実現させるためのプログラムが記録された、コンピュータにより読み取り可能な記録媒体であり、
前記ベクトルｓは署名鍵であり、
前記多次多変数多項式の組Ｆ及び前記ベクトルｙは公開鍵であり、
前記メッセージは、前記公開鍵及び前記第２情報を利用して、当該第２情報に対応する第１情報の種類に応じて選択される所定の演算を実行することで得られる情報である、
記録媒体。

【図１】