情報処理装置、及び情報処理方法

【課題】より高い安全性を有する公開鍵認証方式を実現すること。
【解決手段】環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ_１，…，ｆ_ｍ）及びベクトルｓ∈Ｋ^ｎに基づいてメッセージを生成し、多次多変数多項式の組Ｆ及びベクトルｙ＝（ｆ_１（ｓ），…，ｆ_ｍ（ｓ））を保持する検証者にメッセージを提供し、ｋ通り（ｋ≧３）の検証パターンの中から検証者が選択した検証パターンに対応する回答情報を検証者に提供し、１つのメッセージについて検証者が２通り以上の検証パターンに対する回答情報を要求してきた場合には回答情報を検証者に提供しない情報処理装置が提供される。ベクトルｓは秘密鍵、多次多変数多項式の組Ｆ及びベクトルｙは公開鍵、メッセージは公開鍵及び回答情報を利用して、当該回答情報に対応する検証パターン用に用意された演算により得られる情報である。

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

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

【図１】