【手続補正書】
【提出日】平成25年9月20日(2013.9.20)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
Ｌ個（Ｌ≧２）の秘密鍵ｓｉ（ｉ＝１〜Ｌ）、及びｎ次多変数多項式の組Ｆ（ｎ≧２）についてｙｉ＝Ｆ（ｓｉ）を満たすＬ個の公開鍵ｙｉを保持する鍵保持部と、
（Ｌ−１）個のｙｉ＝Ｆ（ｓｉ）を満たす秘密鍵ｓｉを用いた認証プロトコルを検証者との間で実行する認証プロトコル実行部と、
を備え、
前記認証プロトコル実行部は、
前記検証者からＬ個のチャレンジＣｈｉを受信するチャレンジ受信部と、
前記チャレンジ受信部により受信されたＬ個のチャレンジＣｈｉの中から（Ｌ−１）個のチャレンジＣｈｉを任意に選択するチャレンジ選択部と、
前記秘密鍵ｓｉを用いて、前記チャレンジ選択部により選択された（Ｌ−１）個のチャレンジＣｈｉのそれぞれに対する（Ｌ−１）個の回答Ｒｓｐｉを生成する回答生成部と、
前記回答生成部により生成された（Ｌ−１）個の回答Ｒｓｐｉを前記検証者に送信する回答送信部と、
を含む、
認証装置。
【請求項２】
前記認証プロトコル実行部は、
前記検証者に対し、Ｌ個の前記秘密鍵ｓｉのそれぞれに対応するメッセージＣｍｔｉを送信するメッセージ送信部をさらに含み、
前記チャレンジ受信部は、前記メッセージ送信部により送信された各メッセージＣｍｔｉに応じて、前記検証者によりｋ通り（ｋ≧２）の検証パターンの中から選択された検証パターンを示すチャレンジＣｈｉを受信する、
請求項１に記載の認証装置。
【請求項３】
前記メッセージＣｍｔｉがＣｍｔｉ＝（ｃｉ，１，…，ｃｉ，Ｎ）である場合、
前記メッセージ送信部は、一方向性関数Ｈを用いて新たなメッセージＣｍｔ’＝Ｈ（Ｃｍｔ１，…，ＣｍｔＬ）を算出して当該メッセージＣｍｔ’を前記検証者に送信し、
前記回答送信部は、前記回答Ｒｓｐｉと共に、当該回答Ｒｓｐｉを利用しても前記検証者が復元できない前記メッセージＣｍｔｉの要素を送信する、
請求項２に記載の認証装置。
【請求項４】
前記鍵保持部は、前記Ｌ個の秘密鍵ｓｉのうち、１つの秘密鍵ｓｉ０（１≦ｉ０≦Ｌ）を保持しないようにし、
前記認証プロトコル実行部は、前記認証プロトコルの中で実行される前記秘密鍵ｓｉ０に関する処理を偽証アルゴリズムに基づいて実行する、
請求項２に記載の認証装置。
【請求項５】
Ｌ個の秘密鍵ｓｉ（ｉ＝１〜Ｌ）、ｎ次多変数多項式の組Ｆ（ｎ≧２）についてｙｉ＝Ｆ（ｓｉ）を満たすＬ個の公開鍵ｙｉを保持する鍵保持部と、
検証者からＱ組（Ｑ≧２）のＬ個のチャレンジＣｈｉ（ｊ）（ｊ＝１〜Ｑ）を受信するチャレンジ受信部と、
前記チャレンジ受信部により受信されたＱ組のＬ個のチャレンジＣｈｉ（ｊ）の中から１組のＬ個のチャレンジＣｈｉ（ｊ）を任意に選択するチャレンジ選択部と、
前記秘密鍵ｓｉを用いて、前記チャレンジ選択部により選択されたＬ個のチャレンジＣｈｉ（ｊ）のそれぞれに対するＬ個の回答Ｒｓｐｉを生成する回答生成部と、
前記回答生成部により生成されたＬ個の回答Ｒｓｐｉを前記検証者に送信する回答送信部と、
を備える、
認証装置。
【請求項６】
前記検証者に対し、Ｌ個の前記秘密鍵ｓｉのそれぞれに対応するメッセージＣｍｔｉを送信するメッセージ送信部をさらに含み、
前記チャレンジ受信部は、前記メッセージ送信部により送信された各メッセージＣｍｔｉに応じて、前記検証者によりｋ通り（ｋ≧２）の検証パターンの中から選択された検証パターンを示すチャレンジＣｈｉ（ｊ）を受信する、
請求項５に記載の認証装置。
【請求項７】
前記メッセージＣｍｔｉがＣｍｔｉ＝（ｃｉ，１，…，ｃｉ，Ｎ）である場合、
前記メッセージ送信部は、一方向性関数Ｈを用いて新たなメッセージＣｍｔ’＝Ｈ（Ｃｍｔ１，…，ＣｍｔＬ）を算出して当該メッセージＣｍｔ’を前記検証者に送信し、
前記回答送信部は、前記回答Ｒｓｐｉと共に、当該回答Ｒｓｐｉを利用しても前記検証者が復元できない前記メッセージＣｍｔｉの要素を送信する、
請求項６に記載の認証装置。
【請求項８】
Ｌ個（Ｌ≧２）の秘密鍵ｓｉ（ｉ＝１〜Ｌ）、及びｎ次多変数多項式の組Ｆ（ｎ≧２）についてｙｉ＝Ｆ（ｓｉ）を満たすＬ個の公開鍵ｙｉを生成する鍵生成ステップと、
（Ｌ−１）個のｙｉ＝Ｆ（ｓｉ）を満たす秘密鍵ｓｉを用いた認証プロトコルを検証者との間で実行する認証プロトコル実行ステップと、
を含み、
前記認証プロトコル実行ステップは、
前記検証者からＬ個のチャレンジＣｈｉを受信するチャレンジ受信ステップと、
前記チャレンジ受信ステップで受信されたＬ個のチャレンジＣｈｉの中から（Ｌ−１）個のチャレンジＣｈｉを任意に選択するチャレンジ選択ステップと、
前記秘密鍵ｓｉを用いて、前記チャレンジ選択ステップで選択された（Ｌ−１）個のチャレンジＣｈｉのそれぞれに対する（Ｌ−１）個の回答Ｒｓｐｉを生成する回答生成ステップと、
前記回答生成ステップで生成された（Ｌ−１）個の回答Ｒｓｐｉを前記検証者に送信する回答送信ステップと、
を含む、
認証方法。
【請求項９】
Ｌ個（Ｌ≧２）の秘密鍵ｓｉ（ｉ＝１〜Ｌ）、及びｎ次多変数多項式の組Ｆ（ｎ≧２）についてｙｉ＝Ｆ（ｓｉ）を満たすＬ個の公開鍵ｙｉを保持する鍵保持機能と、
（Ｌ−１）個のｙｉ＝Ｆ（ｓｉ）を満たす秘密鍵ｓｉを用いた認証プロトコルを検証者との間で実行する認証プロトコル実行機能と、
をコンピュータに実現させるためのプログラムであり、
前記認証プロトコル実行機能は、
前記検証者からＬ個のチャレンジＣｈｉを受信するチャレンジ受信機能と、
前記チャレンジ受信機能により受信されたＬ個のチャレンジＣｈｉの中から（Ｌ−１）個のチャレンジＣｈｉを任意に選択するチャレンジ選択機能と、
前記秘密鍵ｓｉを用いて、前記チャレンジ選択機能により選択された（Ｌ−１）個のチャレンジＣｈｉのそれぞれに対する（Ｌ−１）個の回答Ｒｓｐｉを生成する回答生成機能と、
前記回答生成機能により生成された（Ｌ−１）個の回答Ｒｓｐｉを前記検証者に送信する回答送信機能と、
を含む、
プログラム。
【請求項１０】
Ｌ個の秘密鍵ｓｉ（ｉ＝１〜Ｌ）、ｎ次多変数多項式の組Ｆ（ｎ≧２）についてｙｉ＝Ｆ（ｓｉ）を満たすＬ個の公開鍵ｙｉを生成する鍵生成ステップと、
検証者からＱ組（Ｑ≧２）のＬ個のチャレンジＣｈｉ（ｊ）（ｊ＝１〜Ｑ）を受信するチャレンジ受信ステップと、
前記チャレンジ受信ステップで受信されたＱ組のＬ個のチャレンジＣｈｉ（ｊ）の中から１組のＬ個のチャレンジＣｈｉ（ｊ）を任意に選択するチャレンジ選択ステップと、
前記秘密鍵ｓｉを用いて、前記チャレンジ選択ステップで選択されたＬ個のチャレンジＣｈｉ（ｊ）のそれぞれに対するＬ個の回答Ｒｓｐｉを生成する回答生成ステップと、
前記回答生成ステップで生成されたＬ個の回答Ｒｓｐｉを前記検証者に送信する回答送信ステップと、
を含む、
認証方法。
【請求項１１】
Ｌ個の秘密鍵ｓｉ（ｉ＝１〜Ｌ）、ｎ次多変数多項式Ｆ（ｎ≧２）についてｙｉ＝Ｆ（ｓｉ）を満たすＬ個の公開鍵ｙｉを保持する鍵保持機能と、
検証者からＱ組（Ｑ≧２）のＬ個のチャレンジＣｈｉ（ｊ）（ｊ＝１〜Ｑ）を受信するチャレンジ受信機能と、
前記チャレンジ受信機能により受信されたＱ組のＬ個のチャレンジＣｈｉ（ｊ）の中から１組のＬ個のチャレンジＣｈｉ（ｊ）を任意に選択するチャレンジ選択機能と、
前記秘密鍵ｓｉを用いて、前記チャレンジ選択機能により選択されたＬ個のチャレンジＣｈｉ（ｊ）のそれぞれに対するＬ個の回答Ｒｓｐｉを生成する回答生成機能と、
前記回答生成機能により生成されたＬ個の回答Ｒｓｐｉを前記検証者に送信する回答送信機能と、
をコンピュータに実現させるためのプログラム。