【手続補正書】
【提出日】平成26年2月10日(2014.2.10)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ｓ∈Ｋｎを秘密鍵に設定し、環Ｋ上の多次多項式ｆｉ（ｘ１，…，ｘｎ）（ｉ＝１〜ｍ）を公開鍵またはシステムパラメータ、及びｙｉ＝ｆｉ（ｓ）を公開鍵に設定する鍵設定部と、
検証者に対してメッセージｃを送信するメッセージ送信部と、
１つの前記メッセージｃに対するｋ通り（ｋ≧３）の検証パターンの中から前記検証者により選択された１つの検証パターンの情報を受信する検証パターン受信部と、
ｋ通りの回答情報の中から、前記検証パターン受信部により受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信部と、
を備え、
前記回答情報は、前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対するｋ通りの検証パターンが全て成功した場合に秘密鍵ｓが計算可能となる情報である、
認証装置。
【請求項２】
前記メッセージ送信部により単数又は複数のメッセージｃを送信する第１ステップ、それぞれのメッセージｃに対して前記検証パターン受信部により前記検証者からそれぞれ検証パターンの情報を受信する第２ステップ、それぞれの検証パターンの情報に対して前記回答送信部により回答情報を送信する第３ステップを実行し、前記検証者により全ての回答情報で検証が成功した場合に認証が成功する、
請求項１に記載の認証装置。
【請求項３】
前記メッセージ送信部により単数又は複数のメッセージｃを送信する第１ステップ、それぞれのメッセージｃに対して前記検証パターン受信部により前記検証者からそれぞれ検証パターンの情報を受信する第２ステップ、それぞれの検証パターンの情報に対して前記回答送信部により回答情報を送信する第３ステップを実行する処理を繰り返し、
前記第１〜第３ステップを所定回数実行した結果、前記検証者により毎回全ての回答情報で検証が成功した場合に認証が成功する、
請求項２に記載の認証装置。
【請求項４】
前記メッセージｃがｃ＝（ｃ１，…，ｃｍ）である場合、
前記メッセージ送信部は、一方向性関数Ｈを用いて新たなメッセージｃ’＝Ｈ（ｃ）を算出して、前記検証者に対してメッセージｃ’を送信し、
前記回答送信部は、前記回答情報と共に、当該回答情報を利用しても前記検証者が復元することができないメッセージｃの要素を送信する、
請求項２又は３に記載の認証装置。
【請求項５】
ｓ∈Ｋｎが秘密鍵に設定され、環Ｋ上の多次多項式ｆｉ（ｘ１，…，ｘｎ）（ｉ＝１〜ｍ）が公開鍵またはシステムパラメータ、及びｙｉ＝ｆｉ（ｓ）が公開鍵に設定されており、
証明者からメッセージｃを受信するメッセージ受信部と、
１つの前記メッセージｃに対するｋ通り（ｋ≧３）の検証パターンの中から１つの検証パターンを選択する検証パターン選択部と、
前記検証パターン選択部により選択された検証パターンの情報を前記証明者に対して送信する検証パターン送信部と、
ｋ通りの回答情報の中から、前記検証パターン送信部により送信された検証パターンの情報に対応する回答情報を前記証明者から受信する回答受信部と、
前記メッセージ受信部により受信されたメッセージｃ、及び前記回答受信部により受信された回答情報を用いて前記証明者の正当性を検証する検証部と、
を備え、
前記回答情報は、前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対するｋ通りの検証パターンが全て成功した場合に秘密鍵ｓが計算可能となる情報である、
認証装置。
【請求項６】
ｓ∈Ｋｎを秘密鍵に設定し、環Ｋ上の多次多項式ｆｉ（ｘ１，…，ｘｎ）（ｉ＝１〜ｍ）を公開鍵またはシステムパラメータ、及びｙｉ＝ｆｉ（ｓ）を公開鍵に設定する鍵設定部と、
検証者に対してメッセージｃを送信するメッセージ送信部と、
前記検証者から応答αを受信する応答受信部と、
前記応答受信部により受信された応答αを用いて、前記メッセージｃに対する検証に利用される多項式ｆ”を生成する多項式生成部と、
前記多項式生成部により生成された多項式ｆ”を前記検証者に送信する多項式送信部と、
１つの前記メッセージｃに対するｋ通り（ｋ≧２）の検証パターンの中から前記検証者により選択された１つの検証パターンの情報を受信する検証パターン受信部と、
ｋ通りの回答情報の中から、前記検証パターン受信部により受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信部と、
を備え、
前記回答情報は、２通りの前記応答α、前記多項式ｆ”及び前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対する計２ｋ通りの応答と検証パターンの組合せが全て成功した場合に秘密鍵ｓが計算可能となる情報である、
認証装置。
【請求項７】
前記メッセージ送信部により単数又は複数のメッセージｃを送信する第１ステップ、それぞれのメッセージｃに対して前記応答受信部から応答αを受信する第２ステップ、当該第２ステップで受信した応答αを用いて前記多項式生成部によりそれぞれ多項式ｆ”を生成し、前記多項式送信部により当該多項式ｆ”を送信する第３ステップ、それぞれのメッセージｃに対して前記検証パターン受信部により前記検証者からそれぞれ検証パターンの情報を受信する第４ステップ、それぞれの検証パターンの情報に対して前記回答送信部により回答情報を送信する第５ステップを実行し、前記検証者により全ての回答情報で検証が成功した場合に認証が成功する、
請求項６に記載の認証装置。
【請求項８】
前記メッセージ送信部により単数又は複数のメッセージｃを送信する第１ステップ、それぞれのメッセージｃに対して前記応答受信部から応答αを受信する第２ステップ、当該第２ステップで受信した応答αを用いて前記多項式生成部によりそれぞれ多項式ｆ”を生成し、前記多項式送信部により当該多項式ｆ”を送信する第３ステップ、それぞれのメッセージｃに対して前記検証パターン受信部により前記検証者からそれぞれ検証パターンの情報を受信する第４ステップ、それぞれの検証パターンの情報に対して前記回答送信部により回答情報を送信する第５ステップを実行する処理を繰り返し、
前記第１〜第５ステップを所定回数実行した結果、前記検証者により毎回全ての回答情報で検証が成功した場合に認証が成功する、
請求項７に記載の認証装置。
【請求項９】
ｓ∈Ｋｎが秘密鍵に設定され、環Ｋ上の多次多項式ｆｉ（ｘ１，…，ｘｎ）（ｉ＝１〜ｍ）が公開鍵またはシステムパラメータ、及びｙｉ＝ｆｉ（ｓ）が公開鍵に設定されており、
証明者からメッセージｃを受信するメッセージ受信部と、
前記証明者に対して応答αを送信する応答送信部と、
前記応答送信部により送信された応答αを用いて前記証明者により生成された、前記メッセージｃに対する検証に利用される多項式ｆ”を受信する多項式受信部と、
１つの前記メッセージｃに対するｋ通り（ｋ≧２）の検証パターンの中から１つの検証パターンを選択する検証パターン選択部と、
前記検証パターン選択部により選択された検証パターンの情報を前記証明者に対して送信する検証パターン送信部と、
ｋ通りの回答情報の中から、前記検証パターン送信部により送信された検証パターンの情報に対応する回答情報を前記証明者から受信する回答受信部と、
前記メッセージ受信部により受信されたメッセージｃ、前記多項式受信部により受信された多項式ｆ”、及び前記回答受信部により受信された回答情報を用いて前記証明者の正当性を検証する検証部と、
を備え、
前記回答情報は、２通りの前記応答α、前記多項式ｆ”及び前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対する計２ｋ通りの応答と検証パターンの組合せが全て成功した場合に秘密鍵ｓが計算可能となる情報である、
認証装置。
【請求項１０】
前記ｍ及びｎは、ｍ＜ｎの関係を有する、
請求項１、５、６、９のいずれか１項に記載の認証装置。
【請求項１１】
前記ｍ及びｎは、２ｍ−ｎ≪１の関係を有する、
請求項１０に記載の認証装置。
【請求項１２】
ｓ∈Ｋｎを秘密鍵に設定し、環Ｋ上の多次多項式ｆｉ（ｘ１，…，ｘｎ）（ｉ＝１〜ｍ）を公開鍵またはシステムパラメータ、及びｙｉ＝ｆｉ（ｓ）を公開鍵に設定する鍵設定ステップと、
検証者に対してメッセージｃを送信するメッセージ送信ステップと、
１つの前記メッセージｃに対するｋ通り（ｋ≧３）の検証パターンの中から前記検証者により選択された１つの検証パターンの情報を受信する検証パターン受信ステップと、
ｋ通りの回答情報の中から、前記検証パターン受信ステップで受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信ステップと、
を含み、
前記回答情報は、前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対するｋ通りの検証パターンが全て成功した場合に秘密鍵ｓが計算可能となる情報である、
認証方法。
【請求項１３】
ｓ∈Ｋｎが秘密鍵に設定され、環Ｋ上の多次多項式ｆｉ（ｘ１，…，ｘｎ）（ｉ＝１〜ｍ）が公開鍵またはシステムパラメータ、及びｙｉ＝ｆｉ（ｓ）が公開鍵に設定されており、
証明者からメッセージｃを受信するメッセージ受信ステップと、
１つの前記メッセージｃに対するｋ通り（ｋ≧３）の検証パターンの中から１つの検証パターンを選択する検証パターン選択ステップと、
前記検証パターン選択ステップで選択された検証パターンの情報を前記証明者に対して送信する検証パターン送信ステップと、
ｋ通りの回答情報の中から、前記検証パターン送信ステップで送信された検証パターンの情報に対応する回答情報を前記証明者から受信する回答受信ステップと、
前記メッセージ受信ステップで受信されたメッセージｃ、及び前記回答受信ステップで受信された回答情報を用いて前記証明者の正当性を検証する検証ステップと、
を含み、
前記回答情報は、前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対するｋ通りの検証パターンが全て成功した場合に秘密鍵ｓが計算可能となる情報である、
認証方法。
【請求項１４】
ｓ∈Ｋｎを秘密鍵に設定し、環Ｋ上の多次多項式ｆｉ（ｘ１，…，ｘｎ）（ｉ＝１〜ｍ）を公開鍵またはシステムパラメータ、及びｙｉ＝ｆｉ（ｓ）を公開鍵に設定する鍵設定ステップと、
検証者に対してメッセージｃを送信するメッセージ送信ステップと、
前記検証者から応答αを受信する応答受信ステップと、
前記応答受信ステップで受信された応答αを用いて、前記メッセージｃに対する検証に利用される多項式ｆ”を生成する多項式生成ステップと、
前記多項式生成ステップで生成された多項式ｆ”を前記検証者に送信する多項式送信ステップと、
１つの前記メッセージｃに対するｋ通り（ｋ≧２）の検証パターンの中から前記検証者により選択された１つの検証パターンの情報を受信する検証パターン受信ステップと、
ｋ通りの回答情報の中から、前記検証パターン受信ステップで受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信ステップと、
を含み、
前記回答情報は、２通りの前記応答α、前記多項式ｆ”及び前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対する計２ｋ通りの応答と検証パターンの組合せが全て成功した場合に秘密鍵ｓが計算可能となる情報である、
認証方法。
【請求項１５】
ｓ∈Ｋｎが秘密鍵に設定され、環Ｋ上の多次多項式ｆｉ（ｘ１，…，ｘｎ）（ｉ＝１〜ｍ）が公開鍵またはシステムパラメータ、及びｙｉ＝ｆｉ（ｓ）が公開鍵に設定されており、
証明者からメッセージｃを受信するメッセージ受信ステップと、
前記証明者に対して応答αを送信する応答送信ステップと、
前記応答送信ステップで送信された応答αを用いて前記証明者により生成された、前記メッセージｃに対する検証に利用される多項式ｆ”を受信する多項式受信ステップと、
１つの前記メッセージｃに対するｋ通り（ｋ≧２）の検証パターンの中から１つの検証パターンを選択する検証パターン選択ステップと、
前記検証パターン選択ステップで選択された検証パターンの情報を前記証明者に対して送信する検証パターン送信ステップと、
ｋ通りの回答情報の中から、前記検証パターン送信ステップで送信された検証パターンの情報に対応する回答情報を前記証明者から受信する回答受信ステップと、
前記メッセージ受信ステップで受信されたメッセージｃ、前記多項式受信ステップで受信された多項式ｆ”、及び前記回答受信ステップで受信された回答情報を用いて前記証明者の正当性を検証する検証ステップと、
を含み、
前記回答情報は、２通りの前記応答α、前記多項式ｆ”及び前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対する計２ｋ通りの応答と検証パターンの組合せが全て成功した場合に秘密鍵ｓが計算可能となる情報である、
認証方法。
【請求項１６】
ｓ∈Ｋｎを秘密鍵に設定し、環Ｋ上の多次多項式ｆｉ（ｘ１，…，ｘｎ）（ｉ＝１〜ｍ）を公開鍵またはシステムパラメータ、及びｙｉ＝ｆｉ（ｓ）を公開鍵に設定する鍵設定機能と、
検証者に対してメッセージｃを送信するメッセージ送信機能と、
１つの前記メッセージｃに対するｋ通り（ｋ≧３）の検証パターンの中から前記検証者により選択された１つの検証パターンの情報を受信する検証パターン受信機能と、
ｋ通りの回答情報の中から、前記検証パターン受信機能により受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信機能と、
をコンピュータに実現させるためのプログラムであり、
前記回答情報は、前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対するｋ通りの検証パターンが全て成功した場合に秘密鍵ｓが計算可能となる情報である、
プログラム。
【請求項１７】
ｓ∈Ｋｎを秘密鍵に設定し、環Ｋ上の多次多項式ｆｉ（ｘ１，…，ｘｎ）（ｉ＝１〜ｍ）を公開鍵またはシステムパラメータ、及びｙｉ＝ｆｉ（ｓ）を公開鍵に設定する鍵設定部と、
前記多次多項式ｆｉ（ｘ１，…，ｘｎ）及び前記秘密鍵ｓに基づいてＮ個のメッセージｃを生成するメッセージ生成部と、
文書Ｍ及び前記メッセージｃを一方向性関数に適用して得られた情報に基づいて、ｋＮ通り（ｋ≧３）の検証パターンの中から検証パターンを選択する検証パターン選択部と、
前記検証パターン選択部により選択された検証パターンに応じて、前記メッセージｃ及び前記文書Ｍを用いた検証を通過するような電子署名σを生成する署名生成部と、
を備え、
前記電子署名σは、前記（ｋ−１）Ｎ＋１通りの検証パターンに対応する電子署名σを用いて実施した検証が全て成功した場合に秘密鍵ｓが計算可能となる情報である、
署名生成装置。
【請求項１８】
前記メッセージ生成部により生成された単数又は複数のメッセージｃを送信する第１ステップ、それぞれのメッセージｃに対して前記検証パターン選択部により検証パターンを選択する第２ステップ、それぞれの検証パターンの情報に対して前記署名生成部により電子署名σを送信する第３ステップを実行し、電子署名σを用いて実施した検証が全て成功した場合に認証が成功する、
請求項１７に記載の署名生成装置。
【請求項１９】
前記ｍ及びｎは、ｍ＜ｎの関係を有する、
請求項１７に記載の署名生成装置。
【請求項２０】
前記多次多項式ｆｉは２次多項式である、
請求項１７に記載の署名生成装置。
【請求項２１】
ｓ∈Ｋｎを秘密鍵に設定し、環Ｋ上の多次多項式ｆｉ（ｘ１，…，ｘｎ）（ｉ＝１〜ｍ）を公開鍵またはシステムパラメータ、及びｙｉ＝ｆｉ（ｓ）を公開鍵に設定する鍵設定部と、
検証者に対してメッセージｃを送信するメッセージ送信部と、
１つの前記メッセージｃに対するｋ通り（ｋ≧３）の検証パターンの中から前記検証者により選択された１つの検証パターンの情報を受信する検証パターン受信部と、
ｋ通りの回答情報の中から、前記検証パターン受信部により受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信部と、
を備え、
前記回答情報は、前記秘密鍵ｓをｒ∈Ｋｎによりマスクした情報ｚ∈Ｋｎと、前記ｒをｔ∈Ｋｎによりマスクしたｔ’∈Ｋｎと、前記多次多項式ｆｉに前記ｒを代入したｆｉ（ｒ）をｅｉ∈Ｋによりマスクしたｅｉ’∈Ｋを用いて計算される情報である、
認証装置。
【請求項２２】
前記メッセージ送信部により単数又は複数のメッセージｃを送信する第１ステップ、それぞれのメッセージｃに対して前記検証パターン受信部により前記検証者からそれぞれ検証パターンの情報を受信する第２ステップ、それぞれの検証パターンの情報に対して前記回答送信部により回答情報を送信する第３ステップを実行し、前記検証者により全ての回答情報で検証が成功した場合に認証が成功する、
請求項２１に記載の認証装置。
【請求項２３】
前記多次多項式ｆｉは２次多項式である、
請求項１、５、６、９、２１のいずれか１項に記載の認証装置。