【手続補正書】
【提出日】平成27年2月23日(2015.2.23)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
多次多変数多項式の組Ｆ＝（ｆ１，…，ｆｍ）を含む公開鍵を利用した公開鍵認証方式又は電子署名方式のアルゴリズムを実行するエンティティの間で共有されている情報から所定の関数を用いて、前記多次多変数多項式の組Ｆを構成する各項の係数に利用する数を生成する数生成部と、
前記数生成部が生成した数を、前記多次多変数多項式の組Ｆを構成要素に含む多次多変数多項式の係数に割り当てる割当部と、
を備え、
前記割当部は、前記多次多変数多項式の組Ｆを構成要素に含む多次多変数多項式の係数のうち、複数の、変数の組み合わせの種類が同じ項の係数をグループ化しておき、割り当て処理をグループ単位で実行する、
情報処理装置。
【請求項２】
多次多変数多項式の組Ｆ＝（ｆ１，…，ｆｍ）を含む公開鍵を利用した公開鍵認証方式又は電子署名方式のアルゴリズムを実行するエンティティの間で共有されている情報から所定の関数を用いて、前記多次多変数多項式の組Ｆを構成する各項の係数に利用する数を生成する数生成部と、
前記数生成部が生成した数を、前記多次多変数多項式の組Ｆを構成要素に含む多次多変数多項式の係数に割り当てる割当部と、
を備え、
前記割当部は、前記多次多変数多項式の組Ｆを構成要素に含む多次多変数多項式を２次形式で表現した場合の係数行列を行又は列毎にグループ化しておき、割り当て処理をグループ単位で実行する、
情報処理装置。
【請求項３】
前記数生成部は、前記割当部が１つのグループに対する割り当て処理を実行する際に、当該１つのグループに属する係数の分だけ前記数を生成する、
請求項１または２に記載の情報処理装置。
【請求項４】
前記数生成部は、前記１つのグループに属する係数の分だけ前記数を生成する際、１つの数を生成し、生成した数を１ビットずつローテーションして所要数の数を生成する、
請求項３に記載の情報処理装置。
【請求項５】
前記各グループに対応する種類の項に前記係数を割り当て、当該項の変数に任意の数を代入した値をテーブルとして保持するテーブル保持部をさらに備える、
請求項１または２に記載の情報処理装置。
【請求項６】
多次多変数多項式の組Ｆ＝（ｆ１，…，ｆｍ）を含む公開鍵を利用した公開鍵認証方式又は電子署名方式のアルゴリズムを実行するエンティティの間で共有されている情報から所定の関数を用いて前記多次多変数多項式の組Ｆを構成する各項の係数と同じ数だけ数を生成する数生成部と、
証明者と認証者との間で予め決められた順序で前記数生成部が生成した数を、前記多次多変数多項式の組Ｆを構成要素に含む多次多変数多項式の係数に割り当てる割当部と、
を備える、
情報処理装置。
【請求項７】
前記情報は、乱数のシードであり、
前記所定の関数は、前記シードを利用して乱数を生成する乱数生成器である、
請求項１〜６のいずれかに記載の情報処理装置。
【請求項８】
環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ１，…，ｆｍ）、及びベクトルｓ∈Ｋｎに基づいてメッセージを生成するメッセージ生成部と、
前記多次多変数多項式の組Ｆ及びベクトルｙ＝（ｙ１，…，ｙｍ）＝（ｆ１（ｓ），…，ｆｍ（ｓ））を保持する検証者に前記メッセージを提供するメッセージ提供部と、
ｋ通り（ｋ≧３）の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供部と、
を備え、
前記ベクトルｓは秘密鍵であり、
前記多次多変数多項式の組Ｆ及び前記ベクトルｙは公開鍵であり、
前記回答情報は、乱数の組及び前記メッセージの中から前記検証パターンに応じて選択される情報であり、
前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報である、
請求項１〜７のいずれかに記載の情報処理装置。
【請求項９】
環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ１，…，ｆｍ）及びベクトルｙ＝（ｙ１，…，ｙｍ）＝（ｆ１（ｓ），…，ｆｍ（ｓ））を保持する情報保持部と、
前記多次多変数多項式の組Ｆ及びベクトルｓ∈Ｋｎに基づいて生成されたメッセージを取得するメッセージ取得部と、
前記メッセージを提供した証明者に対し、ｋ通り（ｋ≧３）の検証パターンの中からランダムに選択した１つの検証パターンの情報を提供するパターン情報提供部と、
前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得部と、
前記メッセージ、前記多次多変数多項式の組Ｆ、前記ベクトルｙ、及び前記回答情報に基づいて前記証明者が前記ベクトルｓを保持しているか否かを検証する検証部と、
を備え、
前記ベクトルｓは秘密鍵であり、
前記多次多変数多項式の組Ｆ及び前記ベクトルｙは公開鍵であり、
前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報である、
請求項１〜７のいずれかに記載の情報処理装置。
【請求項１０】
環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ１，…，ｆｍ）、及びベクトルｓ∈Ｋｎに基づいてメッセージを生成するメッセージ生成部と、
前記多次多変数多項式の組Ｆ及びベクトルｙ＝（ｙ１，…，ｙｍ）＝（ｆ１（ｓ），…，ｆｍ（ｓ））を保持する検証者に前記メッセージを提供するメッセージ提供部と、
前記検証者がランダムに選択した第１の情報及び前記メッセージを生成する際に得られる第２の情報を用いて第３の情報を生成する中間情報生成部と、
前記検証者に前記第３の情報を提供する中間情報提供部と、
ｋ通り（ｋ≧２）の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供部と、
を備え、
前記ベクトルｓは秘密鍵であり、
前記多次多変数多項式の組Ｆ及び前記ベクトルｙは公開鍵であり、
前記回答情報は、前記メッセージの中から前記検証パターンに応じて選択される情報であり、
前記メッセージは、前記公開鍵、前記第１の情報、前記第３の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報である、
請求項１〜７のいずれかに記載の情報処理装置。
【請求項１１】
環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ１，…，ｆｍ）及びベクトルｙ＝（ｙ１，…，ｙｍ）＝（ｆ１（ｓ），…，ｆｍ（ｓ））を保持する情報保持部と、
前記多次多変数多項式の組Ｆ及びベクトルｓ∈Ｋｎに基づいて生成されたメッセージを取得するメッセージ取得部と、
前記メッセージを提供した証明者に対し、ランダムに選択した第１の情報を提供する情報提供部と、
前記第１の情報及び前記メッセージを生成する際に得られる第２の情報を用いて前記証明者が生成した第３の情報を取得する中間情報取得部と、
ｋ通り（ｋ≧２）の検証パターンの中からランダムに選択した１つの検証パターンの情報を前記証明者に提供するパターン情報提供部と、
前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得部と、
前記メッセージ、前記第１の情報、前記第３の情報、前記多次多変数多項式の組Ｆ、及び前記回答情報に基づいて前記証明者が前記ベクトルｓを保持しているか否かを検証する検証部と、
を備え、
前記ベクトルｓは秘密鍵であり、
前記多次多変数多項式の組Ｆ及び前記ベクトルｙは公開鍵であり、
前記メッセージは、前記公開鍵、前記第１の情報、前記第３の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報である、
請求項１〜７のいずれかに記載の情報処理装置。
【請求項１２】
前記アルゴリズムが複数回繰り返し実行される場合において、前記数生成部は１回だけ前記数を生成し、前記割当部は１回だけ前記割り当て処理を実行し、
前記アルゴリズムは、前記割当部が割り当てた係数を繰り返し利用する、
請求項１または２に記載の情報処理装置。
【請求項１３】
環Ｋ上で定義される多次多変数多項式の組Ｆ＝（ｆ１，…，ｆｍ）、及び署名鍵ｓ∈Ｋｎを用いて文書Ｍに対する電子署名を生成する署名生成部と、
前記多次多変数多項式の組Ｆ及びベクトルｙ＝（ｆ１（ｓ），…，ｆｍ（ｓ））を保持する検証者へと前記電子署名を提供する署名提供部と、
を備える、
請求項１〜７のいずれかに記載の情報処理装置。
【請求項１４】
多次多変数多項式の組Ｆ＝（ｆ１，…，ｆｍ）を含む公開鍵を利用した公開鍵認証方式又は電子署名方式のアルゴリズムを実行するエンティティの間で共有されている情報から所定の関数を用いて、前記多次多変数多項式の組Ｆを構成する各項の係数に利用する数を生成するステップと、
生成した数を、前記多次多変数多項式の組Ｆを構成要素に含む多次多変数多項式の係数に割り当てるステップと、
を含み、
前記割り当てるステップでは、前記多次多変数多項式の組Ｆを構成要素に含む多次多変数多項式の係数のうち、複数の、変数の組み合わせの種類が同じ項の係数をグループ化しておき、割り当て処理をグループ単位で実行する、
情報処理方法。
【請求項１５】
多次多変数多項式の組Ｆ＝（ｆ１，…，ｆｍ）を含む公開鍵を利用した公開鍵認証方式又は電子署名方式のアルゴリズムを実行するエンティティの間で共有されている情報から所定の関数を用いて、前記多次多変数多項式の組Ｆを構成する各項の係数に利用する数を生成するステップと、
生成した数を、前記多次多変数多項式の組Ｆを構成要素に含む多次多変数多項式の係数に割り当てるステップと、
を含み、
前記割り当てるステップでは、前記多次多変数多項式の組Ｆを構成要素に含む多次多変数多項式を２次形式で表現した場合の係数行列を行又は列毎にグループ化しておき、割り当て処理をグループ単位で実行する、
情報処理方法。
【請求項１６】
多次多変数多項式の組Ｆ＝（ｆ１，…，ｆｍ）を含む公開鍵を利用した公開鍵認証方式又は電子署名方式のアルゴリズムを実行するエンティティの間で共有されている情報から所定の関数を用いて前記多次多変数多項式の組Ｆを構成する各項の係数と同じ数だけ数を生成するステップと、
証明者と認証者との間で予め決められた順序で、前記生成された数を、前記多次多変数多項式の組Ｆを構成要素に含む多次多変数多項式の係数に割り当てるステップと、
を含む、
情報処理方法。
【請求項１７】
多次多変数多項式の組Ｆ＝（ｆ１，…，ｆｍ）を含む公開鍵を利用した公開鍵認証方式又は電子署名方式のアルゴリズムを実行するエンティティの間で共有されている情報から所定の関数を用いて、前記多次多変数多項式の組Ｆを構成する各項の係数に利用する数を生成する数生成機能と、
前記数生成機能が生成した数を、前記多次多変数多項式の組Ｆを構成要素に含む多次多変数多項式の係数に割り当てる割当機能と、
をコンピュータに実現させるためのプログラムであり、
前記割当機能は、前記多次多変数多項式の組Ｆを構成要素に含む多次多変数多項式の係数のうち、複数の、変数の組み合わせの種類が同じ項の係数をグループ化しておき、割り当て処理をグループ単位で実行する、
プログラム。
【請求項１８】
多次多変数多項式の組Ｆ＝（ｆ１，…，ｆｍ）を含む公開鍵を利用した公開鍵認証方式又は電子署名方式のアルゴリズムを実行するエンティティの間で共有されている情報から所定の関数を用いて、前記多次多変数多項式の組Ｆを構成する各項の係数に利用する数を生成する数生成機能と、
前記数生成機能が生成した数を、前記多次多変数多項式の組Ｆを構成要素に含む多次多変数多項式の係数に割り当てる割当機能と、
をコンピュータに実現させるためのプログラムであり、
前記割当機能は、前記多次多変数多項式の組Ｆを構成要素に含む多次多変数多項式を２次形式で表現した場合の係数行列を行又は列毎にグループ化しておき、割り当て処理をグループ単位で実行する、
プログラム。
【請求項１９】
多次多変数多項式の組Ｆ＝（ｆ１，…，ｆｍ）を含む公開鍵を利用した公開鍵認証方式又は電子署名方式のアルゴリズムを実行するエンティティの間で共有されている情報から所定の関数を用いて前記多次多変数多項式の組Ｆを構成する各項の係数と同じ数だけ数を生成する数生成機能と、
証明者と認証者との間で予め決められた順序で、前記生成された数を、前記多次多変数多項式の組Ｆを構成要素に含む多次多変数多項式の係数に割り当てる割当機能と、
をコンピュータに実現させるためのプログラム。
【請求項２０】
請求項１９に記載のプログラムが記録された、コンピュータにより読み取り可能な記録媒体。