認証装置、認証方法、プログラム、及び署名生成装置
【課題】代数曲面上の求セクション問題を安全性の根拠とし、偽造困難性が保証された公開鍵認証方式を実現すること。
【解決手段】多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）を秘密鍵に設定し、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆを公開鍵に設定する鍵設定部と、検証者に対してメッセージｃを送信するメッセージ送信部と、１つの前記メッセージｃに対するｋ通り（ｋ≧３）の検証パターンの中から前記検証者により選択された１つの検証パターンの情報を受信する検証パターン受信部と、ｋ通りの回答情報の中から、前記検証パターン受信部により受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信部と、を備え、前記回答情報は、前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対するｋ通りの検証パターンが全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、認証装置が提供される。
【解決手段】多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）を秘密鍵に設定し、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆを公開鍵に設定する鍵設定部と、検証者に対してメッセージｃを送信するメッセージ送信部と、１つの前記メッセージｃに対するｋ通り（ｋ≧３）の検証パターンの中から前記検証者により選択された１つの検証パターンの情報を受信する検証パターン受信部と、ｋ通りの回答情報の中から、前記検証パターン受信部により受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信部と、を備え、前記回答情報は、前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対するｋ通りの検証パターンが全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、認証装置が提供される。
Notice: Undefined index: DEJ in /mnt/www/gzt_disp.php on line 298
【特許請求の範囲】
【請求項１】
多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）を秘密鍵に設定し、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆを公開鍵に設定する鍵設定部と、
検証者に対してメッセージｃを送信するメッセージ送信部と、
１つの前記メッセージｃに対するｋ通り（ｋ≧３）の検証パターンの中から前記検証者により選択された１つの検証パターンの情報を受信する検証パターン受信部と、
ｋ通りの回答情報の中から、前記検証パターン受信部により受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信部と、
を備え、
前記回答情報は、前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対するｋ通りの検証パターンが全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、
認証装置。
【請求項２】
前記メッセージ送信部により単数又は複数のメッセージｃを送信する第１ステップ、それぞれのメッセージｃに対して前記検証パターン受信部により前記検証者からそれぞれ検証パターンの情報を受信する第２ステップ、それぞれの検証パターンの情報に対して前記回答送信部により回答情報を送信する第３ステップを実行し、前記検証者により全ての回答情報で検証が成功した場合に認証が成功する、
請求項１に記載の認証装置。
【請求項３】
前記メッセージ送信部により単数又は複数のメッセージｃを送信する第１ステップ、それぞれのメッセージｃに対して前記検証パターン受信部により前記検証者からそれぞれ検証パターンの情報を受信する第２ステップ、それぞれの検証パターンの情報に対して前記回答送信部により回答情報を送信する第３ステップを実行する処理を繰り返し、
前記第１〜第３ステップを所定回数実行した結果、前記検証者により毎回全ての回答情報で検証が成功した場合に認証が成功する、
請求項２に記載の認証装置。
【請求項４】
前記メッセージｃがｃ＝（ｃ１，…，ｃｍ）である場合、
前記メッセージ送信部は、一方向性関数Ｈを用いて新たなメッセージｃ’＝Ｈ（ｃ）を算出して、前記検証者に対してメッセージｃ’を送信し、
前記回答送信部は、前記回答情報と共に、当該回答情報を利用しても前記検証者が復元することができないメッセージｃの要素を送信する、
請求項２又は３に記載の認証装置。
【請求項５】
多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）が秘密鍵に設定され、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆが公開鍵に設定されており、
証明者からメッセージｃを受信するメッセージ受信部と、
１つの前記メッセージｃに対するｋ通り（ｋ≧３）の検証パターンの中から１つの検証パターンを選択する検証パターン選択部と、
前記検証パターン選択部により選択された検証パターンの情報を前記証明者に対して送信する検証パターン送信部と、
ｋ通りの回答情報の中から、前記検証パターン送信部により送信された検証パターンの情報に対応する回答情報を前記証明者から受信する回答受信部と、
前記メッセージ受信部により受信されたメッセージｃ、及び前記回答受信部により受信された回答情報を用いて前記証明者の正当性を検証する検証部と、
を備え、
前記回答情報は、前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対するｋ通りの検証パターンが全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、
認証装置。
【請求項６】
多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）を秘密鍵に設定し、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆを公開鍵に設定する鍵設定部と、
検証者に対してメッセージｃを送信するメッセージ送信部と、
前記検証者から応答αを受信する応答受信部と、
前記応答受信部により受信された応答αを用いて、前記メッセージｃに対する検証に利用される多項式ｆ”を生成する多項式生成部と、
前記多項式生成部により生成された多項式ｆ”を前記検証者に送信する多項式送信部と、
１つの前記メッセージｃに対するｋ通り（ｋ≧２）の検証パターンの中から前記検証者により選択された１つの検証パターンの情報を受信する検証パターン受信部と、
ｋ通りの回答情報の中から、前記検証パターン受信部により受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信部と、
を備え、
前記回答情報は、２通りの前記応答α、前記多項式ｆ”及び前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対する計２ｋ通りの応答と検証パターンの組合せが全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、
認証装置。
【請求項７】
前記メッセージ送信部により単数又は複数のメッセージｃを送信する第１ステップ、それぞれのメッセージｃに対して前記応答受信部から応答αを受信する第２ステップ、当該第２ステップで受信した応答αを用いて前記多項式生成部によりそれぞれ多項式ｆ”を生成し、前記多項式送信部により当該多項式ｆ”を送信する第３ステップ、それぞれのメッセージｃに対して前記検証パターン受信部により前記検証者からそれぞれ検証パターンの情報を受信する第４ステップ、それぞれの検証パターンの情報に対して前記回答送信部により回答情報を送信する第５ステップを実行し、前記検証者により全ての回答情報で検証が成功した場合に認証が成功する、
請求項６に記載の認証装置。
【請求項８】
前記メッセージ送信部により単数又は複数のメッセージｃを送信する第１ステップ、それぞれのメッセージｃに対して前記応答受信部から応答αを受信する第２ステップ、当該第２ステップで受信した応答αを用いて前記多項式生成部によりそれぞれ多項式ｆ”を生成し、前記多項式送信部により当該多項式ｆ”を送信する第３ステップ、それぞれのメッセージｃに対して前記検証パターン受信部により前記検証者からそれぞれ検証パターンの情報を受信する第４ステップ、それぞれの検証パターンの情報に対して前記回答送信部により回答情報を送信する第５ステップを実行する処理を繰り返し、
前記第１〜第５ステップを所定回数実行した結果、前記検証者により毎回全ての回答情報で検証が成功した場合に認証が成功する、
請求項７に記載の認証装置。
【請求項９】
多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）が秘密鍵に設定され、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆが公開鍵に設定されており、
証明者からメッセージｃを受信するメッセージ受信部と、
前記証明者に対して応答αを送信する応答送信部と、
前記応答送信部により送信された応答αを用いて前記証明者により生成された、前記メッセージｃに対する検証に利用される多項式ｆ”を受信する多項式受信部と、
１つの前記メッセージｃに対するｋ通り（ｋ≧２）の検証パターンの中から１つの検証パターンを選択する検証パターン選択部と、
前記検証パターン選択部により選択された検証パターンの情報を前記証明者に対して送信する検証パターン送信部と、
ｋ通りの回答情報の中から、前記検証パターン送信部により送信された検証パターンの情報に対応する回答情報を前記証明者から受信する回答受信部と、
前記メッセージ受信部により受信されたメッセージｃ、前記多項式受信部により受信された多項式ｆ”、及び前記回答受信部により受信された回答情報を用いて前記証明者の正当性を検証する検証部と、
を備え、
前記回答情報は、２通りの前記応答α、前記多項式ｆ”及び前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対する計２ｋ通りの応答と検証パターンの組合せが全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、
認証装置。
【請求項１０】
多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）を秘密鍵に設定し、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆを公開鍵に設定する鍵設定ステップと、
検証者に対してメッセージｃを送信するメッセージ送信ステップと、
１つの前記メッセージｃに対するｋ通り（ｋ≧３）の検証パターンの中から前記検証者により選択された１つの検証パターンの情報を受信する検証パターン受信ステップと、
ｋ通りの回答情報の中から、前記検証パターン受信ステップで受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信ステップと、
を含み、
前記回答情報は、前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対するｋ通りの検証パターンが全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、
認証方法。
【請求項１１】
多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）が秘密鍵に設定され、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆが公開鍵に設定されており、
証明者からメッセージｃを受信するメッセージ受信ステップと、
１つの前記メッセージｃに対するｋ通り（ｋ≧３）の検証パターンの中から１つの検証パターンを選択する検証パターン選択ステップと、
前記検証パターン選択ステップで選択された検証パターンの情報を前記証明者に対して送信する検証パターン送信ステップと、
ｋ通りの回答情報の中から、前記検証パターン送信ステップで送信された検証パターンの情報に対応する回答情報を前記証明者から受信する回答受信ステップと、
前記メッセージ受信ステップで受信されたメッセージｃ、及び前記回答受信ステップで受信された回答情報を用いて前記証明者の正当性を検証する検証ステップと、
を含み、
前記回答情報は、前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対するｋ通りの検証パターンが全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、
認証方法。
【請求項１２】
多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）を秘密鍵に設定し、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆを公開鍵に設定する鍵設定ステップと、
検証者に対してメッセージｃを送信するメッセージ送信ステップと、
前記検証者から応答αを受信する応答受信ステップと、
前記応答受信ステップで受信された応答αを用いて、前記メッセージｃに対する検証に利用される多項式ｆ”を生成する多項式生成ステップと、
前記多項式生成ステップで生成された多項式ｆ”を前記検証者に送信する多項式送信ステップと、
１つの前記メッセージｃに対するｋ通り（ｋ≧２）の検証パターンの中から前記検証者により選択された１つの検証パターンの情報を受信する検証パターン受信ステップと、
ｋ通りの回答情報の中から、前記検証パターン受信ステップで受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信ステップと、
を含み、
前記回答情報は、２通りの前記応答α、前記多項式ｆ”及び前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対する計２ｋ通りの応答と検証パターンの組合せが全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、
認証方法。
【請求項１３】
多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）が秘密鍵に設定され、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆが公開鍵に設定されており、
証明者からメッセージｃを受信するメッセージ受信ステップと、
前記証明者に対して応答αを送信する応答送信ステップと、
前記応答送信ステップで送信された応答αを用いて前記証明者により生成された、前記メッセージｃに対する検証に利用される多項式ｆ”を受信する多項式受信ステップと、
１つの前記メッセージｃに対するｋ通り（ｋ≧２）の検証パターンの中から１つの検証パターンを選択する検証パターン選択ステップと、
前記検証パターン選択ステップで選択された検証パターンの情報を前記証明者に対して送信する検証パターン送信ステップと、
ｋ通りの回答情報の中から、前記検証パターン送信ステップで送信された検証パターンの情報に対応する回答情報を前記証明者から受信する回答受信ステップと、
前記メッセージ受信ステップで受信されたメッセージｃ、前記多項式受信ステップで受信された多項式ｆ”、及び前記回答受信ステップで受信された回答情報を用いて前記証明者の正当性を検証する検証ステップと、
を含み、
前記回答情報は、２通りの前記応答α、前記多項式ｆ”及び前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対する計２ｋ通りの応答と検証パターンの組合せが全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、
認証方法。
【請求項１４】
多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）を秘密鍵に設定し、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆを公開鍵に設定する鍵設定機能と、
検証者に対してメッセージｃを送信するメッセージ送信機能と、
１つの前記メッセージｃに対するｋ通り（ｋ≧３）の検証パターンの中から前記検証者により選択された１つの検証パターンの情報を受信する検証パターン受信機能と、
ｋ通りの回答情報の中から、前記検証パターン受信機能により受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信機能と、
をコンピュータに実現させるためのプログラムであり、
前記回答情報は、前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対するｋ通りの検証パターンが全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、
プログラム。
【請求項１５】
多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）を秘密鍵に設定し、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆを公開鍵に設定する鍵設定部と、
前記多次多項式ｕｉ（ｔ）に基づいてN個のメッセージｃを生成するメッセージ生成部と、
文書Ｍ及び前記メッセージｃを一方向性関数に適用して得られた情報に基づいて、ｋN通り（ｋ≧３）の検証パターンの中から検証パターンを選択する検証パターン選択部と、
前記検証パターン選択部により選択された検証パターンに応じて、前記メッセージｃ及び前記文書Ｍを用いた検証を通過するような電子署名σを生成する署名生成部と、
を備え、
前記電子署名σは、前記（ｋ−１）N＋１通りの検証パターンに対応する電子署名σを用いて実施した検証が全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、
署名生成装置。
【請求項１】
多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）を秘密鍵に設定し、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆを公開鍵に設定する鍵設定部と、
検証者に対してメッセージｃを送信するメッセージ送信部と、
１つの前記メッセージｃに対するｋ通り（ｋ≧３）の検証パターンの中から前記検証者により選択された１つの検証パターンの情報を受信する検証パターン受信部と、
ｋ通りの回答情報の中から、前記検証パターン受信部により受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信部と、
を備え、
前記回答情報は、前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対するｋ通りの検証パターンが全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、
認証装置。
【請求項２】
前記メッセージ送信部により単数又は複数のメッセージｃを送信する第１ステップ、それぞれのメッセージｃに対して前記検証パターン受信部により前記検証者からそれぞれ検証パターンの情報を受信する第２ステップ、それぞれの検証パターンの情報に対して前記回答送信部により回答情報を送信する第３ステップを実行し、前記検証者により全ての回答情報で検証が成功した場合に認証が成功する、
請求項１に記載の認証装置。
【請求項３】
前記メッセージ送信部により単数又は複数のメッセージｃを送信する第１ステップ、それぞれのメッセージｃに対して前記検証パターン受信部により前記検証者からそれぞれ検証パターンの情報を受信する第２ステップ、それぞれの検証パターンの情報に対して前記回答送信部により回答情報を送信する第３ステップを実行する処理を繰り返し、
前記第１〜第３ステップを所定回数実行した結果、前記検証者により毎回全ての回答情報で検証が成功した場合に認証が成功する、
請求項２に記載の認証装置。
【請求項４】
前記メッセージｃがｃ＝（ｃ１，…，ｃｍ）である場合、
前記メッセージ送信部は、一方向性関数Ｈを用いて新たなメッセージｃ’＝Ｈ（ｃ）を算出して、前記検証者に対してメッセージｃ’を送信し、
前記回答送信部は、前記回答情報と共に、当該回答情報を利用しても前記検証者が復元することができないメッセージｃの要素を送信する、
請求項２又は３に記載の認証装置。
【請求項５】
多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）が秘密鍵に設定され、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆが公開鍵に設定されており、
証明者からメッセージｃを受信するメッセージ受信部と、
１つの前記メッセージｃに対するｋ通り（ｋ≧３）の検証パターンの中から１つの検証パターンを選択する検証パターン選択部と、
前記検証パターン選択部により選択された検証パターンの情報を前記証明者に対して送信する検証パターン送信部と、
ｋ通りの回答情報の中から、前記検証パターン送信部により送信された検証パターンの情報に対応する回答情報を前記証明者から受信する回答受信部と、
前記メッセージ受信部により受信されたメッセージｃ、及び前記回答受信部により受信された回答情報を用いて前記証明者の正当性を検証する検証部と、
を備え、
前記回答情報は、前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対するｋ通りの検証パターンが全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、
認証装置。
【請求項６】
多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）を秘密鍵に設定し、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆを公開鍵に設定する鍵設定部と、
検証者に対してメッセージｃを送信するメッセージ送信部と、
前記検証者から応答αを受信する応答受信部と、
前記応答受信部により受信された応答αを用いて、前記メッセージｃに対する検証に利用される多項式ｆ”を生成する多項式生成部と、
前記多項式生成部により生成された多項式ｆ”を前記検証者に送信する多項式送信部と、
１つの前記メッセージｃに対するｋ通り（ｋ≧２）の検証パターンの中から前記検証者により選択された１つの検証パターンの情報を受信する検証パターン受信部と、
ｋ通りの回答情報の中から、前記検証パターン受信部により受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信部と、
を備え、
前記回答情報は、２通りの前記応答α、前記多項式ｆ”及び前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対する計２ｋ通りの応答と検証パターンの組合せが全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、
認証装置。
【請求項７】
前記メッセージ送信部により単数又は複数のメッセージｃを送信する第１ステップ、それぞれのメッセージｃに対して前記応答受信部から応答αを受信する第２ステップ、当該第２ステップで受信した応答αを用いて前記多項式生成部によりそれぞれ多項式ｆ”を生成し、前記多項式送信部により当該多項式ｆ”を送信する第３ステップ、それぞれのメッセージｃに対して前記検証パターン受信部により前記検証者からそれぞれ検証パターンの情報を受信する第４ステップ、それぞれの検証パターンの情報に対して前記回答送信部により回答情報を送信する第５ステップを実行し、前記検証者により全ての回答情報で検証が成功した場合に認証が成功する、
請求項６に記載の認証装置。
【請求項８】
前記メッセージ送信部により単数又は複数のメッセージｃを送信する第１ステップ、それぞれのメッセージｃに対して前記応答受信部から応答αを受信する第２ステップ、当該第２ステップで受信した応答αを用いて前記多項式生成部によりそれぞれ多項式ｆ”を生成し、前記多項式送信部により当該多項式ｆ”を送信する第３ステップ、それぞれのメッセージｃに対して前記検証パターン受信部により前記検証者からそれぞれ検証パターンの情報を受信する第４ステップ、それぞれの検証パターンの情報に対して前記回答送信部により回答情報を送信する第５ステップを実行する処理を繰り返し、
前記第１〜第５ステップを所定回数実行した結果、前記検証者により毎回全ての回答情報で検証が成功した場合に認証が成功する、
請求項７に記載の認証装置。
【請求項９】
多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）が秘密鍵に設定され、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆが公開鍵に設定されており、
証明者からメッセージｃを受信するメッセージ受信部と、
前記証明者に対して応答αを送信する応答送信部と、
前記応答送信部により送信された応答αを用いて前記証明者により生成された、前記メッセージｃに対する検証に利用される多項式ｆ”を受信する多項式受信部と、
１つの前記メッセージｃに対するｋ通り（ｋ≧２）の検証パターンの中から１つの検証パターンを選択する検証パターン選択部と、
前記検証パターン選択部により選択された検証パターンの情報を前記証明者に対して送信する検証パターン送信部と、
ｋ通りの回答情報の中から、前記検証パターン送信部により送信された検証パターンの情報に対応する回答情報を前記証明者から受信する回答受信部と、
前記メッセージ受信部により受信されたメッセージｃ、前記多項式受信部により受信された多項式ｆ”、及び前記回答受信部により受信された回答情報を用いて前記証明者の正当性を検証する検証部と、
を備え、
前記回答情報は、２通りの前記応答α、前記多項式ｆ”及び前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対する計２ｋ通りの応答と検証パターンの組合せが全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、
認証装置。
【請求項１０】
多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）を秘密鍵に設定し、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆを公開鍵に設定する鍵設定ステップと、
検証者に対してメッセージｃを送信するメッセージ送信ステップと、
１つの前記メッセージｃに対するｋ通り（ｋ≧３）の検証パターンの中から前記検証者により選択された１つの検証パターンの情報を受信する検証パターン受信ステップと、
ｋ通りの回答情報の中から、前記検証パターン受信ステップで受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信ステップと、
を含み、
前記回答情報は、前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対するｋ通りの検証パターンが全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、
認証方法。
【請求項１１】
多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）が秘密鍵に設定され、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆが公開鍵に設定されており、
証明者からメッセージｃを受信するメッセージ受信ステップと、
１つの前記メッセージｃに対するｋ通り（ｋ≧３）の検証パターンの中から１つの検証パターンを選択する検証パターン選択ステップと、
前記検証パターン選択ステップで選択された検証パターンの情報を前記証明者に対して送信する検証パターン送信ステップと、
ｋ通りの回答情報の中から、前記検証パターン送信ステップで送信された検証パターンの情報に対応する回答情報を前記証明者から受信する回答受信ステップと、
前記メッセージ受信ステップで受信されたメッセージｃ、及び前記回答受信ステップで受信された回答情報を用いて前記証明者の正当性を検証する検証ステップと、
を含み、
前記回答情報は、前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対するｋ通りの検証パターンが全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、
認証方法。
【請求項１２】
多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）を秘密鍵に設定し、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆを公開鍵に設定する鍵設定ステップと、
検証者に対してメッセージｃを送信するメッセージ送信ステップと、
前記検証者から応答αを受信する応答受信ステップと、
前記応答受信ステップで受信された応答αを用いて、前記メッセージｃに対する検証に利用される多項式ｆ”を生成する多項式生成ステップと、
前記多項式生成ステップで生成された多項式ｆ”を前記検証者に送信する多項式送信ステップと、
１つの前記メッセージｃに対するｋ通り（ｋ≧２）の検証パターンの中から前記検証者により選択された１つの検証パターンの情報を受信する検証パターン受信ステップと、
ｋ通りの回答情報の中から、前記検証パターン受信ステップで受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信ステップと、
を含み、
前記回答情報は、２通りの前記応答α、前記多項式ｆ”及び前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対する計２ｋ通りの応答と検証パターンの組合せが全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、
認証方法。
【請求項１３】
多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）が秘密鍵に設定され、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆが公開鍵に設定されており、
証明者からメッセージｃを受信するメッセージ受信ステップと、
前記証明者に対して応答αを送信する応答送信ステップと、
前記応答送信ステップで送信された応答αを用いて前記証明者により生成された、前記メッセージｃに対する検証に利用される多項式ｆ”を受信する多項式受信ステップと、
１つの前記メッセージｃに対するｋ通り（ｋ≧２）の検証パターンの中から１つの検証パターンを選択する検証パターン選択ステップと、
前記検証パターン選択ステップで選択された検証パターンの情報を前記証明者に対して送信する検証パターン送信ステップと、
ｋ通りの回答情報の中から、前記検証パターン送信ステップで送信された検証パターンの情報に対応する回答情報を前記証明者から受信する回答受信ステップと、
前記メッセージ受信ステップで受信されたメッセージｃ、前記多項式受信ステップで受信された多項式ｆ”、及び前記回答受信ステップで受信された回答情報を用いて前記証明者の正当性を検証する検証ステップと、
を含み、
前記回答情報は、２通りの前記応答α、前記多項式ｆ”及び前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対する計２ｋ通りの応答と検証パターンの組合せが全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、
認証方法。
【請求項１４】
多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）を秘密鍵に設定し、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆを公開鍵に設定する鍵設定機能と、
検証者に対してメッセージｃを送信するメッセージ送信機能と、
１つの前記メッセージｃに対するｋ通り（ｋ≧３）の検証パターンの中から前記検証者により選択された１つの検証パターンの情報を受信する検証パターン受信機能と、
ｋ通りの回答情報の中から、前記検証パターン受信機能により受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信機能と、
をコンピュータに実現させるためのプログラムであり、
前記回答情報は、前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対するｋ通りの検証パターンが全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、
プログラム。
【請求項１５】
多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）を秘密鍵に設定し、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆを公開鍵に設定する鍵設定部と、
前記多次多項式ｕｉ（ｔ）に基づいてN個のメッセージｃを生成するメッセージ生成部と、
文書Ｍ及び前記メッセージｃを一方向性関数に適用して得られた情報に基づいて、ｋN通り（ｋ≧３）の検証パターンの中から検証パターンを選択する検証パターン選択部と、
前記検証パターン選択部により選択された検証パターンに応じて、前記メッセージｃ及び前記文書Ｍを用いた検証を通過するような電子署名σを生成する署名生成部と、
を備え、
前記電子署名σは、前記（ｋ−１）N＋１通りの検証パターンに対応する電子署名σを用いて実施した検証が全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、
署名生成装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【公開番号】特開２０１１−２５４１５５（Ｐ２０１１−２５４１５５Ａ）
【公開日】平成２３年１２月１５日（２０１１．１２．１５）
【国際特許分類】
【出願番号】特願２０１０−１２５０２１（Ｐ２０１０−１２５０２１）
【出願日】平成２２年５月３１日（２０１０．５．３１）
【出願人】（０００００２１８５）ソニー株式会社 (34,172)
【Ｆターム（参考）】
【公開日】平成２３年１２月１５日（２０１１．１２．１５）
【国際特許分類】
【出願日】平成２２年５月３１日（２０１０．５．３１）
【出願人】（０００００２１８５）ソニー株式会社 (34,172)
【Ｆターム（参考）】
[ Back to top ]