情報処理装置、情報処理方法、プログラム、及び記録媒体

【課題】高い安全性を有し、通信効率の良い公開鍵認証方式を実現すること。
【解決手段】環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ_１，…，ｆ_ｍ）及びベクトルｓ∈Ｋ^ｎに基づいてメッセージを生成し、前記多次多変数多項式の組Ｆ及びベクトルｙ＝（ｆ_１（ｓ），…，ｆ_ｍ（ｓ））を保持する検証者に前記メッセージを提供し、ｋ通り（ｋ≧３）の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する情報処理装置が提供される。また、この情報処理装置は、複数のメッセージを検証者に送る際に、複数のメッセージや複数の情報をハッシュ値に纏めて送信する。

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

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

【図１】