情報処理装置、署名生成装置、情報処理方法、署名生成方法、及びプログラム

【課題】高い安全性を有する効率的な公開鍵認証方式を実現すること。
【解決手段】
環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ_１，…，ｆ_ｍ）及びベクトルｓ∈Ｋ^ｎに基づいてメッセージを生成し、前記多次多変数多項式の組Ｆ及びベクトルｙ＝（ｙ_１，…，ｙ_ｍ）＝（ｆ_１（ｓ），…，ｆ_ｍ（ｓ））を保持する検証者に前記メッセージを提供し、ｋ通り（ｋ≧３）の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する情報処理装置が提供される。但し、前記多次多変数多項式の組Ｆは、ｍ本の３次多項式ｆ_１，…，ｆ_ｍで構成され、Ｇ_１（ｘ_１，ｘ_２）＋Ｇ_２（ｘ_１，ｘ_２）＝Ｆ（ｘ_１＋ｘ_２）−Ｆ（ｘ_１）−Ｆ（ｘ_２）で定義されるＧ_１（ｘ_１，ｘ_２）及びＧ_２（ｘ_１，ｘ_２）がそれぞれｘ_１及びｘ_２に関して加法準同型となるように設定される。

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

【特許請求の範囲】
【請求項１】
環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ_１，…，ｆ_ｍ）及びベクトルｓ∈Ｋ^ｎに基づいてメッセージを生成するメッセージ生成部と、
前記多次多変数多項式の組Ｆ及びベクトルｙ＝（ｙ_１，…，ｙ_ｍ）＝（ｆ_１（ｓ），…，ｆ_ｍ（ｓ））を保持する検証者に前記メッセージを提供するメッセージ提供部と、
ｋ通り（ｋ≧３）の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供部と、
を備え、
前記ベクトルｓは秘密鍵であり、
前記多次多変数多項式の組Ｆ及び前記ベクトルｙは公開鍵であり、
前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Ｆは、ｍ本の３次多項式ｆ_１，…，ｆ_ｍで構成され、Ｇ_１（ｘ_１，ｘ_２）＋Ｇ_２（ｘ_１，ｘ_２）＝Ｆ（ｘ_１＋ｘ_２）−Ｆ（ｘ_１）−Ｆ（ｘ_２）で定義されるＧ_１（ｘ_１，ｘ_２）及びＧ_２（ｘ_１，ｘ_２）がそれぞれｘ_１及びｘ_２に関して加法準同型となるように設定される、
情報処理装置。
【請求項２】
前記メッセージ生成部は、Ｎ回分（Ｎ≧２）のメッセージを生成し、
前記メッセージ提供部は、Ｎ回分の前記メッセージを１回の対話で前記検証者に提供し、
前記回答提供部は、Ｎ回分の前記メッセージのそれぞれについて前記検証者が選択した検証パターンに対応するＮ回分の前記回答情報を１回の対話で前記検証者に提供する、
請求項１に記載の情報処理装置。
【請求項３】
環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ_１，…，ｆ_ｍ）及びベクトルｙ＝（ｙ_１，…，ｙ_ｍ）＝（ｆ_１（ｓ），…，ｆ_ｍ（ｓ））を保持する情報保持部と、
前記多次多変数多項式の組Ｆ及びベクトルｓ∈Ｋ^ｎに基づいて生成されたメッセージを取得するメッセージ取得部と、
前記メッセージを提供した証明者に対し、ｋ通り（ｋ≧３）の検証パターンの中からランダムに選択した１つの検証パターンの情報を提供するパターン情報提供部と、
前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得部と、
前記メッセージ、前記多次多変数多項式の組Ｆ、前記ベクトルｙ、及び前記回答情報に基づいて前記証明者が前記ベクトルｓを保持しているか否かを検証する検証部と、
を備え、
前記ベクトルｓは秘密鍵であり、
前記多次多変数多項式の組Ｆ及び前記ベクトルｙは公開鍵であり、
前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Ｆは、ｍ本の３次多項式ｆ_１，…，ｆ_ｍで構成され、Ｇ_１（ｘ_１，ｘ_２）＋Ｇ_２（ｘ_１，ｘ_２）＝Ｆ（ｘ_１＋ｘ_２）−Ｆ（ｘ_１）−Ｆ（ｘ_２）で定義されるＧ_１（ｘ_１，ｘ_２）及びＧ_２（ｘ_１，ｘ_２）がそれぞれｘ_１及びｘ_２に関して加法準同型となるように設定される、
情報処理装置。
【請求項４】
前記メッセージ取得部は、Ｎ回分（Ｎ≧２）の前記メッセージを１回の対話で取得し、
前記パターン情報提供部は、Ｎ回分の前記メッセージのそれぞれについて検証パターンを選択し、選択したＮ回分の検証パターンの情報を１回の対話で前記証明者に提供し、
前記回答取得部は、前記選択したＮ回分の検証パターンに対応するＮ回分の前記回答情報を１回の対話で前記証明者から取得し、
前記検証部は、Ｎ回分の前記メッセージの全てについて検証が成功した場合に、前記証明者が前記ベクトルｓを保持していると判定する、
請求項３に記載の情報処理装置。
【請求項５】
環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ_１，…，ｆ_ｍ）及びベクトルｓ∈Ｋ^ｎに基づいてメッセージを生成するメッセージ生成部と、
前記多次多変数多項式の組Ｆ及びベクトルｙ＝（ｙ_１，…，ｙ_ｍ）＝（ｆ_１（ｓ），…，ｆ_ｍ（ｓ））を保持する検証者に前記メッセージを提供するメッセージ提供部と、
前記検証者がランダムに選択した第１の情報及び前記メッセージを生成する際に得られる第２の情報を用いて第３の情報を生成する中間情報生成部と、
前記検証者に前記第３の情報を提供する中間情報提供部と、
ｋ通り（ｋ≧２）の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供部と、
を備え、
前記ベクトルｓは秘密鍵であり、
前記多次多変数多項式の組Ｆ及び前記ベクトルｙは公開鍵であり、
前記メッセージは、前記公開鍵、前記第１の情報、前記第３の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Ｆは、ｍ本の３次多項式ｆ_１，…，ｆ_ｍで構成され、Ｇ_１（ｘ_１，ｘ_２）＋Ｇ_２（ｘ_１，ｘ_２）＝Ｆ（ｘ_１＋ｘ_２）−Ｆ（ｘ_１）−Ｆ（ｘ_２）で定義されるＧ_１（ｘ_１，ｘ_２）及びＧ_２（ｘ_１，ｘ_２）がそれぞれｘ_１及びｘ_２に関して線形となるように設定される、
情報処理装置。
【請求項６】
前記メッセージ生成部は、Ｎ回分（Ｎ≧２）のメッセージを生成し、
前記メッセージ提供部は、Ｎ回分の前記メッセージを１回の対話で前記検証者に提供し、
前記中間情報生成部は、Ｎ回分の前記メッセージのそれぞれについて前記検証者が選択した前記第１の情報及び前記メッセージを生成する際に得られるＮ回分の前記第２の情報を用いてＮ回分の前記第３の情報を生成し、
前記中間情報提供部は、Ｎ回分の前記第３の情報を１回の対話で検証者に提供し、
前記回答提供部は、Ｎ回分の前記メッセージのそれぞれについて前記検証者が選択した検証パターンに対応するＮ回分の前記回答情報を１回の対話で前記検証者に提供する、
請求項５に記載の情報処理装置。
【請求項７】
環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ_１，…，ｆ_ｍ）及びベクトルｙ＝（ｙ_１，…，ｙ_ｍ）＝（ｆ_１（ｓ），…，ｆ_ｍ（ｓ））を保持する情報保持部と、
前記多次多変数多項式の組Ｆ及びベクトルｓ∈Ｋ^ｎに基づいて生成されたメッセージを取得するメッセージ取得部と、
前記メッセージを提供した証明者に対し、ランダムに選択した第１の情報を提供する情報提供部と、
前記第１の情報及び前記メッセージを生成する際に得られる第２の情報を用いて前記証明者が生成した第３の情報を取得する中間情報取得部と、
ｋ通り（ｋ≧３）の検証パターンの中からランダムに選択した１つの検証パターンの情報を前記証明者に提供するパターン情報提供部と、
前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得部と、
前記メッセージ、前記第１の情報、前記第３の情報、前記多次多変数多項式の組Ｆ、及び前記回答情報に基づいて前記証明者が前記ベクトルｓを保持しているか否かを検証する検証部と、
を備え、
前記ベクトルｓは秘密鍵であり、
前記多次多変数多項式の組Ｆ及び前記ベクトルｙは公開鍵であり、
前記メッセージは、前記公開鍵、前記第１の情報、前記第３の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Ｆは、ｍ本の３次多項式ｆ_１，…，ｆ_ｍで構成され、Ｇ_１（ｘ_１，ｘ_２）＋Ｇ_２（ｘ_１，ｘ_２）＝Ｆ（ｘ_１＋ｘ_２）−Ｆ（ｘ_１）−Ｆ（ｘ_２）で定義されるＧ_１（ｘ_１，ｘ_２）及びＧ_２（ｘ_１，ｘ_２）がそれぞれｘ_１及びｘ_２に関して線形となるように設定される、
情報処理装置。
【請求項８】
前記メッセージ取得部は、Ｎ回分（Ｎ≧２）の前記メッセージを１回の対話で取得し、
前記情報提供部は、Ｎ回分の前記メッセージのそれぞれについて前記第１の情報をランダムに選択し、選択したＮ回分の前記第１の情報を１回の対話で前記証明者に提供し、
前記中間情報取得部は、Ｎ回分の前記第１の情報及びＮ回分の前記メッセージを生成する際に得られるＮ回分の前記第２の情報を用いて前記証明者が生成したＮ回分の前記第３の情報を取得し、
前記パターン情報提供部は、Ｎ回分の前記メッセージのそれぞれについて検証パターンを選択し、選択したＮ回分の検証パターンの情報を１回の対話で前記証明者に提供し、
前記回答取得部は、前記選択したＮ回分の検証パターンに対応するＮ回分の前記回答情報を１回の対話で前記証明者から取得し、
前記検証部は、Ｎ回分の前記メッセージの全てについて検証が成功した場合に、前記証明者が前記ベクトルｓを保持していると判定する、
請求項７に記載の情報処理装置。
【請求項９】
環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ_１，…，ｆ_ｍ）及びベクトルｓ∈Ｋ^ｎに基づいてメッセージを生成するメッセージ生成部と、
前記多次多変数多項式の組Ｆ及びベクトルｙ＝（ｙ_１，…，ｙ_ｍ）＝（ｆ_１（ｓ），…，ｆ_ｍ（ｓ））を保持する検証者に前記メッセージを提供するメッセージ提供部と、
文書Ｍ及び前記メッセージを一方向性関数に入力して得られる数値に基づき、ｋ通り（ｋ≧３）の検証パターンの中から１つの検証パターンを選択するパターン選択部と、
選択した前記検証パターンに対応する回答情報を生成する回答生成部と、
署名として、前記メッセージ及び前記回答情報を前記検証者に提供する署名提供部と、
を備え、
前記ベクトルｓは秘密鍵であり、
前記多次多変数多項式の組Ｆ及び前記ベクトルｙは公開鍵であり、
前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Ｆは、ｍ本の３次多項式ｆ_１，…，ｆ_ｍで構成され、Ｇ_１（ｘ_１，ｘ_２）＋Ｇ_２（ｘ_１，ｘ_２）＝Ｆ（ｘ_１＋ｘ_２）−Ｆ（ｘ_１）−Ｆ（ｘ_２）で定義されるＧ_１（ｘ_１，ｘ_２）及びＧ_２（ｘ_１，ｘ_２）がそれぞれｘ_１及びｘ_２に関して加法準同型となるように設定される、
署名生成装置。
【請求項１０】
環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ_１，…，ｆ_ｍ）及びベクトルｓ∈Ｋ^ｎに基づいてメッセージを生成するステップと、
前記多次多変数多項式の組Ｆ及びベクトルｙ＝（ｙ_１，…，ｙ_ｍ）＝（ｆ_１（ｓ），…，ｆ_ｍ（ｓ））を保持する検証者に前記メッセージを提供するステップと、
ｋ通り（ｋ≧３）の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供するステップと、
を含み、
前記ベクトルｓは秘密鍵であり、
前記多次多変数多項式の組Ｆ及び前記ベクトルｙは公開鍵であり、
前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Ｆは、ｍ本の３次多項式ｆ_１，…，ｆ_ｍで構成され、Ｇ_１（ｘ_１，ｘ_２）＋Ｇ_２（ｘ_１，ｘ_２）＝Ｆ（ｘ_１＋ｘ_２）−Ｆ（ｘ_１）−Ｆ（ｘ_２）で定義されるＧ_１（ｘ_１，ｘ_２）及びＧ_２（ｘ_１，ｘ_２）がそれぞれｘ_１及びｘ_２に関して加法準同型となるように設定される、
情報処理方法。
【請求項１１】
環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ_１，…，ｆ_ｍ）及びベクトルｙ＝（ｙ_１，…，ｙ_ｍ）＝（ｆ_１（ｓ），…，ｆ_ｍ（ｓ））を保持する情報処理装置が、
前記多次多変数多項式の組Ｆ及びベクトルｓ∈Ｋ^ｎに基づいて生成されたメッセージを取得するステップと、
前記メッセージを提供した証明者に対し、ｋ通り（ｋ≧３）の検証パターンの中からランダムに選択した１つの検証パターンの情報を提供するステップと、
前記選択した検証パターンに対応する回答情報を前記証明者から取得するステップと、
前記メッセージ、前記多次多変数多項式の組Ｆ、前記ベクトルｙ、及び前記回答情報に基づいて前記証明者が前記ベクトルｓを保持しているか否かを検証するステップと、
を含み、
前記ベクトルｓは秘密鍵であり、
前記多次多変数多項式の組Ｆ及び前記ベクトルｙは公開鍵であり、
前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Ｆは、ｍ本の３次多項式ｆ_１，…，ｆ_ｍで構成され、Ｇ_１（ｘ_１，ｘ_２）＋Ｇ_２（ｘ_１，ｘ_２）＝Ｆ（ｘ_１＋ｘ_２）−Ｆ（ｘ_１）−Ｆ（ｘ_２）で定義されるＧ_１（ｘ_１，ｘ_２）及びＧ_２（ｘ_１，ｘ_２）がそれぞれｘ_１及びｘ_２に関して加法準同型となるように設定される、
情報処理方法。
【請求項１２】
環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ_１，…，ｆ_ｍ）及びベクトルｓ∈Ｋ^ｎに基づいてメッセージを生成するステップと、
前記多次多変数多項式の組Ｆ及びベクトルｙ＝（ｙ_１，…，ｙ_ｍ）＝（ｆ_１（ｓ），…，ｆ_ｍ（ｓ））を保持する検証者に前記メッセージを提供するステップと、
前記検証者がランダムに選択した第１の情報及び前記メッセージを生成する際に得られる第２の情報を用いて第３の情報を生成するステップと、
前記検証者に前記第３の情報を提供するステップと、
ｋ通り（ｋ≧２）の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供するステップと、
を含み、
前記ベクトルｓは秘密鍵であり、
前記多次多変数多項式の組Ｆ及び前記ベクトルｙは公開鍵であり、
前記メッセージは、前記公開鍵、前記第１の情報、前記第３の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Ｆは、ｍ本の３次多項式ｆ_１，…，ｆ_ｍで構成され、Ｇ_１（ｘ_１，ｘ_２）＋Ｇ_２（ｘ_１，ｘ_２）＝Ｆ（ｘ_１＋ｘ_２）−Ｆ（ｘ_１）−Ｆ（ｘ_２）で定義されるＧ_１（ｘ_１，ｘ_２）及びＧ_２（ｘ_１，ｘ_２）がそれぞれｘ_１及びｘ_２に関して線形となるように設定される、
情報処理方法。
【請求項１３】
環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ_１，…，ｆ_ｍ）及びベクトルｙ＝（ｙ_１，…，ｙ_ｍ）＝（ｆ_１（ｓ），…，ｆ_ｍ（ｓ））を保持する情報処理装置が、
前記多次多変数多項式の組Ｆ及びベクトルｓ∈Ｋ^ｎに基づいて生成されたメッセージを取得するステップと、
前記メッセージを提供した証明者に対し、ランダムに選択した第１の情報を提供するステップと、
前記第１の情報及び前記メッセージを生成する際に得られる第２の情報を用いて前記証明者が生成した第３の情報を取得するステップと、
ｋ通り（ｋ≧３）の検証パターンの中からランダムに選択した１つの検証パターンの情報を前記証明者に提供するステップと、
前記選択した検証パターンに対応する回答情報を前記証明者から取得するステップと、
前記メッセージ、前記第１の情報、前記第３の情報、前記多次多変数多項式の組Ｆ、及び前記回答情報に基づいて前記証明者が前記ベクトルｓを保持しているか否かを検証するステップと、
を含み、
前記ベクトルｓは秘密鍵であり、
前記多次多変数多項式の組Ｆ及び前記ベクトルｙは公開鍵であり、
前記メッセージは、前記公開鍵、前記第１の情報、前記第３の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Ｆは、ｍ本の３次多項式ｆ_１，…，ｆ_ｍで構成され、Ｇ_１（ｘ_１，ｘ_２）＋Ｇ_２（ｘ_１，ｘ_２）＝Ｆ（ｘ_１＋ｘ_２）−Ｆ（ｘ_１）−Ｆ（ｘ_２）で定義されるＧ_１（ｘ_１，ｘ_２）及びＧ_２（ｘ_１，ｘ_２）がそれぞれｘ_１及びｘ_２に関して線形となるように設定される、
情報処理方法。
【請求項１４】
環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ_１，…，ｆ_ｍ）及びベクトルｓ∈Ｋ^ｎに基づいてメッセージを生成するステップと、
前記多次多変数多項式の組Ｆ及びベクトルｙ＝（ｙ_１，…，ｙ_ｍ）＝（ｆ_１（ｓ），…，ｆ_ｍ（ｓ））を保持する検証者に前記メッセージを提供するステップと、
文書Ｍ及び前記メッセージを一方向性関数に入力して得られる数値に基づき、ｋ通り（ｋ≧３）の検証パターンの中から１つの検証パターンを選択するステップと、
選択した前記検証パターンに対応する回答情報を生成するステップと、
署名として、前記メッセージ及び前記回答情報を前記検証者に提供するステップと、
を含み、
前記ベクトルｓは秘密鍵であり、
前記多次多変数多項式の組Ｆ及び前記ベクトルｙは公開鍵であり、
前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Ｆは、ｍ本の３次多項式ｆ_１，…，ｆ_ｍで構成され、Ｇ_１（ｘ_１，ｘ_２）＋Ｇ_２（ｘ_１，ｘ_２）＝Ｆ（ｘ_１＋ｘ_２）−Ｆ（ｘ_１）−Ｆ（ｘ_２）で定義されるＧ_１（ｘ_１，ｘ_２）及びＧ_２（ｘ_１，ｘ_２）がそれぞれｘ_１及びｘ_２に関して加法準同型となるように設定される、
署名生成方法。
【請求項１５】
環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ_１，…，ｆ_ｍ）及びベクトルｓ∈Ｋ^ｎに基づいてメッセージを生成するメッセージ生成機能と、
前記多次多変数多項式の組Ｆ及びベクトルｙ＝（ｙ_１，…，ｙ_ｍ）＝（ｆ_１（ｓ），…，ｆ_ｍ（ｓ））を保持する検証者に前記メッセージを提供するメッセージ提供機能と、
ｋ通り（ｋ≧３）の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供機能と、
をコンピュータに実現させるためのプログラムであり、
前記ベクトルｓは秘密鍵であり、
前記多次多変数多項式の組Ｆ及び前記ベクトルｙは公開鍵であり、
前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Ｆは、ｍ本の３次多項式ｆ_１，…，ｆ_ｍで構成され、Ｇ_１（ｘ_１，ｘ_２）＋Ｇ_２（ｘ_１，ｘ_２）＝Ｆ（ｘ_１＋ｘ_２）−Ｆ（ｘ_１）−Ｆ（ｘ_２）で定義されるＧ_１（ｘ_１，ｘ_２）及びＧ_２（ｘ_１，ｘ_２）がそれぞれｘ_１及びｘ_２に関して加法準同型となるように設定される、
プログラム。
【請求項１６】
環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ_１，…，ｆ_ｍ）及びベクトルｙ＝（ｙ_１，…，ｙ_ｍ）＝（ｆ_１（ｓ），…，ｆ_ｍ（ｓ））を保持する情報保持機能と、
前記多次多変数多項式の組Ｆ及びベクトルｓ∈Ｋ^ｎに基づいて生成されたメッセージを取得するメッセージ取得機能と、
前記メッセージを提供した証明者に対し、ｋ通り（ｋ≧３）の検証パターンの中からランダムに選択した１つの検証パターンの情報を提供するパターン情報提供機能と、
前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得機能と、
前記メッセージ、前記多次多変数多項式の組Ｆ、前記ベクトルｙ、及び前記回答情報に基づいて前記証明者が前記ベクトルｓを保持しているか否かを検証する検証機能と、
をコンピュータに実現させるためのプログラムであり、
前記ベクトルｓは秘密鍵であり、
前記多次多変数多項式の組Ｆ及び前記ベクトルｙは公開鍵であり、
前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Ｆは、ｍ本の３次多項式ｆ_１，…，ｆ_ｍで構成され、Ｇ_１（ｘ_１，ｘ_２）＋Ｇ_２（ｘ_１，ｘ_２）＝Ｆ（ｘ_１＋ｘ_２）−Ｆ（ｘ_１）−Ｆ（ｘ_２）で定義されるＧ_１（ｘ_１，ｘ_２）及びＧ_２（ｘ_１，ｘ_２）がそれぞれｘ_１及びｘ_２に関して加法準同型となるように設定される、
プログラム。
【請求項１７】
環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ_１，…，ｆ_ｍ）及びベクトルｓ∈Ｋ^ｎに基づいてメッセージを生成するメッセージ生成機能と、
前記多次多変数多項式の組Ｆ及びベクトルｙ＝（ｙ_１，…，ｙ_ｍ）＝（ｆ_１（ｓ），…，ｆ_ｍ（ｓ））を保持する検証者に前記メッセージを提供するメッセージ提供機能と、
前記検証者がランダムに選択した第１の情報及び前記メッセージを生成する際に得られる第２の情報を用いて第３の情報を生成する中間情報生成機能と、
前記検証者に前記第３の情報を提供する中間情報提供機能と、
ｋ通り（ｋ≧２）の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供機能と、
をコンピュータに実現させるためのプログラムであり、
前記ベクトルｓは秘密鍵であり、
前記多次多変数多項式の組Ｆ及び前記ベクトルｙは公開鍵であり、
前記メッセージは、前記公開鍵、前記第１の情報、前記第３の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Ｆは、ｍ本の３次多項式ｆ_１，…，ｆ_ｍで構成され、Ｇ_１（ｘ_１，ｘ_２）＋Ｇ_２（ｘ_１，ｘ_２）＝Ｆ（ｘ_１＋ｘ_２）−Ｆ（ｘ_１）−Ｆ（ｘ_２）で定義されるＧ_１（ｘ_１，ｘ_２）及びＧ_２（ｘ_１，ｘ_２）がそれぞれｘ_１及びｘ_２に関して線形となるように設定される、
プログラム。
【請求項１８】
環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ_１，…，ｆ_ｍ）及びベクトルｙ＝（ｙ_１，…，ｙ_ｍ）＝（ｆ_１（ｓ），…，ｆ_ｍ（ｓ））を保持する情報保持機能と、
前記多次多変数多項式の組Ｆ及びベクトルｓ∈Ｋ^ｎに基づいて生成されたメッセージを取得するメッセージ取得機能と、
前記メッセージを提供した証明者に対し、ランダムに選択した第１の情報を提供する情報提供機能と、
前記第１の情報及び前記メッセージを生成する際に得られる第２の情報を用いて前記証明者が生成した第３の情報を取得する中間情報取得機能と、
ｋ通り（ｋ≧３）の検証パターンの中からランダムに選択した１つの検証パターンの情報を前記証明者に提供するパターン情報提供機能と、
前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得機能と、
前記メッセージ、前記第１の情報、前記第３の情報、前記多次多変数多項式の組Ｆ、及び前記回答情報に基づいて前記証明者が前記ベクトルｓを保持しているか否かを検証する検証機能と、
をコンピュータに実現させるためのプログラムであり、
前記ベクトルｓは秘密鍵であり、
前記多次多変数多項式の組Ｆ及び前記ベクトルｙは公開鍵であり、
前記メッセージは、前記公開鍵、前記第１の情報、前記第３の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Ｆは、ｍ本の３次多項式ｆ_１，…，ｆ_ｍで構成され、Ｇ_１（ｘ_１，ｘ_２）＋Ｇ_２（ｘ_１，ｘ_２）＝Ｆ（ｘ_１＋ｘ_２）−Ｆ（ｘ_１）−Ｆ（ｘ_２）で定義されるＧ_１（ｘ_１，ｘ_２）及びＧ_２（ｘ_１，ｘ_２）がそれぞれｘ_１及びｘ_２に関して線形となるように設定される、
プログラム。
【請求項１９】
環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ_１，…，ｆ_ｍ）及びベクトルｓ∈Ｋ^ｎに基づいてメッセージを生成するメッセージ生成機能と、
前記多次多変数多項式の組Ｆ及びベクトルｙ＝（ｙ_１，…，ｙ_ｍ）＝（ｆ_１（ｓ），…，ｆ_ｍ（ｓ））を保持する検証者に前記メッセージを提供するメッセージ提供機能と、
文書Ｍ及び前記メッセージを一方向性関数に入力して得られる数値に基づき、ｋ通り（ｋ≧３）の検証パターンの中から１つの検証パターンを選択するパターン選択機能と、
選択した前記検証パターンに対応する回答情報を生成する回答生成機能と、
署名として、前記メッセージ及び前記回答情報を前記検証者に提供する署名提供機能と、
をコンピュータに実現させるためのプログラムであり、
前記ベクトルｓは秘密鍵であり、
前記多次多変数多項式の組Ｆ及び前記ベクトルｙは公開鍵であり、
前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記多次多変数多項式の組Ｆは、ｍ本の３次多項式ｆ_１，…，ｆ_ｍで構成され、Ｇ_１（ｘ_１，ｘ_２）＋Ｇ_２（ｘ_１，ｘ_２）＝Ｆ（ｘ_１＋ｘ_２）−Ｆ（ｘ_１）−Ｆ（ｘ_２）で定義されるＧ_１（ｘ_１，ｘ_２）及びＧ_２（ｘ_１，ｘ_２）がそれぞれｘ_１及びｘ_２に関して加法準同型となるように設定される、
プログラム。

【図１】