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

【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、認証装置、認証方法、プログラム、及び署名生成装置に関する。
【背景技術】
【０００２】
情報処理技術や通信技術の急速な発展に伴い、公文書、私文書を問わず、文書の電子化が急速に進んでいる。これに伴い、多くの個人や企業は、電子文書の安全管理に大きな関心を寄せている。こうした関心の高まりを受け、各方面で電子文書の盗聴や偽造等のタンパリング行為に対する安全性が盛んに議論されるようになってきた。電子文書の盗聴に対する安全性は、例えば、電子文書を暗号化することにより確保される。また、電子文書の偽造に対する安全性は、例えば、電子署名を利用することにより確保される。但し、暗号や電子署名には十分なタンパリング耐性が求められる。
【０００３】
電子署名は、電子文書の作成者を特定するために利用される。そのため、電子署名は、電子文書の作成者しか生成できないようにすべきである。仮に、悪意ある第三者が同じ電子署名を生成できてしまうと、その第三者が電子文書の作成者に成りすますことができてしまう。つまり、悪意ある第三者により電子文書が偽造されてしまう。こうした偽造を防止するため、電子署名の安全性については様々な議論が交わされてきた。現在広く利用されている電子署名方式としては、例えば、ＲＳＡ署名方式やＤＳＡ署名方式を利用する方式が知られている。
【０００４】
ＲＳＡ署名方式は、「大きな合成数に対する素因数分解の困難性（以下、素因数分解問題）」を安全性の根拠とする。また、ＤＳＡ署名方式は、「離散対数問題に対する解答の困難性」を安全性の根拠とする。これらの根拠は、古典的なコンピュータを利用して素因数分解問題や離散対数問題を効率的に解くアルゴリズムが存在しないことに起因する。つまり、上記の困難性は、古典的なコンピュータにおける計算量的な困難性を意味する。しかしながら、量子コンピュータを用いると、素因数分解問題や離散対数問題に対する解答が効率的に算出されてしまうと言われている。
【０００５】
現在利用されている電子署名方式や公開鍵認証方式の多くは、ＲＳＡ署名方式やＤＳＡ署名方式と同様、素因数分解問題や離散対数問題の困難性に安全性の根拠をおいている。そのため、こうした電子署名方式や公開鍵認証方式は、量子コンピュータが実用化された場合に、その安全性が確保されないことになる。そこで、素因数分解問題や離散対数問題など、量子コンピュータにより容易に解かれてしまう問題とは異なる問題に安全性の根拠をおく新たな電子署名方式及び公開鍵認証方式が求められている。量子コンピュータにより容易に解くことが難しい問題としては、例えば、代数曲面上の求セクション問題がある。下記の非特許文献１には、代数曲面上の求セクション問題を安全性の根拠とする電子署名方式（以下、ＡＳＳ−ＣＣ方式）が開示されている。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Ｙｕｉｃｈｉ  Ｋｏｍａｎｏ，  Ｋｏｉｃｈｉｒｏ  Ａｋｉｙａｍａ，  Ｙｏｃｈｉｋａｚｕ  Ｈａｎａｔａｎｉ，  ａｎｄ  Ｈｉｄｅｙｕｋｉ  Ｍｉｙａｋｅ，  ＡＳＳ−ＣＣ：  Ｐｒｏｖａｂｌｙ  Ｓｅｃｕｒｅ  Ａｌｇｅｂｒａｉｃ  Ｓｕｒｆａｃｅ  Ｓｉｇｎａｔｕｒｅ  Ｓｅｈｅｍｅ．  Ｔｈｅ  ２０１０  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｃｒｙｐｔｏｇｒａｐｈｙ  ａｎｄ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｅｃｕｒｉｔｙ  Ｍｉｙａｚａｋｉ，  Ｊａｐａｎ，  Ｊａｎ．  １９−２２，  ２０１０．
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、ＡＳＳ−ＣＣ方式は、本件発明者らによる検証の結果、安全性に欠陥があることが判明した。そのため、ＡＳＳ−ＣＣ方式に基づく電子署名方式、及びこれを応用した公開鍵認証方式は、安全上の問題から実際には利用できない。そこで、本発明は、上記問題に鑑みてなされたものであり、本発明の目的とするところは、代数曲面上の求セクション問題を安全性の根拠とし、安全性が確認された公開鍵署名方式を実現することが可能な、新規かつ改良された認証装置、認証方法、プログラム、及び署名生成装置を提供することにある。また、その応用として電子署名方式を実現することも可能である。
【課題を解決するための手段】
【０００８】
上記課題を解決するために、本発明のある観点によれば、多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）を秘密鍵に設定し、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆを公開鍵に設定する鍵設定部と、検証者に対してメッセージｃを送信するメッセージ送信部と、１つの前記メッセージｃに対するｋ通り（ｋ≧３）の検証パターンの中から前記検証者により選択された１つの検証パターンの情報を受信する検証パターン受信部と、ｋ通りの回答情報の中から、前記検証パターン受信部により受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信部と、を備え、前記回答情報は、前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対するｋ通りの検証パターンが全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、認証装置が提供される。
【０００９】
また、上記の認証装置は、前記メッセージ送信部により単数又は複数のメッセージｃを送信する第１ステップ、それぞれのメッセージｃに対して前記検証パターン受信部により前記検証者からそれぞれ検証パターンの情報を受信する第２ステップ、それぞれの検証パターンの情報に対して前記回答送信部により回答情報を送信する第３ステップを実行し、前記検証者により全ての回答情報で検証が成功した場合に認証が成功する、ように構成されていてもよい。
【００１０】
また、上記の認証装置は、前記メッセージ送信部により複数のメッセージｃを送信する第１ステップ、それぞれのメッセージｃに対して前記検証パターン受信部により前記検証者からそれぞれ検証パターンの情報を受信する第２ステップ、それぞれの検証パターンの情報に対して前記回答送信部により回答情報を送信する第３ステップを実行する処理を繰り返し、前記第１〜第３ステップを所定回数実行した結果、前記検証者により毎回全ての回答情報で検証が成功した場合に認証が成功する、ように構成されていてもよい。
【００１１】
また、前記メッセージｃがｃ＝（ｃ１，…，ｃｍ）である場合、前記メッセージ送信部は、一方向性関数Ｈを用いて新たなメッセージｃ’＝Ｈ（ｃ）を算出して、前記検証者に対してメッセージｃ’を送信し、前記回答送信部は、前記回答情報と共に、当該回答情報を利用しても前記検証者が復元することができないメッセージｃの要素を送信する、ように構成されていてもよい。
【００１２】
また、上記課題を解決するために、本発明の別の観点によれば、多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）が秘密鍵に設定され、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆが公開鍵に設定されており、証明者からメッセージｃを受信するメッセージ受信部と、１つの前記メッセージｃに対するｋ通り（ｋ≧３）の検証パターンの中から１つの検証パターンを選択する検証パターン選択部と、前記検証パターン選択部により選択された検証パターンの情報を前記証明者に対して送信する検証パターン送信部と、ｋ通りの回答情報の中から、前記検証パターン送信部により送信された検証パターンの情報に対応する回答情報を前記証明者から受信する回答受信部と、前記メッセージ受信部により受信されたメッセージｃ、及び前記回答受信部により受信された回答情報を用いて前記証明者の正当性を検証する検証部と、を備え、前記回答情報は、前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対するｋ通りの検証パターンが全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、認証装置が提供される。
【００１３】
また、上記課題を解決するために、本発明の別の観点によれば、多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）を秘密鍵に設定し、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆを公開鍵に設定する鍵設定部と、検証者に対してメッセージｃを送信するメッセージ送信部と、前記検証者から応答αを受信する応答受信部と、前記応答受信部により受信された応答αを用いて、前記メッセージｃに対する検証に利用される多項式ｆ”を生成する多項式生成部と、前記多項式生成部により生成された多項式ｆ”を前記検証者に送信する多項式送信部と、１つの前記メッセージｃに対するｋ通り（ｋ≧２）の検証パターンの中から前記検証者により選択された１つの検証パターンの情報を受信する検証パターン受信部と、ｋ通りの回答情報の中から、前記検証パターン受信部により受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信部と、を備え、前記回答情報は、２通りの前記応答α、前記多項式ｆ”及び前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対する計２ｋ通りの応答と検証パターンの組合せが全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、認証装置が提供される。
【００１４】
また、上記の認証装置は、前記メッセージ送信部により複数のメッセージｃを送信する第１ステップ、それぞれのメッセージｃに対して前記応答受信部から応答αを受信する第２ステップ、当該第２ステップで受信した応答αを用いて前記多項式生成部によりそれぞれ多項式ｆ”を生成し、前記多項式送信部により当該多項式ｆ”を送信する第３ステップ、それぞれのメッセージｃに対して前記検証パターン受信部により前記検証者からそれぞれ検証パターンの情報を受信する第４ステップ、それぞれの検証パターンの情報に対して前記回答送信部により回答情報を送信する第５ステップを実行し、前記検証者により全ての回答情報で検証が成功した場合に認証が成功する、ように構成されていてもよい。
【００１５】
また、上記の認証装置は、前記メッセージ送信部により単数又は複数のメッセージｃを送信する第１ステップ、それぞれのメッセージｃに対して前記応答受信部から応答αを受信する第２ステップ、当該第２ステップで受信した応答αを用いて前記多項式生成部によりそれぞれ多項式ｆ”を生成し、前記多項式送信部により当該多項式ｆ”を送信する第３ステップ、それぞれのメッセージｃに対して前記検証パターン受信部により前記検証者からそれぞれ検証パターンの情報を受信する第４ステップ、それぞれの検証パターンの情報に対して前記回答送信部により回答情報を送信する第５ステップを実行する処理を繰り返し、前記第１〜第５ステップを所定回数実行した結果、前記検証者により毎回全ての回答情報で検証が成功した場合に認証が成功する、ように構成されていてもよい。
【００１６】
また、上記課題を解決するために、本発明の別の観点によれば、多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）が秘密鍵に設定され、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆが公開鍵に設定されており、証明者からメッセージｃを受信するメッセージ受信部と、前記証明者に対して応答αを送信する応答送信部と、前記応答送信部により送信された応答αを用いて前記証明者により生成された、前記メッセージｃに対する検証に利用される多項式ｆ”を受信する多項式受信部と、１つの前記メッセージｃに対するｋ通り（ｋ≧２）の検証パターンの中から１つの検証パターンを選択する検証パターン選択部と、前記検証パターン選択部により選択された検証パターンの情報を前記証明者に対して送信する検証パターン送信部と、ｋ通りの回答情報の中から、前記検証パターン送信部により送信された検証パターンの情報に対応する回答情報を前記証明者から受信する回答受信部と、前記メッセージ受信部により受信されたメッセージｃ、前記多項式受信部により受信された多項式ｆ”、及び前記回答受信部により受信された回答情報を用いて前記証明者の正当性を検証する検証部と、を備え、前記回答情報は、２通りの前記応答α、前記多項式ｆ”及び前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対する計２ｋ通りの応答と検証パターンの組合せが全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、認証装置が提供される。
【００１７】
また、上記課題を解決するために、本発明の別の観点によれば、多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）を秘密鍵に設定し、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆを公開鍵に設定する鍵設定ステップと、検証者に対してメッセージｃを送信するメッセージ送信ステップと、１つの前記メッセージｃに対するｋ通り（ｋ≧３）の検証パターンの中から前記検証者により選択された１つの検証パターンの情報を受信する検証パターン受信ステップと、ｋ通りの回答情報の中から、前記検証パターン受信ステップで受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信ステップと、を含み、前記回答情報は、前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対するｋ通りの検証パターンが全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、認証方法が提供される。
【００１８】
また、上記課題を解決するために、本発明の別の観点によれば、多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）が秘密鍵に設定され、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆが公開鍵に設定されており、証明者からメッセージｃを受信するメッセージ受信ステップと、１つの前記メッセージｃに対するｋ通り（ｋ≧３）の検証パターンの中から１つの検証パターンを選択する検証パターン選択ステップと、前記検証パターン選択ステップで選択された検証パターンの情報を前記証明者に対して送信する検証パターン送信ステップと、ｋ通りの回答情報の中から、前記検証パターン送信ステップで送信された検証パターンの情報に対応する回答情報を前記証明者から受信する回答受信ステップと、前記メッセージ受信ステップで受信されたメッセージｃ、及び前記回答受信ステップで受信された回答情報を用いて前記証明者の正当性を検証する検証ステップと、を含み、前記回答情報は、前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対するｋ通りの検証パターンが全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、認証方法が提供される。
【００１９】
また、上記課題を解決するために、本発明の別の観点によれば、多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）を秘密鍵に設定し、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆを公開鍵に設定する鍵設定ステップと、検証者に対してメッセージｃを送信するメッセージ送信ステップと、前記検証者から応答αを受信する応答受信ステップと、前記応答受信ステップで受信された応答αを用いて、前記メッセージｃに対する検証に利用される多項式ｆ”を生成する多項式生成ステップと、前記多項式生成ステップで生成された多項式ｆ”を前記検証者に送信する多項式送信ステップと、１つの前記メッセージｃに対するｋ通り（ｋ≧２）の検証パターンの中から前記検証者により選択された１つの検証パターンの情報を受信する検証パターン受信ステップと、ｋ通りの回答情報の中から、前記検証パターン受信ステップで受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信ステップと、を含み、前記回答情報は、２通りの前記応答α、前記多項式ｆ”及び前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対する計２ｋ通りの応答と検証パターンの組合せが全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、認証装置が提供される。
【００２０】
また、上記課題を解決するために、本発明の別の観点によれば、多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）が秘密鍵に設定され、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆが公開鍵に設定されており、証明者からメッセージｃを受信するメッセージ受信ステップと、前記証明者に対して応答αを送信する応答送信ステップと、前記応答送信ステップで送信された応答αを用いて前記証明者により生成された、前記メッセージｃに対する検証に利用される多項式ｆ”を受信する多項式受信ステップと、１つの前記メッセージｃに対するｋ通り（ｋ≧２）の検証パターンの中から１つの検証パターンを選択する検証パターン選択ステップと、前記検証パターン選択ステップで選択された検証パターンの情報を前記証明者に対して送信する検証パターン送信ステップと、ｋ通りの回答情報の中から、前記検証パターン送信ステップで送信された検証パターンの情報に対応する回答情報を前記証明者から受信する回答受信ステップと、前記メッセージ受信ステップで受信されたメッセージｃ、前記多項式受信ステップで受信された多項式ｆ”、及び前記回答受信ステップで受信された回答情報を用いて前記証明者の正当性を検証する検証ステップと、を含み、前記回答情報は、２通りの前記応答α、前記多項式ｆ”及び前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対する計２ｋ通りの応答と検証パターンの組合せが全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、認証装置が提供される。
【００２１】
また、上記課題を解決するために、本発明の別の観点によれば、多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）を秘密鍵に設定し、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆを公開鍵に設定する鍵設定機能と、検証者に対してメッセージｃを送信するメッセージ送信機能と、１つの前記メッセージｃに対するｋ通り（ｋ≧３）の検証パターンの中から前記検証者により選択された１つの検証パターンの情報を受信する検証パターン受信機能と、ｋ通りの回答情報の中から、前記検証パターン受信機能により受信された検証パターンの情報に対応する回答情報を前記検証者に送信する回答送信機能と、をコンピュータに実現させるためのプログラムであり、前記回答情報は、前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対するｋ通りの検証パターンが全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、プログラムが提供される。さらに、上記課題を解決するために、本発明の別の観点によれば、上記のプログラムが記録された、コンピュータにより読み取り可能な記録媒体が提供される。
【００２２】
また、上記課題を解決するために、本発明の別の観点によれば、多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）を秘密鍵に設定し、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆを公開鍵に設定する鍵設定部と、前記多次多項式ｕｉ（ｔ）に基づいてN個のメッセージｃを生成するメッセージ生成部と、文書Ｍ及び前記メッセージｃを一方向性関数に適用して得られた情報に基づいて、ｋN通り（ｋ≧３）の検証パターンの中から検証パターンを選択する検証パターン選択部と、前記検証パターン選択部により選択された検証パターンに応じて、前記メッセージｃ及び前記文書Ｍを用いた検証を通過するような電子署名σを生成する署名生成部と、を備え、前記電子署名σは、前記（ｋ−１）N＋１通りの検証パターンに対応する電子署名σを用いて実施した検証が全て成功した場合に秘密鍵ｕｉが計算可能となる情報である、署名生成装置が提供される。
【発明の効果】
【００２３】
以上説明したように本発明によれば、代数曲面上の求セクション問題を安全性の根拠とし、安全性が確認された公開鍵署名方式を実現することが可能になる。また、その応用として、代数曲面上の求セクション問題を安全性の根拠とし、安全性が確認された電子署名方式を実現することも可能である。
【図面の簡単な説明】
【００２４】
【図１】公開鍵認証方式のアルゴリズム構成について説明するための説明図である。
【図２】電子署名方式のアルゴリズム構成について説明するための説明図である。
【図３】ｎパスの公開鍵認証方式について説明するための説明図である。
【図４】ＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式のアルゴリズムについて説明するための説明図である。
【図５】ＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式のアルゴリズムに対する偽証アルゴリズムについて説明するための説明図である。
【図６】本発明の第１実施形態（３パス）に係る公開鍵認証方式のアルゴリズムについて説明するための説明図である。
【図７】同実施形態に係る公開鍵認証方式の拡張アルゴリズムについて説明するための説明図である。
【図８】同実施形態に係る公開鍵認証方式の並列化アルゴリズムについて説明するための説明図である。
【図９】同実施形態に係る公開鍵認証方式の非対話型アルゴリズムについて説明するための説明図である。
【図１０】同実施形態に係る公開鍵認証方式の具体的なアルゴリズムについて説明するための説明図である。
【図１１】本発明の第２実施形態（５パス）に係る公開鍵認証方式のアルゴリズムについて説明するための説明図である。
【図１２】同実施形態に係る公開鍵認証方式の拡張アルゴリズムについて説明するための説明図である。
【図１３】同実施形態に係る公開鍵認証方式の並列化アルゴリズムについて説明するための説明図である。
【図１４】同実施形態に係る公開鍵認証方式の拡張アルゴリズムに対する並列化について説明するための説明図である。
【図１５】同実施形態に係る公開鍵認証方式の非対話型アルゴリズムについて説明するための説明図である。
【図１６】同実施形態に係る公開鍵認証方式の具体的なアルゴリズムについて説明するための説明図である。
【図１７】本発明の各実施形態に係るアルゴリズムを実行することが可能な情報処理装置のハードウェア構成例について説明するための説明図である。
【図１８】本発明の第１及び第２実施形態に係る公開鍵認証方式の効率を比較した図表である。
【発明を実施するための形態】
【００２５】
以下に添付図面を参照しながら、本発明の好適な実施の形態について詳細に説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。
【００２６】
［説明の流れについて］
ここで、以下に記載する本発明の実施形態に関する説明の流れについて簡単に述べる。まず、図１を参照しながら、公開鍵認証方式のアルゴリズム構成について説明する。次いで、図２を参照しながら、電子署名方式のアルゴリズム構成について説明する。次いで、図３を参照しながら、ｎパスの公開鍵認証方式について説明する。次いで、図４を参照しながら、ＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式のアルゴリズムについて説明する。また、図５を参照しながら、ＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式のアルゴリズムに対する偽証アルゴリズムについて説明する。
【００２７】
次いで、図６を参照しながら、本発明の第１実施形態（３パス）に係る公開鍵認証方式のアルゴリズムについて説明する。次いで、図７を参照しながら、同実施形態に係る公開鍵認証方式の拡張アルゴリズムについて説明する。次いで、図８を参照しながら、同実施形態に係る公開鍵認証方式の並列化アルゴリズムについて説明する。次いで、図９を参照しながら、同実施形態に係る公開鍵認証方式の非対話型アルゴリズムについて説明する。次いで、図１０を参照しながら、同実施形態に係る公開鍵認証方式の具体的なアルゴリズムについて説明する。
【００２８】
次いで、図１１を参照しながら、本発明の第２実施形態（５パス）に係る公開鍵認証方式のアルゴリズムについて説明する。次いで、図１２を参照しながら、同実施形態に係る公開鍵認証方式の拡張アルゴリズムについて説明する。次いで、図１３、図１４を参照しながら、同実施形態に係る公開鍵認証方式の並列化アルゴリズムについて説明する。次いで、図１５を参照しながら、同実施形態に係る公開鍵認証方式の非対話型アルゴリズムについて説明する。次いで、図１６を参照しながら、同実施形態に係る公開鍵認証方式の具体的なアルゴリズムについて説明する。
【００２９】
次いで、図１７を参照しながら、本発明の第１及び第２実施形態に係る各アルゴリズムを実現することが可能な情報処理装置のハードウェア構成例について説明する。最後に、本実施形態の技術的思想について纏め、当該技術的思想から得られる作用効果について簡単に説明する。
【００３０】
（説明項目）
１：はじめに
１−１：公開鍵認証方式のアルゴリズム構成
１−２：電子署名方式のアルゴリズム構成
１−３：ｎパスの公開鍵認証方式
１−４：ＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式
１−４−１：ＡＳＳ−ＣＣ電子署名方式について
１−４−２：ＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式について
２：第１実施形態
２−１：公開鍵認証方式のアルゴリズム
２−２：拡張アルゴリズム
２−３：並列化アルゴリズム
２−４：非対話型アルゴリズム
２−５：電子署名方式への変形
２−６：具体例
３：第２実施形態
３−１：公開鍵認証方式のアルゴリズム
３−２：拡張アルゴリズム
３−３：並列化アルゴリズム
３−４：非対話型アルゴリズム
３−５：電子署名方式への変形
３−６：具体例
４：ハードウェア構成例
５：まとめ
【００３１】
＜１：はじめに＞
はじめに、本発明に係る実施形態について詳細に説明するに先立ち、一般的な公開鍵認証方式のアルゴリズム構成、一般的な電子署名方式のアルゴリズム構成、ｎパスの公開鍵認証方式、ＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式について簡単に説明する。
【００３２】
［１−１：公開鍵認証方式のアルゴリズム構成］
まず、図１を参照しながら、一般的な公開鍵認証方式のアルゴリズム構成について説明する。図１は、一般的な公開鍵認証方式のアルゴリズム構成について説明するための説明図である。
【００３３】
（概要）
公開鍵認証方式とは、ある人（証明者）が、公開鍵ｐｋ及び秘密鍵ｓｋを利用して、他の人（検証者）に本人であることを納得させるための認証方式である。例えば、証明者Ａの公開鍵ｐｋＡは、検証者に公開される。一方、証明者Ａの秘密鍵ｓｋＡは、証明者により秘密に管理される。公開鍵認証方式では、公開鍵ｐｋＡに対応する秘密鍵ｓｋＡを知る者が証明者Ａ本人であるとみなされる。
【００３４】
証明者Ａが検証者Ｂに対して本人であることを証明しようとする場合、証明者Ａは、検証者Ｂと対話プロトコルを実行して、自身が公開鍵ｐｋＡに対応する秘密鍵ｓｋＡを知っていることを証明すればよい。そして、対話プロトコルにより証明者Ａが秘密鍵ｓｋＡを知っていることが検証者Ｂにより証明された場合、証明者Ａの正当性（本人であること）が証明される。
【００３５】
なお、公開鍵認証方式の安全性を確保するには、次に示す２つの条件が求められる。
【００３６】
１つ目の条件は、対話プロトコルを実行した際に秘密鍵ｓｋを持たない偽証者により偽証が成立してしまう確率を限りなく小さくすることである。この１つ目の条件が成り立つことを「健全性」と呼ぶ。つまり、健全性を有する対話プロトコルにおいては、秘密鍵ｓｋを持たない偽証者により、無視できない確率で偽証が成立することはないと言い換えられる。２つ目の条件は、対話プロトコルを実行したとしても、証明者Ａが有する秘密鍵ｓｋＡの情報が検証者Ｂに一切漏れることがないようにすることである。この２つ目の条件が成り立つことを「零知識性」と呼ぶ。
【００３７】
上記の健全性と零知識性を有する対話プロトコルを利用することにより、公開鍵認証方式の安全性が確保される。
【００３８】
（モデル）
公開鍵認証方式のモデルには、図１に示すように、証明者と検証者という２つのエンティティが存在する。証明者は、鍵生成アルゴリズムＧｅｎを用いて、証明者固有の秘密鍵ｓｋと公開鍵ｐｋの組を生成する。次いで、証明者は、鍵生成アルゴリズムＧｅｎを用いて生成した秘密鍵ｓｋと公開鍵ｐｋの組を利用して検証者と対話プロトコルを実行する。このとき、証明者は、証明者アルゴリズムＰを利用して対話プロトコルを実行する。上記の通り、対話プロトコルにおいて、証明者は、証明者アルゴリズムＰを利用して、秘密鍵ｓｋを保有していることを検証者に証明する。
【００３９】
一方、検証者は、検証者アルゴリズムＶを利用して対話プロトコルを実行し、証明者が公開している公開鍵に対応する秘密鍵を、その証明者が保有しているか否かを検証する。つまり、検証者は、証明者が公開鍵に対応する秘密鍵を保有しているか否かを検証するエンティティである。このように、公開鍵認証方式のモデルは、証明者と検証者という２つのエンティティ、及び、鍵生成アルゴリズムＧｅｎ、証明者アルゴリズムＰ、検証者アルゴリズムＶという３つのアルゴリズムにより構成される。
【００４０】
なお、以下の説明において、「証明者」「検証者」という表現を用いるが、これらの表現はあくまでもエンティティを意味するものである。従って、鍵生成アルゴリズムＧｅｎ、証明者アルゴリズムＰを実行する主体は、「証明者」のエンティティに対応する情報処理装置である。同様に、検証者アルゴリズムＶを実行する主体は、情報処理装置である。これら情報処理装置のハードウェア構成は、例えば、図１７に示した通りである。つまり、鍵生成アルゴリズムＧｅｎ、証明者アルゴリズムＰ、検証者アルゴリズムＶは、ＲＯＭ９０４、ＲＡＭ９０６、記憶部９２０、リムーバブル記録媒体９２８などに記録されたプログラムに基づいてＣＰＵ９０２により実行される。
【００４１】
（鍵生成アルゴリズムＧｅｎ）
鍵生成アルゴリズムＧｅｎは、証明者により利用される。そして、鍵生成アルゴリズムＧｅｎは、証明者に固有の秘密鍵ｓｋと公開鍵ｐｋの組を生成するアルゴリズムである。鍵生成アルゴリズムＧｅｎにより生成された公開鍵ｐｋは公開される。そして、公開された公開鍵ｐｋは、検証者により利用される。一方、鍵生成アルゴリズムＧｅｎにより生成された秘密鍵ｓｋは、証明者が秘密に管理する。そして、秘密に管理される秘密鍵ｓｋは、検証者に対して公開鍵ｐｋに対応する秘密鍵ｓｋを保有していることを証明するために利用される。形式的に、鍵生成アルゴリズムＧｅｎは、セキュリティパラメータ１λ（λは０以上の整数）を入力とし、秘密鍵ｓｋと公開鍵ｐｋを出力するアルゴリズムとして、下記の式（１）のように表現される。
【００４２】
【数１】
0005593850.tif 000002
【００４３】
（証明者アルゴリズムＰ）
証明者アルゴリズムＰは、証明者により利用される。そして、証明者アルゴリズムＰは、公開鍵ｐｋに対応する秘密鍵ｓｋを保有していることを証明するアルゴリズムである。証明者アルゴリズムＰは、証明者の秘密鍵ｓｋと公開鍵ｐｋを入力とし、検証者との対話プロトコルを実行するアルゴリズムとして定義される。
【００４４】
（検証者アルゴリズムＶ）
検証者アルゴリズムＶは、検証者により利用される。そして、検証者アルゴリズムＶは、対話プロトコルの中で、公開鍵ｐｋに対応する秘密鍵ｓｋを証明者が保有しているか否かを検証するアルゴリズムである。検証者アルゴリズムＶは、証明者の公開鍵ｐｋを入力とし、証明者との間で対話プロトコルを実行した後、０又は１（１ｂｉｔ）を出力するアルゴリズムとして定義される。なお、出力０の場合には証明者が不正なものであり、出力１の場合には証明者が正当なものであるとする。形式的に、検証者アルゴリズムＶは、下記の式（２）のように表現される。
【００４５】
【数２】
0005593850.tif 000003
【００４６】
（補足）
上記の通り、公開鍵認証方式は、安全性を確保するため、健全性と零知識性という２つの条件を満たすことが求められる。しかし、証明者が秘密鍵ｓｋを保有していることを証明者に証明させるためには、証明者が秘密鍵ｓｋに依存した手続きを実行し、その結果を検証者に通知して、その通知内容に基づく検証を検証者に実行させる必要がある。秘密鍵ｓｋに依存した手続きを実行するのは、健全性を担保するために必要である。一方で、この手続きの結果を検証者に通知しても、秘密鍵ｓｋの情報が一切検証者に漏れないようにする必要がある。そのため、これらの要件を満たすように、上記の鍵生成アルゴリズムＧｅｎ、証明者アルゴリズムＰ、検証者アルゴリズムＶが設計されることが必要になる。
【００４７】
以上、一般的な公開鍵認証方式のアルゴリズム構成について説明した。
【００４８】
［１−２：電子署名方式のアルゴリズム構成］
次に、図２を参照しながら、一般的な電子署名方式のアルゴリズム構成について説明する。図２は、一般的な電子署名方式のアルゴリズム構成について説明するための説明図である。
【００４９】
（概要）
紙文書とは異なり、ある電子化されたデータに対して押印したり署名を記載したりすることはできない。そのため、電子化されたデータの作成者を証明するためには、紙文書に押印したり署名を記載したりするのと同等の効果を奏する電子的な仕組みが必要とされる。このような仕組みが電子署名である。例えば、データの作成者しか知らない署名データをデータに関連付けて受領者に提供し、その署名データを受領者側で検証する仕組みのことを電子署名方式と呼ぶ。
【００５０】
（モデル）
電子署名方式のモデルには、図２に示すように、署名者と検証者という２つのエンティティが存在する。そして、電子署名方式のモデルは、鍵生成アルゴリズムＧｅｎ、署名生成アルゴリズムＳｉｇ、署名検証アルゴリズムＶｅｒという３つのアルゴリズムにより構成される。
【００５１】
署名者は、鍵生成アルゴリズムＧｅｎを利用して署名者固有の署名鍵ｓｋと検証鍵ｐｋとの組を生成する。また、署名者は、署名生成アルゴリズムＳｉｇを利用して文書Ｍに対して付与する電子署名σを生成する。つまり、署名者は、文書Ｍに電子署名を付与するエンティティである。一方、検証者は、署名検証アルゴリズムＶｅｒを利用して文書Ｍに付与された電子署名σを検証する。つまり、検証者は、文書Ｍの作成者が署名者であるか否かを確認するために、電子署名σを検証するエンティティである。
【００５２】
なお、以下の説明において、「署名者」「検証者」という表現を用いるが、これらの表現はあくまでもエンティティを意味するものである。従って、鍵生成アルゴリズムＧｅｎ、署名生成アルゴリズムＳｉｇを実行する主体は、「署名者」のエンティティに対応する情報処理装置である。同様に、署名検証アルゴリズムＶｅｒを実行する主体は、情報処理装置である。これら情報処理装置のハードウェア構成は、例えば、図１７に示した通りである。つまり、鍵生成アルゴリズムＧｅｎ、署名生成アルゴリズムＳｉｇ、署名検証アルゴリズムＶｅｒは、ＲＯＭ９０４、ＲＡＭ９０６、記憶部９２０、リムーバブル記録媒体９２８などに記録されたプログラムに基づいてＣＰＵ９０２により実行される。
【００５３】
（鍵生成アルゴリズムＧｅｎ）
鍵生成アルゴリズムＧｅｎは、署名者により利用される。そして、鍵生成アルゴリズムＧｅｎは、署名者固有の署名鍵ｓｋと検証鍵ｐｋの組を生成するアルゴリズムである。鍵生成アルゴリズムＧｅｎにより生成された検証鍵ｐｋは公開される。一方、鍵生成アルゴリズムＧｅｎにより生成された署名鍵ｓｋは、署名者により秘密に管理される。そして、署名者により秘密に管理されている署名鍵ｓｋは、文書Ｍに付与される電子署名σの生成に利用される。形式的に、鍵生成アルゴリズムＧｅｎは、セキュリティパラメータ１＾λ（λは０以上の整数）を入力とし、秘密鍵ｓｋと公開鍵ｐｋを出力するアルゴリズムとして、下記の式（３）のように表現される。
【００５４】
【数３】
0005593850.tif 000004
【００５５】
（署名生成アルゴリズムＳｉｇ）
署名生成アルゴリズムＳｉｇは、署名者により利用される。そして、署名生成アルゴリズムＳｉｇは、文書Ｍに対して付与される電子署名σを生成するアルゴリズムである。形式的に、署名生成アルゴリズムＳｉｇは、署名者の署名鍵ｓｋと文書Ｍを入力とし、下記の式（４）に示すように、電子署名σを出力するアルゴリズムとして表現される。
【００５６】
【数４】
0005593850.tif 000005
【００５７】
（署名検証アルゴリズムＶｅｒ）
署名検証アルゴリズムＶｅｒは、検証者により利用される。そして、署名検証アルゴリズムＶｅｒは、電子署名σが文書Ｍに対する正当な電子署名であるか否かを検証するアルゴリズムである。形式的に、署名検証アルゴリズムＶｅｒは、下記の式（５）に示すように、署名者の検証鍵ｐｋ、文書Ｍ、電子署名σを入力とし、０又は１（１ｂｉｔ）を出力するアルゴリズムとして表現される。なお、０を出力する場合（公開鍵ｐｋが文書Ｍと電子署名σを拒否する場合）、文書Ｍに対する電子署名σは不当である。１を出力する場合（公開鍵ｐｋが文書Ｍと電子署名σを受理する場合）、文書Ｍに対する電子署名σは正当である。
【００５８】
【数５】
0005593850.tif 000006
【００５９】
以上、一般的な電子署名方式のアルゴリズム構成について説明した。
【００６０】
［１−３：ｎパスの公開鍵認証方式］
次に、図３を参照しながら、ｎパスの公開鍵認証方式について説明する。図３は、ｎパスの公開鍵認証方式について説明するための説明図である。
【００６１】
上記の通り、公開鍵認証方式は、対話プロトコルの中で、証明者が公開鍵ｐｋに対応する秘密鍵ｓｋを保有していることを検証者に証明する証方式である。また、公開鍵認証方式の安全性を担保するため、健全性と零知識性という２つの条件を満たす必要がある。そのため、対話プロトコルの中では、図３に示すように、証明者と検証者の双方がそれぞれ処理を実行しながら、証明者と検証者との間でｎ回の情報交換が行われる。
【００６２】
ｎパスの公開鍵認証方式の場合、証明者アルゴリズムＰを用いて証明者により処理（Ｓｔｅｐ．１）が実行され、情報Ｔ１が検証者に送信される。次いで、検証者アルゴリズムＶを用いて検証者により処理（Ｓｔｅｐ．２）が実行され、情報Ｔ２が証明者に送信される。同様にして処理（Ｓｔｅｐ．３，…，ｎ）が実行され、情報Ｔ３，…，Ｔｎが送信され、処理（Ｓｔｅｐ．ｎ＋１）が実行される。このように、情報がｎ回送受信される対話プロトコルに基づく公開鍵認証方式のことを「ｎパス」の公開鍵認証方式と呼ぶ。
【００６３】
以上、ｎパスの公開鍵認証方式について説明した。
【００６４】
［１−４：ＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式］
次に、代数曲面上の求セクション問題を安全性の根拠とする公開鍵認証方式の一例について説明する。代数曲面上の求セクション問題とは、環Ｋ上で定義されるｎ変数の多次多項式ｆ（ｘ１，…，ｘｎ）が与えられたときに、ｆ（ｓ１（ｔ），…，ｓｎ−１（ｔ），ｔ）＝０となる環Ｋ上の１変数多次多項式ｓ１（ｔ），…，ｓｎ−１（ｔ）を求める問題である。
【００６５】
（１−４−１：ＡＳＳ−ＣＣ電子署名方式について）
代数曲面上の求セクション問題に安全性の根拠をおく電子署名方式として、ＡＳＳ−ＣＣ電子署名方式（上記の非特許文献１を参照）が知られている。ＡＳＳ−ＣＣ電子署名方式は公開鍵認証方式ではないが、電子署名方式と公開鍵認証方式との関連性を考慮すると、後述するようにＡＳＳ−ＣＣ電子署名方式から、代数曲面上の求セクション問題に安全性をおく公開鍵認証方式を構築することができる。そこで、まず、ＡＳＳ−ＣＣ電子署名方式について説明する。
【００６６】
ＡＳＳ−ＣＣ電子署名方式は、以下に示す鍵生成アルゴリズムＧｅｎ、署名生成アルゴリズムＳｉｇ、署名検証アルゴリズムＶｅｒにより構成される。
【００６７】
（鍵生成アルゴリズムＧｅｎ）
鍵生成アルゴリズムＧｅｎは、下記のＳｔｅｐ．１、Ｓｔｅｐ．２を実行し、署名鍵（ｕｘ（ｔ），ｕｙ（ｔ），ｔ）及び検証鍵Ｘ（ｘ，ｙ，ｔ）を生成する。
【００６８】
Ｓｔｅｐ．１：
鍵生成アルゴリズムＧｅｎは、関数ｕｘ（ｔ），ｕｙ（ｔ），ｃｉ，ｊ（ｔ）（但し、（ｉ，ｊ）∈Λ＼｛０，０｝）を生成する。但し、Λは、正整数の添え字の集合である。
【００６９】
Ｓｔｅｐ．２：
鍵生成アルゴリズムＧｅｎは、ｃ０，０←Σ（ｉ，ｊ）∈Λ＼｛０，０｝ｃｉ，ｊ（ｔ）ｕｘ（ｔ）ｉｕｙ（ｔ）ｊとする。そして、鍵生成アルゴリズムＧｅｎは、署名鍵（ｕｘ（ｔ），ｕｙ（ｔ），ｔ）、及び、検証鍵Ｘ（ｘ，ｙ，ｔ）＝Σ（ｉ，ｊ）∈Λｃｉ，ｊ（ｔ）ｘ（ｔ）ｉｙ（ｔ）ｊを生成する。但し、Ｘ（ｕｘ（ｔ），ｕｙ（ｔ），ｔ）＝Σ（ｉ，ｊ）∈Λ＼｛０，０｝ｃｉ，ｊ（ｔ）ｕｘ（ｔ）ｉｕｙ（ｔ）ｊ＝０である。
【００７０】
（署名生成アルゴリズムＳｉｇ）
署名生成アルゴリズムＳｉｇは、まず、署名鍵（ｕｘ（ｔ），ｕｙ（ｔ），ｔ）と文書Ｍを入力とし、ｉ＝１〜ｎについて、以下のＳｔｅｐ．１〜Ｓｔｅｐ．４を実行する。
【００７１】
Ｓｔｅｐ．１：
署名生成アルゴリズムＳｉｇは、Ｓｉ∈Ｒ｛０，１｝λを選択し、Ｘｉ’（ｘ，ｙ，ｔ）←Ｈ（Ｓｉ）を計算する。但し、Ｈ（…）はハッシュ関数である。ハッシュ関数Ｈは、あるビット列ｓ∈｛０，１｝＊から一定範囲の数値を生成する関数である。また、任意のビット列ｓをハッシュ関数Ｈに入力して得られた値をハッシュ値と呼ぶ（以下同様）。
【００７２】
Ｓｔｅｐ．２：
署名生成アルゴリズムＳｉｇは、セクション（ｒｉ，ｘ（ｔ），ｒｉ，ｙ（ｔ））を選択し、Ｘｉ”（ｘ，ｙ，ｔ）←Ｘｉ（ｘ−ｒｉ，ｘ（ｔ），ｙ−ｒｉ，ｙ（ｔ），ｔ）＋Ｘｉ’（ｘ，ｙ，ｔ）を計算する。
【００７３】
Ｓｔｅｐ．３：
署名生成アルゴリズムＳｉｇは、（ｚｉ，ｘ（ｔ），ｚｉ，ｙ（ｔ））←（ｕｉ，ｘ（ｔ）＋ｒｉ，ｘ（ｔ），ｕｉ，ｙ（ｔ）＋ｒｉ，ｙ（ｔ））を計算する。
【００７４】
Ｓｔｅｐ．４：
署名生成アルゴリズムＳｉｇは、ｖｉ（ｔ）←Ｈ（Ｘｉ’（ｚｉ，ｘ（ｔ），ｚｉ，ｙ（ｔ），ｔ），ｚｉ，ｘ（ｔ），ｚｉ，ｙ（ｔ））を計算する。
【００７５】
Ｓｔｅｐ．５：
ｉ＝１〜ｎについて、上記のＳｔｅｐ．１〜Ｓｔｅｐ．４の処理を実行した後、署名生成アルゴリズムＳｉｇは、ｄ＝（ｄ１，…，ｄｎ）←Ｈ（Ｍ，Ｘ１”（ｘ，ｙ，ｔ），ｖ１（ｔ），…，Ｘｎ”（ｘ，ｙ，ｔ），ｖｎ（ｔ））を計算する。
【００７６】
次に、署名生成アルゴリズムＳｉｇは、ｉ＝１〜ｎについて、以下のＳｔｅｐ．６を実行する。
【００７７】
Ｓｔｅｐ．６：
もしｄｉ＝０ならば、署名生成アルゴリズムＳｉｇは、σｉ←（Ｓｉ，ｒｉ，ｘ（ｔ），ｒｉ，ｙ（ｔ））を計算する。一方、ｄｉ＝１ならば、署名生成アルゴリズムＳｉｇは、σｉ←（０，ｚｉ，ｘ（ｔ），ｚｉ，ｙ（ｔ））を計算する。
【００７８】
Ｓｔｅｐ．７：
そして、署名生成アルゴリズムＳｉｇは、電子署名σ＝（Ｘ１”（ｘ，ｙ，ｔ），ｖ１（ｔ），…，Ｘｎ”（ｘ，ｙ，ｔ），ｖｎ（ｔ），σ１，…，σｎ）を出力する。
【００７９】
（署名検証アルゴリズムＶｅｒ）
署名検証アルゴリズムＶｅｒは、電子署名σと文書Ｍを入力とし、次のＳｔｅｐ．１〜Ｓｔｅｐ．３を実行する。
【００８０】
Ｓｔｅｐ．１：
署名検証アルゴリズムＶｅｒは、ｄ＝（ｄ１，…，ｄｎ）←Ｈ（Ｍ，Ｘ１”（ｘ，ｙ，ｔ），…，Ｘｎ”（ｘ，ｙ，ｔ），ｖｎ（ｔ））を計算する。
【００８１】
次に、署名検証アルゴリズムＶｅｒは、ｉ＝１〜ｎについて、以下のＳｔｅｐ．２を実行する。
【００８２】
Ｓｔｅｐ．２：
もしｄｉ＝０ならば、署名検証アルゴリズムＶｅｒは、σｉを（Ｓｉ，ｒｉ，ｘ（ｔ），ｒｉ，ｙ（ｔ））に分割する。次いで、署名検証アルゴリズムＶｅｒは、Ｘｉ’（ｘ，ｙ，ｔ）←Ｈ（Ｓｉ）を計算する。次いで、署名検証アルゴリズムＶｅｒは、Ｘｉ”（ｘ，ｙ，ｔ）＝Ｘｉ（ｘ−ｒｉ，ｘ（ｔ），ｙ−ｒｉ，ｙ（ｔ），ｔ）＋Ｘｉ’（ｘ，ｙ，ｔ）の等式が成立するか否かを検証する。一方、ｄｉ＝１ならば、署名検証アルゴリズムＶｅｒは、σｉを（０，ｚｉ，ｘ（ｔ），ｚｉ，ｙ（ｔ））に分割する。次いで、署名検証アルゴリズムＶｅｒは、ｖｉ＝Ｈ（Ｘｉ”（ｚｉ，ｘ（ｔ），ｚｉ，ｙ（ｔ），ｔ），ｚｉ，ｘ（ｔ），ｚｉ，ｙ（ｔ））の等式が成立するか否かを検証する。
【００８３】
Ｓｔｅｐ．３：
ｉ＝１〜ｎについて、上記のＳｔｅｐ．２の処理を実行した後、署名検証アルゴリズムＶｅｒは、Ｓｔｅｐ．２の検証がｉ＝１〜ｎの全てについて通過したか否かを確認する。そして、署名検証アルゴリズムＶｅｒは、ｉ＝１〜ｎの全てについてＳｔｅｐ．２の検証が通過した場合に電子署名σを受理（１を出力）し、１つでも通過していない場合に電子署名σを拒否（０を出力）する。
【００８４】
（電子署名の偽証可能性について）
以上説明した鍵生成アルゴリズムＧｅｎ、署名生成アルゴリズムＳｉｇ、署名検証アルゴリズムＶｅｒによりＡＳＳ−ＣＣ電子署名方式は成り立っている。ＡＳＳ−ＣＣ電子署名方式は、代数曲面上の求セクション問題に安全性の根拠をおくという点において、量子コンピュータを用いたタンパリングに対しても耐性の高い電子署名方式である。しかしながら、本件発明者らにより、上記のＡＳＳ−ＣＣ電子署名方式における電子署名の偽造アルゴリズム（以下、署名偽造アルゴリズム）が発見された。
【００８５】
（ＡＳＳ−ＣＣ電子署名方式に対する電子署名の偽造アルゴリズム）
署名偽造アルゴリズムは、文書Ｍのみを入力とし、電子署名σを偽造するアルゴリズムである。まず、署名偽造アルゴリズムは、ｉ＝１〜ｎについて、以下のＳｔｅｐ．１〜Ｓｔｅｐ．３の処理を実行する。
【００８６】
Ｓｔｅｐ．１：
署名偽造アルゴリズムは、Ｓｉ∈Ｒ｛０，１｝λを選択し、Ｘｉ’（ｘ，ｙ，ｔ）←Ｈ（Ｓｉ）を計算する。
【００８７】
Ｓｔｅｐ．２：
署名偽造アルゴリズムは、セクション（ｒｉ，ｘ（ｔ），ｒｉ，ｙ（ｔ））を選択し、Ｘｉ”（ｘ，ｙ，ｔ）←Ｘｉ（ｘ−ｒｉ，ｘ（ｔ），ｙ−ｒｉ，ｙ（ｔ），ｔ）＋Ｘｉ’（ｘ，ｙ，ｔ）を計算する。
【００８８】
Ｓｔｅｐ．３：
署名偽造アルゴリズムは、セクション（ｚｉ，ｘ（ｔ），ｚｉ，ｙ（ｔ））を選択し、ｖｉ←Ｈ（Ｘｉ”（ｚｉ，ｘ（ｔ），ｚｉ，ｙ（ｔ），ｔ），ｚｉ，ｘ（ｔ），ｚｉ，ｙ（ｔ））を計算する。
【００８９】
Ｓｔｅｐ．４：
ｉ＝１〜ｎについて、上記のＳｔｅｐ．１〜３を実行した後、署名偽造アルゴリズムは、ｄ＝（ｄ１，…，ｄｎ）←Ｈ（Ｍ，Ｘ１”（ｘ，ｙ，ｔ），ｖ１（ｔ），…，Ｘｎ”（ｘ，ｙ，ｔ），ｖｎ（ｔ））を計算する。
【００９０】
次に、署名偽造アルゴリズムは、ｉ＝１〜ｎについて、以下のＳｔｅｐ．５を実行する。
【００９１】
Ｓｔｅｐ．５：
もしｄｉ＝０ならば、署名偽造アルゴリズムは、σｉ←（Ｓｉ，ｒｉ，ｘ（ｔ），ｒｉ，ｙ（ｔ））を計算する。一方、ｄｉ＝１ならば、署名偽造アルゴリズムは、σｉ←（０，ｚｉ，ｘ（ｔ），ｚｉ，ｙ（ｔ））を計算する。
【００９２】
Ｓｔｅｐ．６：
そして、署名生成アルゴリズムＳｉｇは、電子署名σ＝（Ｘ１”（ｘ，ｙ，ｔ），ｖ１（ｔ），…，Ｘｎ”（ｘ，ｙ，ｔ），ｖｎ（ｔ），σ１，…，σｎ）を出力する。
【００９３】
以上が署名偽造アルゴリズムの内容である。署名偽造アルゴリズムとＡＳＳ−ＣＣ電子署名方式における署名生成アルゴリズムＳｉｇの１つの違いは、（ｚｉ，ｘ（ｔ），ｚｉ，ｙ（ｔ））の生成方法にある。署名生成アルゴリズムＳｉｇは（ｚｉ，ｘ（ｔ），ｚｉ，ｙ（ｔ））を署名鍵（ｕｘ（ｔ），ｕｙ（ｔ），ｔ）から生成しているのに対し、署名偽造アルゴリズムは、署名鍵（ｕｘ（ｔ），ｕｙ（ｔ），ｔ）を利用していない。
【００９４】
また、署名偽造アルゴリズムとＡＳＳ−ＣＣ電子署名方式における署名生成アルゴリズムＳｉｇのもう１つの違いは、ｖｉの計算方法にある。署名生成アルゴリズムＳｉｇはＸｉ’（ｚｉ，ｘ（ｔ），ｚｉ，ｙ（ｔ），ｔ）を用いているが、署名偽造アルゴリズムは、Ｘｉ”（ｚｉ，ｘ（ｔ），ｚｉ，ｙ（ｔ），ｔ）を用いている。つまり、上記の署名偽造アルゴリズムのようにｖｉを設定すれば、署名鍵（ｕｘ（ｔ），ｕｙ（ｔ），ｔ）を利用せずに検証を通過する電子署名σが生成できてしまうのである。
【００９５】
以上、ＡＳＳ−ＣＣ電子署名方式に対する署名偽造アルゴリズムについて説明した。このような署名偽造アルゴリズムが存在することにより、ＡＳＳ−ＣＣ電子署名方式は安全に機能しないと言える。このような安全性に関する問題は、ＡＳＳ−ＣＣ電子署名方式を公開鍵認証方式に変形した場合にも引き継がれる。
【００９６】
（１−４−２：ＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式について）
ＡＳＳ−ＣＣ電子署名方式のアルゴリズムは、図４に示すような公開鍵認証方式（以下、ＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式）の対話プロトコルに変形することができる。なお、図４に示したＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式は、上記の非特許文献１には開示されていないものである。ここで、図４に示したＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式の対話プロトコルについて説明する。図４は、ＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式の対話プロトコルを説明するための説明図である。
【００９７】
図４に示すように、証明者と検証者の間で公開鍵ｐｋ＝Ｘ（ｘ，ｙ，ｚ）が共有されている。また、証明者は、秘密鍵ｓｋ＝（ｕｘ（ｙ），ｕｙ（ｙ），ｔ）を保有している。なお、秘密鍵ｓｋ、公開鍵ｐｋの生成方法は、ＡＳＳ−ＣＣ電子署名方式における署名鍵ｓｋ、検証鍵ｐｋの生成方法と同じである。
【００９８】
Ｓｔｅｐ．１：
まず、証明者アルゴリズムＰは、（ｒｘ（ｔ），ｒｙ（ｔ））∈ＲＳＴを計算する。但し、ＳＴは、代数曲面上のセクションを表現する多項式の組全体の集合である。次いで、証明者アルゴリズムＰは、ｚｘ（ｔ）←ｕｘ（ｔ）＋ｒｘ（ｔ）、ｚｙ（ｔ）←ｕｙ（ｔ）＋ｒｙ（ｔ）を計算する。次いで、証明者アルゴリズムＰは、Ｓ∈Ｒ｛０，１｝λを選択し、Ｘ’（ｘ，ｙ，ｔ）←Ｈ１（Ｓ）を計算する。
【００９９】
Ｓｔｅｐ．１（続き）：
次いで、証明者アルゴリズムＰは、Ｘ”（ｘ，ｙ，ｔ）←Ｘ（ｘ−ｒｘ（ｔ），ｙ−ｒｙ（ｔ），ｔ）＋Ｘ’（ｘ，ｙ，ｔ）を計算する。次いで、証明者アルゴリズムＰは、ｖ←Ｈ２（Ｘ’（ｚｘ（ｔ），ｚｙ（ｔ），ｔ），ｚｘ（ｔ），ｚｙ（ｔ））を計算する。但し、Ｈ１、Ｈ２はハッシュ関数である。そして、証明者アルゴリズムＰは、（Ｘ”（ｘ，ｙ，ｔ），ｖ）を検証者に送る。
【０１００】
Ｓｔｅｐ．２：
検証者アルゴリズムＶは、ｄ∈Ｒ｛０，１｝を選択する。そして、検証者アルゴリズムＶは、ｄを証明者に送る。
【０１０１】
Ｓｔｅｐ．３：
もしｄ＝０ならば、証明者アルゴリズムＰは、電子署名σ＝（Ｓ，ｒｘ（ｔ），ｒｙ（ｔ））を計算する。一方、ｄ＝１ならば、証明者アルゴリズムＰは、電子署名σ＝（ε，ｚｘ（ｔ），ｚｙ（ｔ））を計算する。そして、証明者アルゴリズムＰは、電子署名σを検証者に送る。なお、σ＝（ａ，ｂ（ｔ），ｃ（ｔ））と表現することにする。つまり、ｄ＝０の場合、ａ＝Ｓ、ｂ（ｔ）＝ｒｘ（ｔ）、ｃ（ｔ）＝ｒｙ（ｔ）であり、ｄ＝１の場合、ａ＝ε、ｂ（ｔ）＝ｚｘ（ｔ）、ｃ（ｔ）＝ｚｙ（ｔ）である。
【０１０２】
Ｓｔｅｐ．４：
検証者アルゴリズムＶは、ｄ＝０の場合、ａ’（ｘ，ｙ，ｔ）←Ｈ１（ａ）を計算する。そして、検証者アルゴリズムＶは、Ｘ”（ｘ，ｙ，ｔ）＝Ｘ（ｘ−ｂ（ｔ），ｙ−ｃ（ｔ），ｔ）＋ａ’（ｘ，ｙ，ｔ）の等式が成り立つか否かを検証する。一方、ｄ＝１の場合、検証者アルゴリズムＶは、ｖ＝Ｈ２（Ｘ”（ｂ（ｔ），ｃ（ｔ），ｔ），ｂ（ｔ），ｃ（ｔ））の等式が成り立つか否かを検証する。
【０１０３】
Ｓｔｅｐ．５：
検証者アルゴリズムＶは、Ｓｔｅｐ．４の検証が成功した場合に認証の成功を示す１を出力し、失敗した場合に認証の失敗を示す０を出力する。
【０１０４】
以上説明したように、ＡＳＳ−ＣＣ電子署名方式は、公開鍵認証方式に変形することができる。しかしながら、ＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式は、ＡＳＳ−ＣＣ電子署名方式と同じ安全上の問題を内包している。つまり、ＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式では、秘密鍵ｓｋを保有していない偽証者により偽証される可能性がある。そこで、図５を参照しながら、ＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式の偽証方法について説明する。
【０１０５】
（ＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式における偽証方法）
ＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式における偽証方法は、図５のＳｔｅｐ．１において下線を付した部分（※１、※２）に特徴がある。ＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式において、ｚｘ（ｔ）、ｚｙ（ｔ）は、秘密鍵ｓｋを用いて生成されていた。しかし、図５に示す偽証方法においては、ｚｘ（ｔ）、ｚｙ（ｔ）が任意に選択されている（※１）。また、ＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式において、ｖは、Ｘ’（ｚｘ（ｔ），ｚｙ（ｔ），ｙ）を利用して生成されていた。しかし、図５に示す偽証方法においては、ｖがＸ”（ｚｘ（ｔ），ｚｙ（ｔ），ｙ）を利用して生成されている（※２）。
【０１０６】
つまり、図５に示した偽証方法を用いれば、ｕｘ（ｔ）、ｕｙ（ｔ）を知らない偽証者が容易に偽証することができてしまうのである。すなわち、ＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式は健全性を有しない。先に述べた通り、公開鍵認証方式は、健全性と零知識性という２つの条件を両立させなければ、その安全性を保証することができない。上記のＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式は、零知識性を有するものの、健全性を有しない。そのため、ＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式における安全性は保証されない。
【０１０７】
そこで、ＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式の健全性を確保するための改良方法について考察する。ＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式の健全性を確保する方法として、例えば、検証者に、ｖ＝Ｈ（Ｘ’（ｚｘ（ｔ），ｚｙ（ｔ），ｔ），ｚｘ（ｔ），ｚｙ（ｔ））を追加で検証させる方法が考えられる。しかし、この方法を実現するには、検証者に対し、Ｘ’の情報と（ｚｘ（ｔ），ｚｙ（ｔ））の情報を渡す必要がある。
【０１０８】
ｄ＝０の場合に（ｚｘ（ｔ），ｚｙ（ｔ））の情報を検証者に渡すと、既に（ｒｘ（ｔ），ｒｙ（ｔ））の情報を得ている検証者は、秘密鍵ｓｋを計算できてしまう。一方、ｄ＝１の場合にＸ’の情報を検証者に渡すと、既にＸ”の情報を得ている検証者は、（ｒｘ（ｔ），ｒｙ（ｔ））の情報を計算することができてしまう。その結果、検証者は、計算した（ｒｘ（ｔ），ｒｙ（ｔ））の情報と（ｚｘ（ｔ），ｚｙ（ｔ））の情報から秘密鍵ｓｋを計算することができてしまう。
【０１０９】
そのため、ｖ＝Ｈ（Ｘ’（ｚｘ（ｔ），ｚｙ（ｔ），ｔ），ｚｘ（ｔ），ｚｙ（ｔ））を検証者に追加で検証させる方法を適用すると、健全性は確保されるが、零知識性が失われてしまう。このように、ＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式を改良して、健全性と零知識性という２つの条件を共に満たす公開鍵認証方式を構築することは難しい。そこで、本件発明者は、代数曲面上の求セクション問題を安全性の根拠とし、健全性と零知識性という２つの条件を満たす新たな公開鍵認証方式を考案した。以下、詳細に説明する。
【０１１０】
＜２：第１実施形態＞
本発明に係る第１実施形態について説明する。本実施形態は、代数曲面上の求セクション問題に安全性の根拠をおく３パスの公開鍵認証方式（以下、本手法）に関する。なお、ここでは３パスの公開鍵認証方式を例に挙げるが、本実施形態の対話プロトコルを拡張してｎパス（ｎ≧４）の公開鍵認証方式に一般化することも可能である。
【０１１１】
［２−１：公開鍵認証方式のアルゴリズム］
まず、図６を参照しながら、本手法に係る公開鍵認証方式のアルゴリズムについて説明する。図６は、本手法に係る公開鍵認証方式のアルゴリズムについて説明するための説明図である。なお、本手法は、鍵生成アルゴリズムＧｅｎ、証明者アルゴリズムＰ、検証者アルゴリズムＶにより構成される。以下、各アルゴリズムの内容について説明する。
【０１１２】
（鍵生成アルゴリズムＧｅｎ）
鍵生成アルゴリズムＧｅｎは、環Ｋ上で定義されるｎ変数の多次多項式ｆ０（ｘ１，…，ｘｎ）と、１変数の多次多項式ｕ１（ｔ），…，ｕｎ−１（ｔ）を生成する。次に、鍵生成アルゴリズムＧｅｎは、ｃ（ｔ）←ｆ０（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）を計算する。そして、鍵生成アルゴリズムＧｅｎは、ｆ（ｘ１，…，ｘｎ）＝ｆ０（ｘ１，…，ｘｎ）−ｃ（ｘｎ）を計算し、ｆを公開鍵ｐｋに設定する。また、鍵生成アルゴリズムＧｅｎは、（ｕ１，…，ｕｎ−１）を秘密鍵ｓｋに設定する。ここで、ｆ０（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たすことに注意されたい。
【０１１３】
（証明者アルゴリズムＰ、検証者アルゴリズムＶ）
次に、図６を参照しながら、対話プロトコルにおける証明者アルゴリズムＰと検証者アルゴリズムＶによる処理について説明する。この対話プロトコルは、「証明者がｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）を満たす（ｕ１，…，ｕｎ−１）を知っていること」を（ｕ１，…，ｕｎ−１）の情報を検証者に一切漏らさずに、検証者に証明するのである。なお、鍵生成アルゴリズムＧｅｎにより生成された公開鍵ｐｋは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムＧｅｎにより生成された秘密鍵ｓｋは、証明者により秘密に管理されているものとする。
【０１１４】
Ｓｔｅｐ．１：
まず、証明者アルゴリズムＰは、任意に数ｗを選択する。次いで、証明者アルゴリズムＰは、擬似乱数生成器Ｇ１に数ｗを適用して１変数多項式ｒ１（ｔ），…，ｒｎ−１（ｔ）と数ｗ’を生成する。つまり、証明者アルゴリズムＰは、（ｒ１，…，ｒｎ−１，ｗ’）←Ｇ１（ｗ）を計算する。次いで、証明者アルゴリズムＰは、擬似乱数生成器Ｇ２に数ｗ’を適用してｎ変数多項式ｆ’（ｘ１，…，ｘｎ）を生成する。つまり、証明者アルゴリズムＰは、ｆ’←Ｇ２（ｗ’）を計算する。
【０１１５】
Ｓｔｅｐ．１（続き）：
次いで、証明者アルゴリズムＰは、（ｚ１（ｔ），…，ｚｎ−１（ｔ））←（ｕ１（ｔ）−ｒ１（ｔ），…，ｕｎ−１（ｔ）−ｒｎ−１（ｔ））を計算する。この計算は、秘密鍵（ｕ１，…，ｕｎ−１）を１変数多項式（ｒ１，…，ｒｎ−１）によりマスクする操作に相当する。さらに、証明者アルゴリズムＰは、ｆ”（ｘ１，…，ｘｎ）←ｆ（ｘ１＋ｒ１（ｘｎ），…，ｘｎ−１＋ｒｎ−１（ｘｎ），ｘｎ）＋ｆ’（ｘ１，…，ｘｎ）を計算する。この計算は、ｘ１，…，ｘｎについての多項式ｆ（ｘ１＋ｒ１（ｘｎ），…，ｘｎ−１＋ｒｎ−１（ｘｎ），ｘｎ）を多項式ｆ’（ｘ１，…，ｘｎ）によりマスクする操作に相当する。
【０１１６】
Ｓｔｅｐ．１（続き）：
次いで、証明者アルゴリズムＰは、ｆ”（ｚ１（ｔ），…，ｚｎ−１（ｔ），ｔ）とｚ１，…，ｚｎ−１のハッシュ値ｃ１を生成する。つまり、証明者アルゴリズムＰは、ｃ１←Ｈ１（ｆ”（ｚ１（ｔ），…，ｚｎ−１（ｔ），ｔ），ｚ１，…，ｚｎ−１）を計算する。また、証明者アルゴリズムＰは、数ｗ’のハッシュ値ｃ２を生成する。つまり、証明者アルゴリズムＰは、ｃ２←Ｈ２（ｗ’）を計算する。さらに、証明者アルゴリズムＰは、多項式ｆ”のハッシュ値ｃ３を生成する。つまり、証明者アルゴリズムＰは、ｃ３←Ｈ３（ｆ”）を計算する。なお、上記のＨ１（…）、Ｈ２（…）、Ｈ３（…）は、ハッシュ関数である。また、ハッシュ値（ｃ１，ｃ２，ｃ３）はメッセージである。
【０１１７】
Ｓｔｅｐ．１で生成されたメッセージ（ｃ１，ｃ２，ｃ３）は、検証者に送られる。
【０１１８】
Ｓｔｅｐ．２：
検証者アルゴリズムＶは、３つの検証パターンのうち、どの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムＶは、選択した検証パターンを表す要求ｄ∈｛０，１，２｝を証明者に送る。
【０１１９】
Ｓｔｅｐ．３：
証明者アルゴリズムＰは、検証者から受けた要求ｄに応じて検証者に送り返す情報σを生成する。もしｄ＝０の場合、証明者アルゴリズムＰは、情報σ＝ｗを生成する。また、ｄ＝１の場合、証明者アルゴリズムＰは、情報σ＝（ｗ’，ｚ１，…，ｚｎ−１）を生成する。そして、ｄ＝２の場合、証明者アルゴリズムＰは、情報σ＝（ｆ”，ｚ１，…，ｚｎ−１）を生成する。このようにして生成された情報σは、証明者アルゴリズムＰにより検証者に送られる。
【０１２０】
Ｓｔｅｐ．４：
検証者アルゴリズムＶは、証明者から受け取った情報σを利用して以下の検証処理を実行する。
【０１２１】
ｄ＝０の場合、検証者アルゴリズムＶは、（ｒ’１，…，ｒ’ｎ−１，ｗ”）←Ｇ１（σ）を計算する。さらに、検証者アルゴリズムＶは、ｆ'''←Ｇ２（ｗ”）を計算する。そして、検証者アルゴリズムＶは、ｃ２＝Ｈ２（ｗ”）の等号が成り立つか否かを検証する。また、検証者アルゴリズムＶは、ｃ３＝Ｈ３（ｆ（ｘ１＋ｒ’１（ｘｎ），…，ｘｎ−１＋ｒ’ｎ−１（ｘｎ），ｘｎ）＋ｆ'''（ｘ１，…，ｘｎ））の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、これらの検証が全て成功した場合に認証成功を示す値１を出力し、検証に失敗があった場合に認証失敗を示す値０を出力する。
【０１２２】
ｄ＝１の場合、検証者アルゴリズムＶは、（ｗ”，ｚ’１，…，ｚ’ｎ−１）←σを計算する。さらに、検証者アルゴリズムＶは、ｆ'''←Ｇ２（ｗ”）を計算する。そして、検証者アルゴリズムＶは、ｃ１＝Ｈ１（ｆ'''（ｚ’１（ｔ），…，ｚ’ｎ−１（ｔ），ｔ），ｚ’１，…，ｚ’ｎ−１））の等号が成り立つか否かを検証する。また、検証者アルゴリズムＶは、ｃ２＝Ｈ２（ｗ”）の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、これらの検証が全て成功した場合に認証成功を示す値１を出力し、検証に失敗があった場合に認証失敗を示す値０を出力する。
【０１２３】
ｄ＝２の場合、検証者アルゴリズムＶは、（ｆ''''，ｚ’１，…，ｚ’ｎ−１）←σを計算する。そして、検証者アルゴリズムＶは、ｃ１＝Ｈ１（ｆ'''（ｚ’１（ｔ），…，ｚ’ｎ−１（ｔ），ｔ），ｚ’１，…，ｚ’ｎ−１））の等号が成り立つか否かを検証する。さらに、検証者アルゴリズムＶは、ｃ３＝Ｈ３（ｆ''''）の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、これらの検証が全て成功した場合に認証成功を示す値１を出力し、検証に失敗があった場合に認証失敗を示す値０を出力する。
【０１２４】
（補足）
さて、上記Ｓｔｅｐ．１において生成されたメッセージ（ｃ１，ｃ２，ｃ３）を検証者に送った際、秘密鍵ｓｋに関する情報、（ｒ１，…，ｒｎ−１）に関する情報、（ｚ１，…，ｚｎ−１）に関する情報が検証者に一切漏れていないことに注意されたい。また、上記Ｓｔｅｐ．３において生成された情報σを検証者に送った際、ｄ＝０のときにはｚ１，…，ｚｎ−１に関する情報が検証者に一切漏れておらず、ｄ＝１，２のときにはｒ１，…，ｒｎ−１に関する情報が検証者に一切漏れていないことに注意されたい。
【０１２５】
（本手法とＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式との主な相違点について）
先に説明したように、ＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式において、検証者は、２通りの検証パターンしか要求しなかった。一方、本手法の場合、検証者は、３通りの検証パターンを要求する可能性がある。そして、具体的な相違点として、ＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式の場合には本手法のｄ＝１に対応するｆ’（ｚ１（ｔ），…，ｚｎ−１（ｔ），ｔ）を用いた検証が実行されていなかった点が挙げられる。
【０１２６】
本手法の場合、ｄ＝１の検証パターンと、ｄ＝２の検証パターンにおいて、ｃ１＝Ｈ１（ｆ’（ｚ１（ｔ），…，ｚｎ−１（ｔ），ｔ），ｚ１，…，ｚｎ−１）の検証と、ｃ１＝Ｈ１（ｆ”（ｚ１（ｔ），…，ｚｎ−１（ｔ），ｔ），ｚ１，…，ｚｎ−１）の検証が行われており、両方の検証を通過するならばｆ’（ｚ１（ｔ），…，ｚｎ−１（ｔ），ｔ）＝ｆ”（ｚ１（ｔ），…，ｚｎ−１（ｔ），ｔ）となることが保証されている。こうした点が、本手法とＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式との主な相違点である。
【０１２７】
なお、ＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式に対し、単純に、本手法のｄ＝１に対応する検証パターンを追加しても、ＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式が抱える安全性の問題は解消されない。例えば、ＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式において、ｖ＝Ｈ２（Ｘ’（ｚｘ（ｔ），ｚｙ（ｔ），ｔ），ｚｘ（ｔ），ｚｙ（ｔ））の検証を追加しても安全性の問題は解消されない。図４に示したように、ＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式の場合、１パス目で既にＸ”の情報を送信してしまっているため、上記追加の検証を行うためにＸ’の情報を検証者に与えると、ｒｘ（ｔ）、ｒｙ（ｔ）に関する情報が漏れ、零知識性を失ってしまう。
【０１２８】
一方、本手法の場合、１パス目ではｆ’、ｆ”、ｒ１，…，ｒｎ−１，ｚ１，…，ｚｎ−１の情報を検証者に送らず、それらのハッシュ値のみを検証者に送っている。そして、３パス目で検証に必要な最低限の情報のみを検証者に対して送るように証明者アルゴリズムＰが設計されているため、本手法の対話プロトコルでは零知識性が担保されている。また、本手法では、１パス目でハッシュ値を送ることにより、１パス目で証明者アルゴリズムＰが用いた乱数を、３パス目で別の乱数であったかのように偽装できない仕組みを設けている。一方、ＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式では、Ｘ’に関する情報やハッシュ値を１パス目で送っていないため、３パス目では別のＸ’を利用したかのように偽装される可能性がある。本手法とＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式との間には、このような相違点も存在する。
【０１２９】
（本手法における健全性について）
本手法の健全性は、検証者の全ての要求ｄ＝０，１，２に対して、証明者がメッセージ（ｃ１，ｃ２，ｃ３）に対する正しい情報σを回答したならば、その回答内容から、下記の式（６）及び式（７）を満たすｆ''''、ｆ'''、ｒ’１，…，ｒ’ｎ−１、ｚ’１，…ｚ’ｎ−１が計算できるということから保証されている。なお、このことはＡＳＳ−ＣＣ−ＩＰ公開鍵認証方式においては保証されていない。
【０１３０】
【数６】
0005593850.tif 000007
【０１３１】
このようなロジックが保証されることにより、代数曲面上の求セクション問題を解かない限りにおいて２／３より高い確率で偽証することは不可能であることが保証される。つまり、検証者の要求ｄ＝０，１，２の全てに正しく回答するためには、偽証者が上記の式（６）及び式（７）を満たすｆ''''、ｆ'''、ｒ’１，…，ｒ’ｎ−１、ｚ’１，…ｚ’ｎ−１を計算できる必要がある。言い換えると、偽証者はｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす（ｕ１，…，ｕｎ−１）を計算できる必要がある。なお、検証者の要求ｄ＝０，１，２の高々２つまでに偽証者が正しく回答する可能性はある。そのため、偽証の成功確率は２／３となる。上記の対話プロトコルは十分な回数実行される。そのため、偽証の成功確率は無視できるほど小さくすることができる。
【０１３２】
（変形例）
上記の証明者アルゴリズムＰは、メッセージｃ３として、ｆ”（ｚ１（ｔ），…，ｚｎ−１（ｔ），ｔ）とｚ１，…，ｚｎ−１のハッシュ値を用いていた。しかし、ｆ”（ｚ１（ｔ），…，ｚｎ−１（ｔ），ｔ）＝ｆ’（ｚ１（ｔ），…，ｚｎ−１（ｔ），ｔ）であるため、証明者アルゴリズムＰは、メッセージｃ３として、ｆ’（ｚ１（ｔ），…，ｚｎ−１（ｔ），ｔ）とｚ１，…，ｚｎ−１のハッシュ値を用いてもよい。また、証明者アルゴリズムＰは、ｆ”（ｚ１（ｔ），…，ｚｎ−１（ｔ），ｔ）のハッシュ値と、ｚ１，…，ｚｎ−１のハッシュ値とを別々に計算し、それぞれをメッセージとして検証者に送るようにしてもよい。
【０１３３】
上記の証明者アルゴリズムＰは、数ｗに擬似乱数生成器Ｇ１を適用して１変数多項式ｒ１（ｔ），…，ｒｎ−１（ｔ）と数ｗ’を生成している。また、上記の証明者アルゴリズムＰは、数ｗ’を擬似乱数生成器Ｇ２に適用してｎ変数多項式ｆ’（ｘ１，…，ｘｎ）を生成している。しかし、証明者アルゴリズムＰは、最初からｗ＝（ｒ１（ｔ），…，ｒｎ−１（ｔ），ｗ’）を算出し、Ｇ１を恒等写像としてもよい。また、この場合には、数ｗをＧ１に適用する必要はない。なお、Ｇ２についても同様である。
【０１３４】
上記の方式では、ハッシュ関数Ｈ１，Ｈ２，Ｈ３を用いてｃ１，ｃ２，ｃ３を計算しているが、ハッシュ関数の代わりにコミットメント方式ＣＯＭを用いてもよい。コミットメント関数ＣＯＭは、文字列Ｓと乱数ρの２つを引数にとる関数である。コミットメント関数の例としては、Ｓｈａｉ  ＨａｌｅｖｉとＳｉｌｖｉｏ  Ｍｉｃａｌｉによって国際会議ＣＲＹＰＴＯ１９９６で発表された方式などがある。
【０１３５】
このコミットメント関数を用いる場合、ｃ１，ｃ２，ｃ３を計算する前に、乱数ρ１，ρ２，ρ３を用意し、ハッシュ関数Ｈ１（・），Ｈ２（・），Ｈ３（・）を適用する代わりにコミットメント関数ＣＯＭ（・，ρ１），ＣＯＭ（・，ρ２），ＣＯＭ（・，ρ２）を適用することによりｃ１，ｃ２，ｃ３を生成する。また、この変形例では、検証部で計算するＣｉを生成するために必要なρｉを回答情報に含めることになる。なお、この変形手法は、後述の全ての方式について適用可能である。
【０１３６】
以上、本手法に係る基本的なアルゴリズム構成について説明した。
【０１３７】
［２−２：拡張アルゴリズム］
次に、図７を参照しながら、本手法を拡張した公開鍵認証方式（以下、拡張手法）のアルゴリズムについて説明する。図７は、拡張手法に基づく対話プロトコルの流れを説明するための説明図である。この拡張手法は、１パス目に送信するメッセージ（ｃ１，ｃ２，ｃ３）を１つのハッシュ値ｃに変換して検証者に送る方式である。また、この拡張手法では、１パス目にハッシュ値ｃを送るように対話プロトコルを構成するため、３パス目で送る情報σから復元できないメッセージを情報σと共に検証者に送る。このように拡張することで、対話プロトコルの中で検証者に送るハッシュ値の数を減らすことが可能になり、通信するデータサイズを削減することができる。以下、拡張方式における各アルゴリズムの内容について詳細に説明する。
【０１３８】
（鍵生成アルゴリズムＧｅｎ）
鍵生成アルゴリズムＧｅｎは、環Ｋ上で定義されるｎ変数の多次多項式ｆ０（ｘ１，…，ｘｎ）と、１変数の多次多項式ｕ１（ｔ），…，ｕｎ−１（ｔ）を生成する。次に、鍵生成アルゴリズムＧｅｎは、ｃ（ｔ）←ｆ０（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）を計算する。そして、鍵生成アルゴリズムＧｅｎは、ｆ（ｘ１，…，ｘｎ）＝ｆ０（ｘ１，…，ｘｎ）−ｃ（ｘｎ）を計算し、ｆを公開鍵ｐｋに設定する。また、鍵生成アルゴリズムＧｅｎは、（ｕ１，…，ｕｎ−１）を秘密鍵ｓｋに設定する。ここで、ｆ０（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たすことに注意されたい。
【０１３９】
（証明者アルゴリズムＰ、検証者アルゴリズムＶ）
次に、図７を参照しながら、対話プロトコルにおける証明者アルゴリズムＰと検証者アルゴリズムＶによる処理について説明する。この対話プロトコルは、「証明者がｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）を満たす（ｕ１，…，ｕｎ−１）を知っていること」を（ｕ１，…，ｕｎ−１）の情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムＧｅｎにより生成された公開鍵ｐｋは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムＧｅｎにより生成された秘密鍵ｓｋは、証明者により秘密に管理されているものとする。
【０１４０】
Ｓｔｅｐ．１：
まず、証明者アルゴリズムＰは、任意に数ｗを選択する。次いで、証明者アルゴリズムＰは、擬似乱数生成器Ｇ１に数ｗを適用して１変数多項式ｒ１（ｔ），…，ｒｎ−１（ｔ）と数ｗ’を生成する。つまり、証明者アルゴリズムＰは、（ｒ１，…，ｒｎ−１，ｗ’）←Ｇ１（ｗ）を計算する。次いで、証明者アルゴリズムＰは、擬似乱数生成器Ｇ２に数ｗ’を適用してｎ変数多項式ｆ’（ｘ１，…，ｘｎ）を生成する。つまり、証明者アルゴリズムＰは、ｆ’←Ｇ２（ｗ’）を計算する。
【０１４１】
Ｓｔｅｐ．１（続き）：
次いで、証明者アルゴリズムＰは、（ｚ１（ｔ），…，ｚｎ−１（ｔ））←（ｕ１（ｔ）−ｒ１（ｔ），…，ｕｎ−１（ｔ）−ｒｎ−１（ｔ））を計算する。この計算は、秘密鍵（ｕ１，…，ｕｎ−１）を１変数多項式（ｒ１，…，ｒｎ−１）によりマスクする操作に相当する。さらに、証明者アルゴリズムＰは、ｆ”（ｘ１，…，ｘｎ）←ｆ（ｘ１＋ｒ１（ｘｎ），…，ｘｎ−１＋ｒｎ−１（ｘｎ），ｘｎ）＋ｆ’（ｘ１，…，ｘｎ）を計算する。この計算は、ｘ１，…，ｘｎについての多項式ｆ（ｘ１＋ｒ１（ｘｎ），…，ｘｎ−１＋ｒｎ−１（ｘｎ），ｘｎ）を多項式ｆ’（ｘ１，…，ｘｎ）によりマスクする操作に相当する。
【０１４２】
Ｓｔｅｐ．１（続き）：
次いで、証明者アルゴリズムＰは、ｆ”（ｚ１（ｔ），…，ｚｎ−１（ｔ），ｔ）とｚ１，…，ｚｎ−１のハッシュ値ｃ１を生成する。つまり、証明者アルゴリズムＰは、ｃ１←Ｈ１（ｆ”（ｚ１（ｔ），…，ｚｎ−１（ｔ），ｔ），ｚ１，…，ｚｎ−１）を計算する。また、証明者アルゴリズムＰは、数ｗ’のハッシュ値ｃ２を生成する。つまり、証明者アルゴリズムＰは、ｃ２←Ｈ２（ｗ’）を計算する。さらに、証明者アルゴリズムＰは、多項式ｆ”のハッシュ値ｃ３を生成する。つまり、証明者アルゴリズムＰは、ｃ３←Ｈ３（ｆ”）を計算する。なお、上記のＨ１（…）、Ｈ２（…）、Ｈ３（…）は、ハッシュ関数である。また、ハッシュ値（ｃ１、ｃ２、ｃ３）はメッセージである。
【０１４３】
Ｓｔｅｐ．１（続き）：
拡張方式の場合、証明者アルゴリズムＰは、メッセージ（ｃ１，ｃ２，ｃ３）をハッシュ関数Ｈに適用してハッシュ値ｃを生成する。そして、証明者アルゴリズムＰは、生成したハッシュ値ｃを検証者に送る。
【０１４４】
Ｓｔｅｐ．２：
検証者アルゴリズムＶは、３つの検証パターンのうち、どの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムＶは、選択した検証パターンを表す要求ｄ∈｛０，１，２｝を証明者に送る。
【０１４５】
Ｓｔｅｐ．３：
証明者アルゴリズムＰは、検証者から受けた要求ｄに応じて検証者に送り返す情報σを生成する。もしｄ＝０の場合、証明者アルゴリズムＰは、情報（σ，ｃ＊）＝（ｗ，ｃ１）を生成する。また、ｄ＝１の場合、証明者アルゴリズムＰは、情報（σ，ｃ＊）＝（ｗ’，ｚ１，…，ｚｎ−１，ｃ３）を生成する。そして、ｄ＝２の場合、証明者アルゴリズムＰは、情報（σ，ｃ＊）＝（ｆ”，ｚ１，…，ｚｎ−１，ｃ２）を生成する。このようにして生成された情報（σ，ｃ＊）は、証明者アルゴリズムＰにより検証者に送られる。
【０１４６】
Ｓｔｅｐ．４：
検証者アルゴリズムＶは、証明者から受け取った情報（σ，ｃ＊）を利用して以下の検証処理を実行する。
【０１４７】
ｄ＝０の場合、検証者アルゴリズムＶは、（ｒ’１，…，ｒ’ｎ−１，ｗ”）←Ｇ１（σ）を計算する。次いで、検証者アルゴリズムＶは、ｆ'''←Ｇ２（ｗ”）を計算する。次いで、検証者アルゴリズムＶは、ｃ’２＝Ｈ２（ｗ”）を計算する。次いで、検証者アルゴリズムＶは、ｃ’３＝Ｈ３（ｆ（ｘ１＋ｒ’１（ｘｎ），…，ｘｎ−１＋ｒ’ｎ−１（ｘｎ），ｘｎ）＋ｆ'''（ｘ１，…，ｘｎ））を計算する。その後、検証者アルゴリズムＶは、ｃ＝Ｈ（ｃ＊，ｃ’２，ｃ’３）の等号が成り立つか否かを検証する。そして、検証者アルゴリズムＶは、検証が成功した場合に認証成功を示す値１を出力し、検証が失敗した場合に認証失敗を示す値０を出力する。
【０１４８】
ｄ＝１の場合、検証者アルゴリズムＶは、（ｗ”，ｚ’１，…，ｚ’ｎ−１）←σを計算する。次いで、検証者アルゴリズムＶは、ｆ'''←Ｇ２（ｗ”）を計算する。次いで、検証者アルゴリズムＶは、ｃ’１＝Ｈ１（ｆ'''（ｚ’１（ｔ），…，ｚ’ｎ−１（ｔ），ｔ），ｚ’１，…，ｚ’ｎ−１））を計算する。次いで、検証者アルゴリズムＶは、ｃ’２＝Ｈ２（ｗ”）を計算する。その後、検証者アルゴリズムＶは、ｃ＝Ｈ（ｃ’１，ｃ’２，ｃ＊）の等号が成り立つか否かを検証する。そして、検証者アルゴリズムＶは、検証が成功した場合に認証成功を示す値１を出力し、検証が失敗した場合に認証失敗を示す値０を出力する。
【０１４９】
ｄ＝２の場合、検証者アルゴリズムＶは、（ｆ''''，ｚ’１，…，ｚ’ｎ−１）←σを計算する。次いで、検証者アルゴリズムＶは、ｃ’１＝Ｈ１（ｆ'''（ｚ’１（ｔ），…，ｚ’ｎ−１（ｔ），ｔ），ｚ’１，…，ｚ’ｎ−１））を計算する。次いで、検証者アルゴリズムＶは、ｃ’３＝Ｈ３（ｆ''''）を計算する。その後、検証者アルゴリズムＶは、ｃ＝Ｈ（ｃ’１，ｃ＊，ｃ’３）の等号が成り立つか否かを検証する。そして、検証者アルゴリズムＶは、検証が成功した場合に認証成功を示す値１を出力し、検証が失敗した場合に認証失敗を示す値０を出力する。
【０１５０】
以上、拡張方式の対話プロトコルにおける各アルゴリズムの処理について説明した。このように拡張することで、対話プロトコルの中で検証者に送るハッシュ値の数を減らすことが可能になり、通信するデータサイズを削減することができる。
【０１５１】
［２−３：並列化アルゴリズム］
さて、先に述べた通り、本手法又は拡張手法に係る対話プロトコルを適用すれば、偽証が成功する確率を２／３以下に抑制することができる。従って、この対話プロトコルを２回実行すれば、偽証が成功する確率を（２／３）２以下に抑制することができる。同様に、この対話プロトコルをＮ回実行すると、偽証が成功する確率は（２／３）Ｎとなり、Ｎを十分に大きい数（例えば、Ｎ＝１４０）にすれば、偽証が成功する確率は無視できる程度に小さくなる。例えば、本手法に係る対話プロトコルを並列的にＮ回実行するアルゴリズムは図８のようになる。以下、図８を参照しながら、並列的に対話プロトコルをＮ回実行する各アルゴリズムの内容について説明する。
【０１５２】
（鍵生成アルゴリズムＧｅｎ）
鍵生成アルゴリズムＧｅｎは、環Ｋ上で定義されるｎ変数の多次多項式ｆ０（ｘ１，…，ｘｎ）と、１変数の多次多項式ｕ１（ｔ），…，ｕｎ−１（ｔ）を生成する。次に、鍵生成アルゴリズムＧｅｎは、ｃ（ｔ）←ｆ０（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）を計算する。そして、鍵生成アルゴリズムＧｅｎは、ｆ（ｘ１，…，ｘｎ）＝ｆ０（ｘ１，…，ｘｎ）−ｃ（ｘｎ）を計算し、ｆを公開鍵ｐｋに設定する。また、鍵生成アルゴリズムＧｅｎは、（ｕ１，…，ｕｎ−１）を秘密鍵ｓｋに設定する。ここで、ｆ０（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たすことに注意されたい。
【０１５３】
（証明者アルゴリズムＰ、検証者アルゴリズムＶ）
次に、図８を参照しながら、対話プロトコルにおける証明者アルゴリズムＰと検証者アルゴリズムＶによる処理について説明する。この対話プロトコルは、「証明者がｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）を満たす（ｕ１，…，ｕｎ−１）を知っていること」を（ｕ１，…，ｕｎ−１）の情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムＧｅｎにより生成された公開鍵ｐｋは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムＧｅｎにより生成された秘密鍵ｓｋは、証明者により秘密に管理されているものとする。
【０１５４】
Ｓｔｅｐ．１：
まず、証明者アルゴリズムＰは、ｉ＝１〜Ｎについて、以下の処理（１）〜処理（８）を実行する。（処理１）証明者アルゴリズムＰは、任意に数ｗｉを選択する。（処理２）証明者アルゴリズムＰは、擬似乱数生成器Ｇ１に数ｗｉを適用して１変数多項式ｒ１，ｉ（ｔ），…，ｒｎ−１，ｉ（ｔ）と数ｗ’ｉを生成する。つまり、証明者アルゴリズムＰは、（ｒ１，ｉ，…，ｒｎ−１，ｉ，ｗ’ｉ）←Ｇ１（ｗｉ）を計算する。（処理３）証明者アルゴリズムＰは、擬似乱数生成器Ｇ２に数ｗ’ｉを適用してｎ変数多項式ｆ’ｉ（ｘ１，…，ｘｎ）を生成する。つまり、証明者アルゴリズムＰは、ｆ’ｉ←Ｇ２（ｗ’ｉ）を計算する。
【０１５５】
Ｓｔｅｐ．１（続き）：
（処理４）証明者アルゴリズムＰは、（ｚ１，ｉ（ｔ），…，ｚｎ−１，ｉ（ｔ））←（ｕ１，ｉ（ｔ）−ｒ１，ｉ（ｔ），…，ｕｎ−１，ｉ（ｔ）−ｒｎ−１，ｉ（ｔ））を計算する。この計算は、秘密鍵（ｕ１，ｉ，…，ｕｎ−１，ｉ）を１変数多項式（ｒ１，ｉ，…，ｒｎ−１，ｉ）によりマスクする操作に相当する。（処理５）証明者アルゴリズムＰは、ｆ”ｉ（ｘ１，…，ｘｎ）←ｆ（ｘ１＋ｒ１，ｉ（ｘｎ），…，ｘｎ−１＋ｒｎ−１，ｉ（ｘｎ），ｘｎ）＋ｆ’ｉ（ｘ１，…，ｘｎ）を計算する。この計算は、ｘ１，…，ｘｎについての多項式ｆ（ｘ１＋ｒ１，ｉ（ｘｎ），…，ｘｎ−１＋ｒｎ−１，ｉ（ｘｎ），ｘｎ）を多項式ｆ’ｉ（ｘ１，…，ｘｎ）によりマスクする操作に相当する。
【０１５６】
Ｓｔｅｐ．１（続き）：
（処理６）証明者アルゴリズムＰは、ｆ”ｉ（ｚ１，ｉ（ｔ），…，ｚｎ−１，ｉ（ｔ），ｔ）とｚ１，ｉ，…，ｚｎ−１，ｉのハッシュ値ｃ１，ｉを生成する。つまり、証明者アルゴリズムＰは、ｃ１，ｉ←Ｈ１（ｆ”ｉ（ｚ１，ｉ（ｔ），…，ｚｎ−１，ｉ（ｔ），ｔ），ｚ１，ｉ，…，ｚｎ−１，ｉ）を計算する。（処理７）証明者アルゴリズムＰは、数ｗ’ｉのハッシュ値ｃ２，ｉを生成する。つまり、証明者アルゴリズムＰは、ｃ２，ｉ←Ｈ２（ｗ’ｉ）を計算する。（処理８）証明者アルゴリズムＰは、多項式ｆ”ｉのハッシュ値ｃ３，ｉを生成する。つまり、証明者アルゴリズムＰは、ｃ３，ｉ←Ｈ３（ｆ”ｉ）を計算する。なお、上記のＨ１（…）、Ｈ２（…）、Ｈ３（…）は、ハッシュ関数である。また、ハッシュ値（ｃ１，ｉ、ｃ２，ｉ、ｃ３，ｉ）はメッセージである。
【０１５７】
ｉ＝１〜Ｎについて、上記の（処理１）〜（処理８）が実行された後、Ｓｔｅｐ．１で生成されたメッセージ（ｃ１，ｉ、ｃ２，ｉ、ｃ３，ｉ）（ｉ＝１〜Ｎ）は、検証者に送られる。
【０１５８】
Ｓｔｅｐ．２：
検証者アルゴリズムＶは、ｉ＝１〜Ｎのそれぞれについて、３つの検証パターンのうち、どの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムＶは、選択した検証パターンを表す要求ｄｉ∈｛０，１，２｝（ｉ＝１〜Ｎ）を証明者に送る。
【０１５９】
Ｓｔｅｐ．３：
証明者アルゴリズムＰは、検証者から受けた要求ｄｉに応じて検証者に送り返す情報σｉを生成する。ここで、証明者アルゴリズムＰは、ｉ＝１〜Ｎについて、以下の（処理１）〜（処理３）を実行する。（処理１）ｄｉ＝０の場合、証明者アルゴリズムＰは、情報σｉ＝ｗｉを生成する。（処理２）ｄｉ＝１の場合、証明者アルゴリズムＰは、情報σｉ＝（ｗ’ｉ，ｚ１，ｉ，…，ｚｎ−１，ｉ）を生成する。（処理３）ｄｉ＝２の場合、証明者アルゴリズムＰは、情報σｉ＝（ｆ”ｉ，ｚ１，ｉ，…，ｚｎ−１，ｉ）を生成する。上記（処理１）〜（処理３）の判定及び処理が実行された後、情報σｉ（ｉ＝１〜Ｎ）は、証明者アルゴリズムＰにより検証者に送られる。
【０１６０】
Ｓｔｅｐ．４：
検証者アルゴリズムＶは、証明者から受け取った情報σｉ（ｉ＝１〜Ｎ）を利用して以下の検証処理を実行する。なお、以下の処理は、ｉ＝１〜Ｎについて実行される。
【０１６１】
ｄｉ＝０の場合、検証者アルゴリズムＶは、（ｒ’１，ｉ，…，ｒ’ｎ−１，ｉ，ｗ”ｉ）←Ｇ１（σｉ）を計算する。さらに、検証者アルゴリズムＶは、ｆ'''ｉ←Ｇ２（ｗ”ｉ）を計算する。そして、検証者アルゴリズムＶは、ｃ２，ｉ＝Ｈ２（ｗ”ｉ）の等号が成り立つか否かを検証する。また、検証者アルゴリズムＶは、ｃ３，ｉ＝Ｈ３（ｆ（ｘ１＋ｒ’１，ｉ（ｘｎ），…，ｘｎ−１＋ｒ’ｎ−１，ｉ（ｘｎ），ｘｎ）＋ｆ'''ｉ（ｘ１，…，ｘｎ））の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、これらの検証が全て成功した場合に認証成功を示す値１を出力し、検証に失敗があった場合に認証失敗を示す値０を出力する。
【０１６２】
ｄｉ＝１の場合、検証者アルゴリズムＶは、（ｗ”ｉ，ｚ’１，ｉ，…，ｚ’ｎ−１，ｉ）←σｉを計算する。さらに、検証者アルゴリズムＶは、ｆ'''ｉ←Ｇ２（ｗ”ｉ）を計算する。そして、検証者アルゴリズムＶは、ｃ１，ｉ＝Ｈ１（ｆ'''ｉ（ｚ’１，ｉ（ｔ），…，ｚ’ｎ−１，ｉ（ｔ），ｔ），ｚ’１，ｉ，…，ｚ’ｎ−１，ｉ））の等号が成り立つか否かを検証する。また、検証者アルゴリズムＶは、ｃ２＝Ｈ２（ｗ”ｉ）の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、これらの検証が全て成功した場合に認証成功を示す値１を出力し、検証に失敗があった場合に認証失敗を示す値０を出力する。
【０１６３】
ｄｉ＝２の場合、検証者アルゴリズムＶは、（ｆ''''ｉ，ｚ’１，ｉ，…，ｚ’ｎ−１，ｉ）←σｉを計算する。そして、検証者アルゴリズムＶは、ｃ１，ｉ＝Ｈ１（ｆ'''ｉ（ｚ’１，ｉ（ｔ），…，ｚ’ｎ−１，ｉ（ｔ），ｔ），ｚ’１，ｉ，…，ｚ’ｎ−１，ｉ））の等号が成り立つか否かを検証する。さらに、検証者アルゴリズムＶは、ｃ３，ｉ＝Ｈ３（ｆ''''ｉ）の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、これらの検証が全て成功した場合に認証成功を示す値１を出力し、検証に失敗があった場合に認証失敗を示す値０を出力する。
【０１６４】
以上、本手法の対話プロトコルを並列的に実行する方法について説明した。上記のように、本手法の対話プロトコルを繰り返し実行することにより、偽証が成功する確率を無視できる程度まで低減させることが可能になる。
【０１６５】
［２−４：非対話型アルゴリズム］
これまで３パスの公開鍵認証方式について説明してきた。しかし、本手法においては、２パス目で検証者から証明者に送られる情報が検証パターンを示す要求ｄ（実際には単なる乱数）だけであるため、１パスの公開鍵認証方式（以下、非対話型方式）に変形することができる。なお、非対話型方式に係る各アルゴリズムの内容を図９に示した。以下、図９を参照しながら、非対話型方式に係る各アルゴリズムの内容について説明する。
【０１６６】
（鍵生成アルゴリズムＧｅｎ）
鍵生成アルゴリズムＧｅｎは、環Ｋ上で定義されるｎ変数の多次多項式ｆ０（ｘ１，…，ｘｎ）と、１変数の多次多項式ｕ１（ｔ），…，ｕｎ−１（ｔ）を生成する。次に、鍵生成アルゴリズムＧｅｎは、ｃ（ｔ）←ｆ０（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）を計算する。そして、鍵生成アルゴリズムＧｅｎは、ｆ（ｘ１，…，ｘｎ）＝ｆ０（ｘ１，…，ｘｎ）−ｃ（ｘｎ）を計算し、ｆを公開鍵ｐｋに設定する。また、鍵生成アルゴリズムＧｅｎは、（ｕ１，…，ｕｎ−１）を秘密鍵ｓｋに設定する。ここで、ｆ０（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たすことに注意されたい。
【０１６７】
（証明者アルゴリズムＰ、検証者アルゴリズムＶ）
次に、図９を参照しながら、対話プロトコルにおける証明者アルゴリズムＰと検証者アルゴリズムＶによる処理について説明する。この対話プロトコルは、「証明者がｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）を満たす（ｕ１，…，ｕｎ−１）を知っていること」を（ｕ１，…，ｕｎ−１）の情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムＧｅｎにより生成された公開鍵ｐｋは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムＧｅｎにより生成された秘密鍵ｓｋは、証明者により秘密に管理されているものとする。
【０１６８】
Ｓｔｅｐ．１：
まず、証明者アルゴリズムＰは、ｉ＝１〜Ｎについて、以下の処理（１）〜処理（８）を実行する。（処理１）証明者アルゴリズムＰは、任意に数ｗｉを選択する。（処理２）証明者アルゴリズムＰは、擬似乱数生成器Ｇ１に数ｗｉを適用して１変数多項式ｒ１，ｉ（ｔ），…，ｒｎ−１，ｉ（ｔ）と数ｗ’ｉを生成する。つまり、証明者アルゴリズムＰは、（ｒ１，ｉ，…，ｒｎ−１，ｉ，ｗ’ｉ）←Ｇ１（ｗｉ）を計算する。（処理３）証明者アルゴリズムＰは、擬似乱数生成器Ｇ２に数ｗ’ｉを適用してｎ変数多項式ｆ’ｉ（ｘ１，…，ｘｎ）を生成する。つまり、証明者アルゴリズムＰは、ｆ’ｉ←Ｇ２（ｗ’ｉ）を計算する。
【０１６９】
Ｓｔｅｐ．１（続き）：
（処理４）証明者アルゴリズムＰは、（ｚ１，ｉ（ｔ），…，ｚｎ−１，ｉ（ｔ））←（ｕ１，ｉ（ｔ）−ｒ１，ｉ（ｔ），…，ｕｎ−１，ｉ（ｔ）−ｒｎ−１，ｉ（ｔ））を計算する。この計算は、秘密鍵（ｕ１，ｉ，…，ｕｎ−１，ｉ）を１変数多項式（ｒ１，ｉ，…，ｒｎ−１，ｉ）によりマスクする操作に相当する。（処理５）証明者アルゴリズムＰは、ｆ”ｉ（ｘ１，…，ｘｎ）←ｆ（ｘ１＋ｒ１，ｉ（ｘｎ），…，ｘｎ−１＋ｒｎ−１，ｉ（ｘｎ），ｘｎ）＋ｆ’ｉ（ｘ１，…，ｘｎ）を計算する。この計算は、ｘ１，…，ｘｎについての多項式ｆ（ｘ１＋ｒ１，ｉ（ｘｎ），…，ｘｎ−１＋ｒｎ−１，ｉ（ｘｎ），ｘｎ）を多項式ｆ’ｉ（ｘ１，…，ｘｎ）によりマスクする操作に相当する。
【０１７０】
Ｓｔｅｐ．１（続き）：
（処理６）証明者アルゴリズムＰは、ｆ”ｉ（ｚ１，ｉ（ｔ），…，ｚｎ−１，ｉ（ｔ），ｔ）とｚ１，ｉ，…，ｚｎ−１，ｉのハッシュ値ｃ１，ｉを生成する。つまり、証明者アルゴリズムＰは、ｃ１，ｉ←Ｈ１（ｆ”ｉ（ｚ１，ｉ（ｔ），…，ｚｎ−１，ｉ（ｔ），ｔ），ｚ１，ｉ，…，ｚｎ−１，ｉ）を計算する。（処理７）証明者アルゴリズムＰは、数ｗ’ｉのハッシュ値ｃ２，ｉを生成する。つまり、証明者アルゴリズムＰは、ｃ２，ｉ←Ｈ２（ｗ’ｉ）を計算する。（処理８）証明者アルゴリズムＰは、多項式ｆ”ｉのハッシュ値ｃ３，ｉを生成する。つまり、証明者アルゴリズムＰは、ｃ３，ｉ←Ｈ３（ｆ”ｉ）を計算する。なお、上記のＨ１（…）、Ｈ２（…）、Ｈ３（…）は、ハッシュ関数である。また、ハッシュ値（ｃ１，ｉ、ｃ２，ｉ、ｃ３，ｉ）はメッセージである。
【０１７１】
Ｓｔｅｐ．２：
次に、証明者アルゴリズムＰは、乱数Ｒを選択する。次いで、証明者アルゴリズムＰは、ｉ＝１〜Ｎについて、乱数ＲとＳｔｅｐ．１で生成したメッセージ（ｃ１，ｉ、ｃ２，ｉ、ｃ３，ｉ）をハッシュ関数Ｈに適用してｄ＝（ｄ１，…，ｄＮ）を生成する。
【０１７２】
Ｓｔｅｐ．３：
次に、証明者アルゴリズムＰは、生成したｄｉに応じて検証者に送り返す情報σｉを生成する。ここで、証明者アルゴリズムＰは、ｉ＝１〜Ｎについて、以下の（処理１）〜（処理３）を実行する。（処理１）ｄｉ＝０の場合、証明者アルゴリズムＰは、情報σｉ＝ｗｉを生成する。（処理２）ｄｉ＝１の場合、証明者アルゴリズムＰは、情報σｉ＝（ｗ’ｉ，ｚ１，ｉ，…，ｚｎ−１，ｉ）を生成する。（処理３）ｄｉ＝２の場合、証明者アルゴリズムＰは、情報σｉ＝（ｆ”ｉ，ｚ１，ｉ，…，ｚｎ−１，ｉ）を生成する。上記（処理１）〜（処理３）の判定及び処理が実行された後、乱数Ｒ、メッセージ（ｃ１，ｉ、ｃ２，ｉ、ｃ３，ｉ）及び情報σｉ（ｉ＝１〜Ｎ）は、証明者アルゴリズムＰにより検証者に送られる。
【０１７３】
Ｓｔｅｐ．４：
検証者アルゴリズムＶは、まず、証明者から受け取った乱数Ｒ、メッセージ（ｃ１，ｉ、ｃ２，ｉ、ｃ３，ｉ）及び情報σｉ（ｉ＝１〜Ｎ）をハッシュ関数Ｈに適用してｄ＝（ｄ１，…，ｄＮ）を生成する。次いで、検証者アルゴリズムＶは、情報σｉ（ｉ＝１〜Ｎ）を利用して以下の検証処理を実行する。なお、以下の処理は、ｉ＝１〜Ｎについて実行される。
【０１７４】
ｄｉ＝０の場合、検証者アルゴリズムＶは、（ｒ’１，ｉ，…，ｒ’ｎ−１，ｉ，ｗ”ｉ）←Ｇ１（σｉ）を計算する。さらに、検証者アルゴリズムＶは、ｆ'''ｉ←Ｇ２（ｗ”ｉ）を計算する。そして、検証者アルゴリズムＶは、ｃ２，ｉ＝Ｈ２（ｗ”ｉ）の等号が成り立つか否かを検証する。また、検証者アルゴリズムＶは、ｃ３，ｉ＝Ｈ３（ｆ（ｘ１＋ｒ’１，ｉ（ｘｎ），…，ｘｎ−１＋ｒ’ｎ−１，ｉ（ｘｎ），ｘｎ）＋ｆ'''ｉ（ｘ１，…，ｘｎ））の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、これらの検証が全て成功した場合に認証成功を示す値１を出力し、検証に失敗があった場合に認証失敗を示す値０を出力する。
【０１７５】
ｄｉ＝１の場合、検証者アルゴリズムＶは、（ｗ”ｉ，ｚ’１，ｉ，…，ｚ’ｎ−１，ｉ）←σｉを計算する。さらに、検証者アルゴリズムＶは、ｆ'''ｉ←Ｇ２（ｗ”ｉ）を計算する。そして、検証者アルゴリズムＶは、ｃ１，ｉ＝Ｈ１（ｆ'''ｉ（ｚ’１，ｉ（ｔ），…，ｚ’ｎ−１，ｉ（ｔ），ｔ），ｚ’１，ｉ，…，ｚ’ｎ−１，ｉ））の等号が成り立つか否かを検証する。また、検証者アルゴリズムＶは、ｃ２＝Ｈ２（ｗ”ｉ）の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、これらの検証が全て成功した場合に認証成功を示す値１を出力し、検証に失敗があった場合に認証失敗を示す値０を出力する。
【０１７６】
ｄｉ＝２の場合、検証者アルゴリズムＶは、（ｆ''''ｉ，ｚ’１，ｉ，…，ｚ’ｎ−１，ｉ）←σｉを計算する。そして、検証者アルゴリズムＶは、ｃ１，ｉ＝Ｈ１（ｆ'''ｉ（ｚ’１，ｉ（ｔ），…，ｚ’ｎ−１，ｉ（ｔ），ｔ），ｚ’１，ｉ，…，ｚ’ｎ−１，ｉ））の等号が成り立つか否かを検証する。さらに、検証者アルゴリズムＶは、ｃ３，ｉ＝Ｈ３（ｆ''''ｉ）の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、これらの検証が全て成功した場合に認証成功を示す値１を出力し、検証に失敗があった場合に認証失敗を示す値０を出力する。
【０１７７】
以上、非対話型方式に係る各アルゴリズムの内容について説明した。上記の通り、非対話型方式は、検証者が検証パターンを選択するために乱数ｄを証明者に送る代わりに、証明者アルゴリズムＰがメッセージ（ｃ１，ｉ、ｃ２，ｉ、ｃ３，ｉ）を利用してｄを生成するというものである。理想的なハッシュ関数Ｈを仮定すれば、ハッシュ値ｄがランダムに振る舞うため、証明者に都合の良いハッシュ値ｄが出ることはない。そのため、上記のような変形を行っても、十分な安全性が確保される。なお、このような変形は、拡張方式などに対しても同様に適用することが可能である。
【０１７８】
［２−５：電子署名方式への変形］
ここで、本手法を電子署名方式へと変形する方法について説明する。なお、ここでは簡単のために、上記の非対話型方式を電子署名方式に変形する方法について述べる。上記の非対話型方式における証明者と検証者を電子署名方式における署名者と検証者に対応させると、証明者のみが検証者を納得させられるという点において、電子署名方式のモデルと近似していることが分かるであろう。こうした考えをもとに、非対話型方式に基づく電子署名方式のアルゴリズム構成について詳細に説明する。
【０１７９】
（鍵生成アルゴリズムＧｅｎ）
鍵生成アルゴリズムＧｅｎは、環Ｋ上で定義されるｎ変数の多次多項式ｆ０（ｘ１，…，ｘｎ）と、１変数の多次多項式ｕ１（ｔ），…，ｕｎ−１（ｔ）を生成する。次に、鍵生成アルゴリズムＧｅｎは、ｃ（ｔ）←ｆ０（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）を計算する。そして、鍵生成アルゴリズムＧｅｎは、ｆ（ｘ１，…，ｘｎ）＝ｆ０（ｘ１，…，ｘｎ）−ｃ（ｘｎ）を計算し、ｆを検証鍵ｐｋに設定する。また、鍵生成アルゴリズムＧｅｎは、（ｕ１，…，ｕｎ−１）を署名鍵ｓｋに設定する。ここで、ｆ０（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たすことに注意されたい。
【０１８０】
（署名生成アルゴリズムＳｉｇ）
署名生成アルゴリズムＳｉｇは、ｉ＝１〜Ｎについて、以下の（処理１）〜（処理１５）を実行する。なお、署名生成アルゴリズムＳｉｇには、署名鍵ｓｋ＝（ｕ１，…，ｕｎ−１）と文書Ｍが入力されているものとする。
【０１８１】
（処理１）署名生成アルゴリズムＳｉｇは、任意に数ｗｉを選択する。（処理２）署名生成アルゴリズムＳｉｇは、擬似乱数生成器Ｇ１に数ｗｉを適用して１変数多項式ｒ１，ｉ（ｔ），…，ｒｎ−１，ｉ（ｔ）と数ｗ’ｉを生成する。つまり、署名生成アルゴリズムＳｉｇは、（ｒ１，ｉ，…，ｒｎ−１，ｉ，ｗ’ｉ）←Ｇ１（ｗｉ）を計算する。（処理３）署名生成アルゴリズムＳｉｇは、擬似乱数生成器Ｇ２に数ｗ’ｉを適用してｎ変数多項式ｆ’ｉ（ｘ１，…，ｘｎ）を生成する。つまり、署名生成アルゴリズムＳｉｇは、ｆ’ｉ←Ｇ２（ｗ’ｉ）を計算する。
【０１８２】
（処理４）署名生成アルゴリズムＳｉｇは、（ｚ１，ｉ（ｔ），…，ｚｎ−１，ｉ（ｔ））←（ｕ１，ｉ（ｔ）−ｒ１，ｉ（ｔ），…，ｕｎ−１，ｉ（ｔ）−ｒｎ−１，ｉ（ｔ））を計算する。この計算は、秘密鍵（ｕ１，ｉ，…，ｕｎ−１，ｉ）を１変数多項式（ｒ１，ｉ，…，ｒｎ−１，ｉ）によりマスクする操作に相当する。（処理５）署名生成アルゴリズムＳｉｇは、ｆ”ｉ（ｘ１，…，ｘｎ）←ｆ（ｘ１＋ｒ１，ｉ（ｘｎ），…，ｘｎ−１＋ｒｎ−１，ｉ（ｘｎ），ｘｎ）＋ｆ’ｉ（ｘ１，…，ｘｎ）を計算する。この計算は、ｘ１，…，ｘｎについての多項式ｆ（ｘ１＋ｒ１，ｉ（ｘｎ），…，ｘｎ−１＋ｒｎ−１，ｉ（ｘｎ），ｘｎ）を多項式ｆ’ｉ（ｘ１，…，ｘｎ）によりマスクする操作に相当する。
【０１８３】
（処理６）署名生成アルゴリズムＳｉｇは、ｆ”ｉ（ｚ１，ｉ（ｔ），…，ｚｎ−１，ｉ（ｔ），ｔ）とｚ１，ｉ，…，ｚｎ−１，ｉのハッシュ値ｃ１，ｉを生成する。つまり、署名生成アルゴリズムＳｉｇは、ｃ１，ｉ←Ｈ１（ｆ”ｉ（ｚ１，ｉ（ｔ），…，ｚｎ−１，ｉ（ｔ），ｔ），ｚ１，ｉ，…，ｚｎ−１，ｉ）を計算する。（処理７）署名生成アルゴリズムＳｉｇは、数ｗ’ｉのハッシュ値ｃ２，ｉを生成する。つまり、署名生成アルゴリズムＳｉｇは、ｃ２，ｉ←Ｈ２（ｗ’ｉ）を計算する。（処理８）署名生成アルゴリズムＳｉｇは、多項式ｆ”ｉのハッシュ値ｃ３，ｉを生成する。つまり、署名生成アルゴリズムＳｉｇは、ｃ３，ｉ←Ｈ３（ｆ”ｉ）を計算する。なお、上記のＨ１（…）、Ｈ２（…）、Ｈ３（…）は、ハッシュ関数である。
【０１８４】
（処理９）署名生成アルゴリズムＳｉｇは、乱数Ｒを選択する。（処理１０）署名生成アルゴリズムＳｉｇは、ｉ＝１〜Ｎについて、文書Ｍ、乱数Ｒ、及びハッシュ値（ｃ１，ｉ，ｃ２，ｉ，ｃ３，ｉ）をハッシュ関数Ｈに適用してｄ＝（ｄ１，…，ｄＮ）を生成する。つまり、署名生成アルゴリズムＳｉｇは、ｄ＝（ｄ１，…，ｄＮ）←Ｈ（Ｒ，Ｍ，ｃ１，１，…，ｃ３，Ｎ）を計算する。（処理１１）署名生成アルゴリズムＳｉｇは、生成したｄｉに応じて情報σｉを生成する。
【０１８５】
ここで、署名生成アルゴリズムＳｉｇは、ｉ＝１〜Ｎについて、以下の（処理１２）〜（処理１４）を実行する。（処理１２）ｄｉ＝０の場合、署名生成アルゴリズムＳｉｇは、情報σｉ＝ｗｉを生成する。（処理１３）ｄｉ＝１の場合、署名生成アルゴリズムＳｉｇは、情報σｉ＝（ｗ’ｉ，ｚ１，ｉ，…，ｚｎ−１，ｉ）を生成する。（処理１４）ｄｉ＝２の場合、署名生成アルゴリズムＳｉｇは、情報σｉ＝（ｆ”ｉ，ｚ１，ｉ，…，ｚｎ−１，ｉ）を生成する。
【０１８６】
（処理１５）ｉ＝１〜Ｎについて、上記（処理１２）〜（処理１４）の判定及び処理が実行された後、署名生成アルゴリズムＳｉｇは、乱数Ｒ、メッセージ（ｃ１，ｉ、ｃ２，ｉ、ｃ３，ｉ）及び情報σｉ（ｉ＝１〜Ｎ）を含む電子署名σ＝（Ｒ，ｃ１，ｉ、ｃ２，ｉ、ｃ３，ｉ，σ１，…，σＮ）を出力する。
【０１８７】
（署名検証アルゴリズムＶｅｒ）
署名検証アルゴリズムＶｅｒは、ｉ＝１〜Ｎについて、以下の全ての検証を通過すれば、電子署名σを受理し、１つでも検証を通過しなかった場合には電子署名σを拒否する。なお、署名検証アルゴリズムＶｅｒには、電子署名σと文書Ｍが入力されているものとする。まず、署名検証アルゴリズムＶｅｒは、ｄ＝（ｄ１，…，ｄＮ）←Ｈ（Ｒ，Ｍ，ｃ１，１，…，ｃ３，Ｎ）を計算する。次いで、署名検証アルゴリズムＶｅｒは、ｉ＝１〜Ｎについて、以下の（検証１）〜（検証３）を実行する。
【０１８８】
（検証１）ｄｉ＝０の場合、署名検証アルゴリズムＶｅｒは、（ｒ’１，ｉ，…，ｒ’ｎ−１，ｉ，ｗ”ｉ）←Ｇ１（σｉ）を計算する。次いで、署名検証アルゴリズムＶｅｒは、ｆ'''ｉ←Ｇ２（ｗ”ｉ）を計算する。そして、署名検証アルゴリズムＶｅｒは、ｃ２，ｉ＝Ｈ２（ｗ”ｉ）の等号が成り立つか否かを検証する。また、署名検証アルゴリズムＶｅｒは、ｃ３，ｉ＝Ｈ３（ｆ（ｘ１＋ｒ’１，ｉ（ｘｎ），…，ｘｎ−１，ｉ＋ｒ’ｎ−１，ｉ（ｘｎ），ｘｎ）＋ｆ'''ｉ（ｘ１，…，ｘｎ））の等号が成り立つか否かを検証する。署名検証アルゴリズムＶｅｒは、これらの検証が全て成功した場合に電子署名σの受理を示す値１を出力し、検証に失敗があった場合に電子署名σの拒否を示す値０を出力する。
【０１８９】
（検証２）ｄｉ＝１の場合、署名検証アルゴリズムＶｅｒは、（ｗ”ｉ，ｚ’１，ｉ，…，ｚ’ｎ−１，ｉ）←σｉを計算する。次いで、署名検証アルゴリズムＶｅｒは、ｆ'''ｉ←Ｇ２（ｗ”ｉ）を計算する。そして、署名検証アルゴリズムＶｅｒは、ｃ１，ｉ＝Ｈ１（ｆ'''ｉ（ｚ’１，ｉ（ｔ），…，ｚ’ｎ−１，ｉ（ｔ），ｔ），ｚ’１，ｉ，…，ｚ’ｎ−１，ｉ））の等号が成り立つか否かを検証する。また、署名検証アルゴリズムＶｅｒは、ｃ２＝Ｈ２（ｗ”ｉ）の等号が成り立つか否かを検証する。署名検証アルゴリズムＶｅｒは、これらの検証が全て成功した場合に電子署名σの受理を示す値１を出力し、検証に失敗があった場合に電子署名σの拒否を示す値０を出力する。
【０１９０】
（検証３）ｄｉ＝２の場合、署名検証アルゴリズムＶｅｒは、（ｆ''''ｉ，ｚ’１，ｉ，…，ｚ’ｎ−１，ｉ）←σｉを計算する。次いで、署名検証アルゴリズムＶｅｒは、ｃ１，ｉ＝Ｈ１（ｆ'''ｉ（ｚ’１，ｉ（ｔ），…，ｚ’ｎ−１，ｉ（ｔ），ｔ），ｚ’１，ｉ，…，ｚ’ｎ−１，ｉ））の等号が成り立つか否かを検証する。さらに、署名検証アルゴリズムＶｅｒは、ｃ３，ｉ＝Ｈ３（ｆ''''ｉ）の等号が成り立つか否かを検証する。署名検証アルゴリズムＶｅｒは、これらの検証が全て成功した場合に電子署名σの受理を示す値１を出力し、検証に失敗があった場合に電子署名σの拒否を示す値０を出力する。
【０１９１】
以上、本手法に基づく電子署名方式の各アルゴリズム構成について説明した。上記の電子署名方式は、代数曲面上の求セクション問題に安全性の根拠をおくものであるが、ＡＳＳ−ＣＣ電子署名方式のような安全性の問題を内包しない。なお、同様にして、上記の拡張方式に基づく電子署名方式を構築することも可能である。
【０１９２】
［２−６：具体例］
次に、図１０を参照しながら、本手法を実施する際に想定される具体的なアルゴリズム構成について説明する。図１０は、本手法の具体例を説明するための説明図である。
【０１９３】
（鍵生成アルゴリズムＧｅｎ）
鍵生成アルゴリズムＧｅｎは、環Ｋ上で定義される３変数のＤ次多項式ｆ０（ｘ，ｙ，ｔ）と、１変数の多次多項式ｕｘ（ｔ），ｕｙ（ｔ）を生成する。但し、Ｄ次多項式ｆ０（ｘ，ｙ，ｔ）は、下記の式（８）により表現される。また、１変数の多次多項式ｕｘ（ｔ）は、下記の式（９）により表現される。さらに、１変数の多次多項式ｕｙ（ｔ）は、下記の式（１０）により表現される。
【０１９４】
【数７】
0005593850.tif 000008
【０１９５】
次に、鍵生成アルゴリズムＧｅｎは、ｃ（ｔ）←ｆ０（ｕｘ（ｔ），ｕｙ（ｔ），ｔ）を計算する。そして、鍵生成アルゴリズムＧｅｎは、ｆ（ｘ，ｙ，ｔ）＝ｆ０（ｘ，ｙ，ｔ）−ｃ（ｔ）を計算し、ｆを公開鍵ｐｋに設定する。また、鍵生成アルゴリズムＧｅｎは、（ｕｘ，ｕｙ）を秘密鍵ｓｋに設定する。なお、鍵生成アルゴリズムＧｅｎにより生成されるｆは、ｘ０ｙ０ｔｋの項以外については最大でＤ次となるが、ｘ０ｙ０ｔｋの項については最大で（Ｄ＋Ｄｓ）次になる。
【０１９６】
（証明者アルゴリズムＰ、検証者アルゴリズムＶ）
次に、図１０を参照しながら、対話プロトコルにおける証明者アルゴリズムＰと検証者アルゴリズムＶによる処理について説明する。この対話プロトコルは、「証明者がｆ（ｕｘ（ｔ），ｕｙ（ｔ），ｔ）を満たす（ｕｘ，ｕｙ）を知っていること」を（ｕｘ，ｕｙ）の情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムＧｅｎにより生成された公開鍵ｐｋは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムＧｅｎにより生成された秘密鍵ｓｋは、証明者により秘密に管理されているものとする。
【０１９７】
Ｓｔｅｐ．１：
まず、証明者アルゴリズムＰは、任意に数ｗを選択する。次いで、証明者アルゴリズムＰは、擬似乱数生成器Ｇ１に数ｗを適用して１変数多項式ｒｘ（ｔ），ｒｙ（ｔ）と数ｗ’を生成する。つまり、証明者アルゴリズムＰは、（ｒｘ，ｒｙ，ｗ’）←Ｇ１（ｗ）を計算する。次いで、証明者アルゴリズムＰは、擬似乱数生成器Ｇ２に数ｗ’を適用して３変数多項式ｆ’（ｘ，ｙ，ｔ）を生成する。つまり、証明者アルゴリズムＰは、ｆ’←Ｇ２（ｗ’）を計算する。なお、多項式ｆ’の次数は多項式ｆの次数と同じにする。つまり、ｘ０ｙ０ｔｋの項以外については最大でＤ次であるが、ｘ０ｙ０ｔｋの項については最大で（Ｄ＋Ｄｓ）次になるようにする。
【０１９８】
Ｓｔｅｐ．１（続き）：
次いで、証明者アルゴリズムＰは、（ｚｘ（ｔ），ｚｙ（ｔ））←（ｕｘ（ｔ）−ｒｘ（ｔ），ｕｙ（ｔ）−ｒｙ（ｔ））を計算する。この計算は、秘密鍵（ｕｘ，ｕｙ）を１変数多項式（ｒｘ，ｒｙ）によりマスクする操作に相当する。さらに、証明者アルゴリズムＰは、ｆ”（ｘ，ｙ，ｔ）←ｆ（ｘ＋ｒｘ（ｔ），ｙ＋ｒｙ（ｔ），ｔ）＋ｆ’（ｘ，ｙ，ｔ）を計算する。この計算は、ｘ，ｙ，ｔについての多項式ｆ（ｘ＋ｒｘ（ｔ），ｙ＋ｒｙ（ｔ），ｔ）を多項式ｆ’（ｘ，ｙ，ｔ）によりマスクする操作に相当する。ここで、ｆ（ｘ＋ｒｘ（ｔ），ｙ＋ｒｙ（ｔ），ｔ）の中に現れるｒｘ（ｔ），ｒｙ（ｔ）に関する項は全てｆ’（ｘ，ｙ，ｔ）でマスクされていることに注意されたい。
【０１９９】
Ｓｔｅｐ．１（続き）：
次いで、証明者アルゴリズムＰは、ｆ”（ｚｘ（ｔ），ｚｙ（ｔ），ｔ）とｚｘ，ｚｙのハッシュ値ｃ１を生成する。つまり、証明者アルゴリズムＰは、ｃ１←Ｈ１（ｆ”（ｚｘ（ｔ），ｚｙ（ｔ），ｔ），ｚｘ，ｚｙ）を計算する。また、証明者アルゴリズムＰは、数ｗ’のハッシュ値ｃ２を生成する。つまり、証明者アルゴリズムＰは、ｃ２←Ｈ２（ｗ’）を計算する。さらに、証明者アルゴリズムＰは、多項式ｆ”のハッシュ値ｃ３を生成する。つまり、証明者アルゴリズムＰは、ｃ３←Ｈ３（ｆ”）を計算する。なお、上記のＨ１（…）、Ｈ２（…）、Ｈ３（…）は、ハッシュ関数である。また、ハッシュ値（ｃ１、ｃ２、ｃ３）はメッセージである。
【０２００】
Ｓｔｅｐ．１で生成されたメッセージ（ｃ１、ｃ２、ｃ３）は、検証者に送られる。
【０２０１】
Ｓｔｅｐ．２：
検証者アルゴリズムＶは、３つの検証パターンのうち、どの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムＶは、選択した検証パターンを表す要求ｄ∈｛０，１，２｝を証明者に送る。
【０２０２】
Ｓｔｅｐ．３：
証明者アルゴリズムＰは、検証者から受けた要求ｄに応じて検証者に送り返す情報σを生成する。もしｄ＝０の場合、証明者アルゴリズムＰは、情報σ＝ｗを生成する。また、ｄ＝１の場合、証明者アルゴリズムＰは、情報σ＝（ｗ’，ｚｘ，ｚｙ）を生成する。そして、ｄ＝２の場合、証明者アルゴリズムＰは、情報σ＝（ｆ”，ｚｘ，ｚｙ）を生成する。このようにして生成された情報σは、証明者アルゴリズムＰにより検証者に送られる。
【０２０３】
Ｓｔｅｐ．４：
検証者アルゴリズムＶは、証明者から受け取った情報σを利用して以下の検証処理を実行する。
【０２０４】
ｄ＝０の場合、検証者アルゴリズムＶは、（ｒ’ｘ，ｒ’ｙ，ｗ”）←Ｇ１（σ）を計算する。さらに、検証者アルゴリズムＶは、ｆ'''←Ｇ２（ｗ”）を計算する。そして、検証者アルゴリズムＶは、ｃ２＝Ｈ２（ｗ”）の等号が成り立つか否かを検証する。また、検証者アルゴリズムＶは、ｃ３＝Ｈ３（ｆ（ｘ＋ｒ’ｘ（ｔ），ｙ＋ｒ’ｙ（ｔ），ｔ）＋ｆ'''（ｘ，ｙ，ｔ））の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、これらの検証が全て成功した場合に認証成功を示す値１を出力し、検証に失敗があった場合に認証失敗を示す値０を出力する。
【０２０５】
ｄ＝１の場合、検証者アルゴリズムＶは、（ｗ”，ｚ’ｘ，ｚ’ｙ）←σを計算する。さらに、検証者アルゴリズムＶは、ｆ'''←Ｇ２（ｗ”）を計算する。そして、検証者アルゴリズムＶは、ｃ１＝Ｈ１（ｆ'''（ｚ’ｘ（ｔ），ｚ’ｙ（ｔ），ｔ），ｚ’ｘ，ｚ’ｙ））の等号が成り立つか否かを検証する。また、検証者アルゴリズムＶは、ｃ２＝Ｈ２（ｗ”）の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、これらの検証が全て成功した場合に認証成功を示す値１を出力し、検証に失敗があった場合に認証失敗を示す値０を出力する。
【０２０６】
ｄ＝２の場合、検証者アルゴリズムＶは、（ｆ''''，ｚ’ｘ，ｚ’ｙ）←σを計算する。そして、検証者アルゴリズムＶは、ｃ１＝Ｈ１（ｆ'''（ｚ’ｘ（ｔ），ｚ’ｙ（ｔ），ｔ），ｚ’ｘ，ｚ’ｙ））の等号が成り立つか否かを検証する。さらに、検証者アルゴリズムＶは、ｃ３＝Ｈ３（ｆ''''）の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、これらの検証が全て成功した場合に認証成功を示す値１を出力し、検証に失敗があった場合に認証失敗を示す値０を出力する。
【０２０７】
以上、本手法を実施する際に想定される具体的なアルゴリズム構成について説明した。
【０２０８】
＜３：第２実施形態＞
次に、本発明の第２実施形態について説明する。これまで３パスの公開鍵認証方式について説明してきた。本実施形態では、５パスの公開鍵認証方式（以下、本手法）について説明する。本手法は、検証者の検証パターンを２ｑ通りにすることにより、公開鍵認証方式の健全性を確保する方式である。
【０２０９】
なお、上記の第１実施形態に係る３パスの公開鍵認証方式は、対話プロトコル１回当たりの偽証確率が２／３であったが、本手法では、後述するように対話プロトコル１回当たりの偽証確率は１／２＋１／ｑとなる。但し、ｑは、利用する環の位数である。従って、環の位数が十分に大きい場合、図１８に示すように、本手法の方が１回当たりの偽証確率を低減することが可能になり、少ない対話プロトコルの実行回数で、偽証確率を十分に小さくすることができる。
【０２１０】
５パスの公開鍵認証方式に係る対話プロトコルは、３パスの公開鍵認証方式に係る対話プロトコルよりも効率が低いように思われるかもしれない。しかし、５パスの公開鍵認証方式においては、環の位数を十分に大きくとった場合、対話プロトコル１回当たりの偽証確率が１／２に近くなるため、同じセキュリティレベルを達成するために必要な対話プロトコルの実行回数が少なくて済む。
【０２１１】
例えば、偽証確率を１／２ｎ以下にしたい場合、３パスの公開鍵認証方式においては、ｎ／（ｌｏｇ３−１）＝１．７０１ｎ回以上、対話プロトコルを実行する必要がある。一方、５パスの公開鍵認証方式においては、ｎ／（１−ｌｏｇ（１＋１／ｑ））回以上、対話プロトコルを実行する必要がある。図１８に示すように、例えば、ｑ＝２４にすれば、同じセキュリティレベルを実現するのに必要な通信量は、３パスの公開鍵認証方式に比べ、５パスの公開鍵認証方式の方が少なくなる。
【０２１２】
［３−１：公開鍵認証方式のアルゴリズム］
以下、図１１を参照しながら、５パスの公開鍵認証方式（本手法）に係るアルゴリズム構成について説明する。図１１は、本手法に係るアルゴリズムの内容について説明するための説明図である。
【０２１３】
（鍵生成アルゴリズムＧｅｎ）
鍵生成アルゴリズムＧｅｎは、環Ｋ上で定義されるｎ変数の多次多項式ｆ０（ｘ１，…，ｘｎ）と、１変数の多次多項式ｕ１（ｔ），…，ｕｎ−１（ｔ）を生成する。次に、鍵生成アルゴリズムＧｅｎは、ｃ（ｔ）←ｆ０（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）を計算する。そして、鍵生成アルゴリズムＧｅｎは、ｆ（ｘ１，…，ｘｎ）＝ｆ０（ｘ１，…，ｘｎ）−ｃ（ｘｎ）を計算し、ｆを公開鍵ｐｋに設定する。また、鍵生成アルゴリズムＧｅｎは、（ｕ１，…，ｕｎ−１）を秘密鍵ｓｋに設定する。
【０２１４】
（証明者アルゴリズムＰ、検証者アルゴリズムＶ）
次に、図１２を参照しながら、対話プロトコルにおける証明者アルゴリズムＰと検証者アルゴリズムＶによる処理について説明する。この対話プロトコルは、「証明者がｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）を満たす（ｕ１，…，ｕｎ−１）を知っていること」を（ｕ１，…，ｕｎ−１）の情報を検証者に一切漏らさずに、検証者に証明するものである。なお、鍵生成アルゴリズムＧｅｎにより生成された公開鍵ｐｋは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムＧｅｎにより生成された秘密鍵ｓｋは、証明者により秘密に管理されているものとする。
【０２１５】
Ｓｔｅｐ．１：
まず、証明者アルゴリズムＰは、任意に数ｗを選択する。次いで、証明者アルゴリズムＰは、擬似乱数生成器Ｇに数ｗを適用して１変数多項式ｒ１（ｔ），…，ｒｎ−１（ｔ）と、ｎ変数多項式ｆ’（ｘ１，…，ｘｎ）を生成する。つまり、証明者アルゴリズムＰは、（ｒ１，…，ｒｎ−１，ｆ’）←Ｇ（ｗ）を計算する。次いで、証明者アルゴリズムＰは、（ｚ１（ｔ），…，ｚｎ−１（ｔ））←（ｕ１（ｔ）−ｒ１（ｔ），…，ｕｎ−１（ｔ）−ｒｎ−１（ｔ））を計算する。この計算は、秘密鍵（ｕ１，…，ｕｎ−１）を１変数多項式（ｒ１，…，ｒｎ−１）によりマスクする操作に相当する。
【０２１６】
Ｓｔｅｐ．１（続き）：
次いで、証明者アルゴリズムＰは、ｆ”（ｚ１（ｔ），…，ｚｎ−１（ｔ），ｔ）とｚ１，…，ｚｎ−１のハッシュ値ｃ１を生成する。つまり、証明者アルゴリズムＰは、ｃ１←Ｈ１（ｆ”（ｚ１（ｔ），…，ｚｎ−１（ｔ），ｔ），ｚ１，…，ｚｎ−１）を計算する。また、証明者アルゴリズムＰは、数ｗのハッシュ値ｃ２を生成する。つまり、証明者アルゴリズムＰは、ｃ２←Ｈ２（ｗ）を計算する。なお、上記のＨ１（…）、Ｈ２（…）は、ハッシュ関数である。また、ハッシュ値（ｃ１、ｃ２）はメッセージである。
【０２１７】
Ｓｔｅｐ．１で生成されたメッセージ（ｃ１、ｃ２）は、検証者に送られる。
【０２１８】
Ｓｔｅｐ．２：
検証者アルゴリズムＶは、ｑ通り存在する環Ｋの元から１つの乱数αを選択する。そして、検証者アルゴリズムＶは、選択した乱数αを証明者に送る。
【０２１９】
Ｓｔｅｐ．３：
証明者アルゴリズムＰは、ｆ”（ｘ１，…，ｘｎ）←αｆ（ｘ１＋ｒ１（ｘｎ），…，ｘｎ−１＋ｒｎ−１（ｘｎ），ｘｎ）＋ｆ’（ｘ１，…，ｘｎ）を計算する。この計算は、ｘ１，…，ｘｎについての多項式ｆ（ｘ１＋ｒ１（ｘｎ），…，ｘｎ−１＋ｒｎ−１（ｘｎ），ｘｎ）を多項式ｆ’（ｘ１，…，ｘｎ）によりマスクする操作に相当する。
【０２２０】
Ｓｔｅｐ．３で生成されたメッセージｆ”は、検証者に送られる。
【０２２１】
Ｓｔｅｐ．４：
検証者アルゴリズムＶは、２つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムＶは、選択した検証パターンを表す要求ｄ∈｛０，１｝を証明者に送る。
【０２２２】
Ｓｔｅｐ．５：
証明者アルゴリズムＰは、検証者から受けた要求ｄに応じて検証者に送り返す情報σを生成する。もしｄ＝０の場合、証明者アルゴリズムＰは、情報σ＝ｗを生成する。また、ｄ＝１の場合、証明者アルゴリズムＰは、情報σ＝（ｚ１，…，ｚｎ−１）を生成する。このようにして生成された情報σは、証明者アルゴリズムＰにより検証者に送られる。
【０２２３】
Ｓｔｅｐ．６：
検証者アルゴリズムＶは、証明者から受け取った情報σを利用して以下の検証処理を実行する。
【０２２４】
ｄ＝０の場合、検証者アルゴリズムＶは、（ｒ’１，…，ｒ’ｎ−１，ｆ'''）←Ｇ（σ）を計算する。そして、検証者アルゴリズムＶは、ｃ２＝Ｈ２（σ）の等号が成り立つか否かを検証する。また、検証者アルゴリズムＶは、ｆ”（ｘ１，…，ｘｎ）＝αｆ（ｘ１＋ｒ’１（ｘｎ），…，ｘｎ−１＋ｒ’ｎ−１（ｘｎ），ｘｎ）＋ｆ'''（ｘ１，…，ｘｎ）の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、これらの検証が全て成功した場合に認証成功を示す値１を出力し、検証に失敗があった場合に認証失敗を示す値０を出力する。
【０２２５】
ｄ＝１の場合、検証者アルゴリズムＶは、（ｚ’１，…，ｚ’ｎ−１）←σを計算する。そして、検証者アルゴリズムＶは、ｃ１＝Ｈ１（ｆ'''（ｚ’１（ｔ），…，ｚ’ｎ−１（ｔ），ｔ），ｚ’１，…，ｚ’ｎ−１））の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、この検証が成功した場合に認証成功を示す値１を出力し、検証に失敗があった場合に認証失敗を示す値０を出力する。
【０２２６】
（補足）
さて、上記Ｓｔｅｐ．１及びＳｔｅｐ．３において生成されたメッセージ（ｃ１，ｃ２）及びｆ”を検証者に送った際、秘密鍵ｓｋに関する情報、（ｒ１，…，ｒｎ−１）に関する情報、（ｚ１，…，ｚｎ−１）に関する情報が検証者に一切漏れていないことに注意されたい。また、上記Ｓｔｅｐ．５において生成された情報σを検証者に送った際、ｄ＝０のときにはｚ１，…，ｚｎ−１に関する情報が検証者に一切漏れておらず、ｄ＝１のときにはｒ１，…，ｒｎ−１に関する情報が検証者に一切漏れていないことに注意されたい。
【０２２７】
（本手法における健全性について）
本手法の健全性は、証明者アルゴリズムＰが１組の（ｃ１，ｃ２）、及び、検証者アルゴリズムＶが選択する２通りの（α１，α２）について、要求ｄ＝０，１に正しく回答した場合に、その回答内容から下記の式（１１）〜式（１３）を満たすｆ''''１、ｆ''''２、ｆ'''、ｒ’１，…，ｒ’ｎ−１、ｚ’１，…，ｚ’ｎ−１を計算できるということから保証されている。
【０２２８】
【数８】
0005593850.tif 000009
【０２２９】
このようなロジックが保証されることにより、代数曲面上の求セクション問題を解かない限りにおいて１／２＋１／ｑより高い確率で偽証することは不可能であることが保証される。つまり、検証者の要求ｄ＝０，１の全てに正しく回答するためには、偽証者が上記の式（１１）〜式（１３）を満たすｆ''''１、ｆ''''２、ｆ'''、ｒ’１，…，ｒ’ｎ−１、ｚ’１，…ｚ’ｎ−１を計算できる必要がある。言い換えると、偽証者はｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす（ｕ１，…，ｕｎ−１）を計算できる必要がある。従って、代数曲面上の求セクション問題を解かない限り、偽証者は、１／２＋１／ｑより高い確率で偽証を成功させることができないのである。なお、上記の対話プロトコルを十分に多くの回数実行することにより、偽証の成功確率を無視できるほど小さくすることができる。
【０２３０】
（変形例）
上記の証明者アルゴリズムＰは、メッセージｃ１として、ｆ”（ｚ１（ｔ），…，ｚｎ−１（ｔ），ｔ）とｚ１，…，ｚｎ−１のハッシュ値を用いていた。しかし、証明者アルゴリズムＰは、ｆ”（ｚ１（ｔ），…，ｚｎ−１（ｔ），ｔ）のハッシュ値と、ｚ１，…，ｚｎ−１のハッシュ値とを別々に計算し、それぞれをメッセージとして検証者に送るようにしてもよい。また、上記の証明者アルゴリズムＰは、数ｗに擬似乱数生成器Ｇを適用して１変数多項式ｒ１（ｔ），…，ｒｎ−１（ｔ）とｎ変数多項式ｆ’（ｘ１，…，ｘｎ）を生成している。しかし、証明者アルゴリズムＰは、最初からｗ＝（ｒ１（ｔ），…，ｒｎ−１（ｔ），ｆ’）を算出し、Ｇを恒等写像としてもよい。また、この場合には、数ｗをＧに適用する必要はない。
【０２３１】
以上、本手法に係る基本的なアルゴリズム構成について説明した。
【０２３２】
［３−２：拡張アルゴリズム］
次に、図１２を参照しながら、本手法を拡張した公開鍵認証方式（以下、拡張手法）のアルゴリズムについて説明する。図１２は、拡張手法に基づく対話プロトコルの流れを説明するための説明図である。この拡張手法は、３パス目に送信する多項式ｆ”を１つのハッシュ値ｃ３に変換して検証者に送る方式である。このように拡張することで、対話プロトコルの中で表現サイズの大きい多項式ｆ”を検証者に送る確率を半減することが可能になり、通信する平均的なデータサイズを削減することができる。以下、拡張方式における各アルゴリズムの内容について詳細に説明する。
【０２３３】
（鍵生成アルゴリズムＧｅｎ）
鍵生成アルゴリズムＧｅｎは、環Ｋ上で定義されるｎ変数の多次多項式ｆ０（ｘ１，…，ｘｎ）と、１変数の多次多項式ｕ１（ｔ），…，ｕｎ−１（ｔ）を生成する。次に、鍵生成アルゴリズムＧｅｎは、ｃ（ｔ）←ｆ０（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）を計算する。そして、鍵生成アルゴリズムＧｅｎは、ｆ（ｘ１，…，ｘｎ）＝ｆ０（ｘ１，…，ｘｎ）−ｃ（ｘｎ）を計算し、ｆを公開鍵ｐｋに設定する。また、鍵生成アルゴリズムＧｅｎは、（ｕ１，…，ｕｎ−１）を秘密鍵ｓｋに設定する。
【０２３４】
（証明者アルゴリズムＰ、検証者アルゴリズムＶ）
次に、図１２を参照しながら、対話プロトコルにおける証明者アルゴリズムＰと検証者アルゴリズムＶによる処理について説明する。この対話プロトコルは、「証明者がｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）を満たす（ｕ１，…，ｕｎ−１）を知っていること」を（ｕ１，…，ｕｎ−１）の情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムＧｅｎにより生成された公開鍵ｐｋは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムＧｅｎにより生成された秘密鍵ｓｋは、証明者により秘密に管理されているものとする。
【０２３５】
Ｓｔｅｐ．１：
まず、証明者アルゴリズムＰは、任意に数ｗを選択する。次いで、証明者アルゴリズムＰは、擬似乱数生成器Ｇに数ｗを適用して１変数多項式ｒ１（ｔ），…，ｒｎ−１（ｔ）と、ｎ変数多項式ｆ’（ｘ１，…，ｘｎ）を生成する。つまり、証明者アルゴリズムＰは、（ｒ１，…，ｒｎ−１，ｆ’）←Ｇ（ｗ）を計算する。次いで、証明者アルゴリズムＰは、（ｚ１（ｔ），…，ｚｎ−１（ｔ））←（ｕ１（ｔ）−ｒ１（ｔ），…，ｕｎ−１（ｔ）−ｒｎ−１（ｔ））を計算する。この計算は、秘密鍵（ｕ１，…，ｕｎ−１）を１変数多項式（ｒ１，…，ｒｎ−１）によりマスクする操作に相当する。
【０２３６】
Ｓｔｅｐ．１（続き）：
次いで、証明者アルゴリズムＰは、ｆ”（ｚ１（ｔ），…，ｚｎ−１（ｔ），ｔ）とｚ１，…，ｚｎ−１のハッシュ値ｃ１を生成する。つまり、証明者アルゴリズムＰは、ｃ１←Ｈ１（ｆ”（ｚ１（ｔ），…，ｚｎ−１（ｔ），ｔ），ｚ１，…，ｚｎ−１）を計算する。また、証明者アルゴリズムＰは、数ｗのハッシュ値ｃ２を生成する。つまり、証明者アルゴリズムＰは、ｃ２←Ｈ２（ｗ）を計算する。なお、上記のＨ１（…）、Ｈ２（…）は、ハッシュ関数である。また、ハッシュ値（ｃ１、ｃ２）はメッセージである。
【０２３７】
Ｓｔｅｐ．１で生成されたメッセージ（ｃ１、ｃ２）は、検証者に送られる。
【０２３８】
Ｓｔｅｐ．２：
検証者アルゴリズムＶは、ｑ通り存在する環Ｋの元から１つの乱数αを選択する。そして、検証者アルゴリズムＶは、選択した乱数αを証明者に送る。
【０２３９】
Ｓｔｅｐ．３：
証明者アルゴリズムＰは、ｆ”（ｘ１，…，ｘｎ）←αｆ（ｘ１＋ｒ１（ｘｎ），…，ｘｎ−１＋ｒｎ−１（ｘｎ），ｘｎ）＋ｆ’（ｘ１，…，ｘｎ）を計算する。この計算は、ｘ１，…，ｘｎについての多項式ｆ（ｘ１＋ｒ１（ｘｎ），…，ｘｎ−１＋ｒｎ−１（ｘｎ），ｘｎ）を多項式ｆ’（ｘ１，…，ｘｎ）によりマスクする操作に相当する。さらに、証明者アルゴリズムＰは、多項式ｆ”のハッシュ値ｃ３を生成する。つまり、証明者アルゴリズムＰは、ｃ３←Ｈ３（ｆ”）を計算する。なお、上記のＨ３（…）は、ハッシュ関数である。また、ハッシュ値ｃ３はメッセージである。
【０２４０】
Ｓｔｅｐ．３で生成されたメッセージｃ３は、検証者に送られる。
【０２４１】
Ｓｔｅｐ．４：
検証者アルゴリズムＶは、２つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムＶは、選択した検証パターンを表す要求ｄ∈｛０，１｝を証明者に送る。
【０２４２】
Ｓｔｅｐ．５：
証明者アルゴリズムＰは、検証者から受けた要求ｄに応じて検証者に送り返す情報σを生成する。もしｄ＝０の場合、証明者アルゴリズムＰは、情報σ＝ｗを生成する。また、ｄ＝１の場合、証明者アルゴリズムＰは、情報σ＝（ｚ１，…，ｚｎ−１，ｆ”）を生成する。このようにして生成された情報σは、証明者アルゴリズムＰにより検証者に送られる。
【０２４３】
Ｓｔｅｐ．６：
検証者アルゴリズムＶは、証明者から受け取った情報σを利用して以下の検証処理を実行する。
【０２４４】
ｄ＝０の場合、検証者アルゴリズムＶは、（ｒ’１，…，ｒ’ｎ−１，ｆ'''）←Ｇ（σ）を計算する。そして、検証者アルゴリズムＶは、ｃ２＝Ｈ２（σ）の等号が成り立つか否かを検証する。また、検証者アルゴリズムＶは、ｃ３＝Ｈ３（αｆ（ｘ１＋ｒ’１（ｘｎ），…，ｘｎ−１＋ｒ’ｎ−１（ｘｎ），ｘｎ）＋ｆ'''（ｘ１，…，ｘｎ））の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、これらの検証が全て成功した場合に認証成功を示す値１を出力し、検証に失敗があった場合に認証失敗を示す値０を出力する。
【０２４５】
ｄ＝１の場合、検証者アルゴリズムＶは、（ｚ’１，…，ｚ’ｎ−１，ｆ'''）←σを計算する。そして、検証者アルゴリズムＶは、ｃ１＝Ｈ１（ｆ'''（ｚ’１（ｔ），…，ｚ’ｎ−１（ｔ），ｔ），ｚ’１，…，ｚ’ｎ−１））の等号が成り立つか否かを検証する。また、検証者アルゴリズムＶは、ｃ２＝Ｈ２（ｆ'''）の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、これらの検証が全て成功した場合に認証成功を示す値１を出力し、検証に失敗があった場合に認証失敗を示す値０を出力する。
【０２４６】
以上、拡張方式の対話プロトコルにおける各アルゴリズムの処理について説明した。このように拡張することで、対話プロトコルの中で表現サイズの大きい多項式ｆ”を検証者に送る確率を半減することが可能になり、通信する平均的なデータサイズを削減することができる。
【０２４７】
［３−３：並列化アルゴリズム］
さて、先に述べた通り、本手法又は拡張手法に係る対話プロトコルを適用すれば、偽証が成功する確率を（１／２＋１／ｑ）以下に抑制することができる。従って、この対話プロトコルを２回実行すれば、偽証が成功する確率を（１／２＋１／ｑ）２以下に抑制することができる。同様に、この対話プロトコルをＮ回実行すると、偽証が成功する確率は（１／２＋１／ｑ）Ｎとなり、Ｎを十分に大きい数（例えば、Ｎ＝８０）にすれば、偽証が成功する確率は無視できる程度に小さくなる。例えば、本手法に係る対話プロトコルを並列的にＮ回実行するアルゴリズムは図１３のようになる。以下、図１３を参照しながら、並列的に対話プロトコルをＮ回実行する各アルゴリズムの内容について説明する。
【０２４８】
（鍵生成アルゴリズムＧｅｎ）
鍵生成アルゴリズムＧｅｎは、環Ｋ上で定義されるｎ変数の多次多項式ｆ０（ｘ１，…，ｘｎ）と、１変数の多次多項式ｕ１（ｔ），…，ｕｎ−１（ｔ）を生成する。次に、鍵生成アルゴリズムＧｅｎは、ｃ（ｔ）←ｆ０（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）を計算する。そして、鍵生成アルゴリズムＧｅｎは、ｆ（ｘ１，…，ｘｎ）＝ｆ０（ｘ１，…，ｘｎ）−ｃ（ｘｎ）を計算し、ｆを公開鍵ｐｋに設定する。また、鍵生成アルゴリズムＧｅｎは、（ｕ１，…，ｕｎ−１）を秘密鍵ｓｋに設定する。ここで、ｆ０（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たすことに注意されたい。
【０２４９】
（証明者アルゴリズムＰ、検証者アルゴリズムＶ）
次に、図１３を参照しながら、対話プロトコルにおける証明者アルゴリズムＰと検証者アルゴリズムＶによる処理について説明する。この対話プロトコルは、「証明者がｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）を満たす（ｕ１，…，ｕｎ−１）を知っていること」を（ｕ１，…，ｕｎ−１）の情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムＧｅｎにより生成された公開鍵ｐｋは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムＧｅｎにより生成された秘密鍵ｓｋは、証明者により秘密に管理されているものとする。
【０２５０】
Ｓｔｅｐ．１：
まず、証明者アルゴリズムＰは、ｉ＝１〜Ｎについて、以下の処理（１）〜処理（５）を実行する。（処理１）証明者アルゴリズムＰは、任意に数ｗｉを選択する。（処理２）証明者アルゴリズムＰは、擬似乱数生成器Ｇに数ｗｉを適用して１変数多項式ｒ１，ｉ（ｔ），…，ｒｎ−１，ｉ（ｔ）と多項式ｆ’ｉ（ｘ１，…，ｘｎ）を生成する。つまり、証明者アルゴリズムＰは、（ｒ１，ｉ，…，ｒｎ−１，ｉ，ｆ’ｉ）←Ｇ（ｗｉ）を計算する。（処理３）証明者アルゴリズムＰは、（ｚ１，ｉ（ｔ），…，ｚｎ−１，ｉ（ｔ））←（ｕ１，ｉ（ｔ）−ｒ１，ｉ（ｔ），…，ｕｎ−１，ｉ（ｔ）−ｒｎ−１，ｉ（ｔ））を計算する。この計算は、秘密鍵（ｕ１，ｉ，…，ｕｎ−１，ｉ）を１変数多項式（ｒ１，ｉ，…，ｒｎ−１，ｉ）によりマスクする操作に相当する。
【０２５１】
Ｓｔｅｐ．１（続き）：
（処理４）証明者アルゴリズムＰは、ｆ”ｉ（ｚ１，ｉ（ｔ），…，ｚｎ−１，ｉ（ｔ），ｔ）とｚ１，ｉ，…，ｚｎ−１，ｉのハッシュ値ｃ１，ｉを生成する。つまり、証明者アルゴリズムＰは、ｃ１，ｉ←Ｈ１（ｆ”ｉ（ｚ１，ｉ（ｔ），…，ｚｎ−１，ｉ（ｔ），ｔ），ｚ１，ｉ，…，ｚｎ−１，ｉ）を計算する。（処理５）証明者アルゴリズムＰは、数ｗ’ｉのハッシュ値ｃ２，ｉを生成する。つまり、証明者アルゴリズムＰは、ｃ２，ｉ←Ｈ２（ｗ’ｉ）を計算する。
【０２５２】
ｉ＝１〜Ｎについて、上記の（処理１）〜（処理５）が実行された後、Ｓｔｅｐ．１で生成されたメッセージ（ｃ１，ｉ、ｃ２，ｉ）（ｉ＝１〜Ｎ）は、検証者に送られる。
【０２５３】
Ｓｔｅｐ．２：
検証者アルゴリズムＶは、ｑ通り存在する環Ｋの元からＮ個の乱数α１，…，αＮを選択する。そして、検証者アルゴリズムＶは、選択した乱数α１，…，αＮを証明者に送る。
【０２５４】
Ｓｔｅｐ．３：
検証者アルゴリズムＶは、ｉ＝１〜Ｎについて、ｆ”ｉ（ｘ１，…，ｘｎ）←αｉｆ（ｘ１＋ｒ１，ｉ（ｘｎ），…，ｘｎ−１＋ｒｎ−１，ｉ（ｘｎ），ｘｎ）＋ｆ’ｉ（ｘ１，…，ｘｎ）を計算する。この計算は、ｘ１，…，ｘｎについての多項式ｆ（ｘ１＋ｒ１，ｉ（ｘｎ），…，ｘｎ−１＋ｒｎ−１，ｉ（ｘｎ），ｘｎ）を多項式ｆ’ｉ（ｘ１，…，ｘｎ）によりマスクする操作に相当する。そして、検証者アルゴリズムＶは、多項式ｆ”１，…，ｆ”Ｎを検証者に送る。
【０２５５】
Ｓｔｅｐ．４：
検証者アルゴリズムＶは、ｉ＝１〜Ｎのそれぞれについて、２つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムＶは、選択した検証パターンを表す要求ｄｉ∈｛０，１｝（ｉ＝１〜Ｎ）を証明者に送る。
【０２５６】
Ｓｔｅｐ．５：
証明者アルゴリズムＰは、検証者から受けた要求ｄｉに応じて検証者に送り返す情報σｉを生成する。ここで、証明者アルゴリズムＰは、ｉ＝１〜Ｎについて、以下の（処理１）又は（処理２）を実行する。（処理１）ｄｉ＝０の場合、証明者アルゴリズムＰは、情報σｉ＝ｗｉを生成する。（処理２）ｄｉ＝１の場合、証明者アルゴリズムＰは、情報σｉ＝（ｗ’ｉ，ｚ１，ｉ，…，ｚｎ−１，ｉ）を生成する。上記（処理１）又は（処理２）の判定及び処理が実行された後、情報σｉ（ｉ＝１〜Ｎ）は、証明者アルゴリズムＰにより検証者に送られる。
【０２５７】
Ｓｔｅｐ．６：
検証者アルゴリズムＶは、証明者から受け取った情報σｉ（ｉ＝１〜Ｎ）を利用して以下の検証処理を実行する。なお、以下の処理は、ｉ＝１〜Ｎについて実行される。
【０２５８】
ｄｉ＝０の場合、検証者アルゴリズムＶは、（ｒ’１，ｉ，…，ｒ’ｎ−１，ｉ，ｆ'''ｉ）←Ｇ１（σｉ）を計算する。そして、検証者アルゴリズムＶは、ｃ２，ｉ＝Ｈ２（σｉ）の等号が成り立つか否かを検証する。また、検証者アルゴリズムＶは、ｆ”ｉ（ｘ１，…，ｘｎ）＝ｆ（ｘ１＋ｒ’１，ｉ（ｘｎ），…，ｘｎ−１，ｉ＋ｒ’ｎ−１，ｉ（ｘｎ），ｘｎ）＋ｆ'''ｉ（ｘ１，…，ｘｎ）の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、これらの検証が全て成功した場合に認証成功を示す値１を出力し、検証に失敗があった場合に認証失敗を示す値０を出力する。
【０２５９】
ｄｉ＝１の場合、検証者アルゴリズムＶは、（ｚ’１，ｉ，…，ｚ’ｎ−１，ｉ）←σｉを計算する。そして、検証者アルゴリズムＶは、ｃ１，ｉ＝Ｈ１（ｆ'''ｉ（ｚ’１，ｉ（ｔ），…，ｚ’ｎ−１，ｉ（ｔ），ｔ），ｚ’１，ｉ，…，ｚ’ｎ−１，ｉ））の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、この検証が成功した場合に認証成功を示す値１を出力し、検証に失敗があった場合に認証失敗を示す値０を出力する。
【０２６０】
以上、本手法の対話プロトコルを並列的に実行する方法について説明した。上記のように、本手法の対話プロトコルを繰り返し実行することにより、偽証が成功する確率を無視できる程度まで低減させることが可能になる。なお、拡張方式についても同様にして並列化することが可能である。拡張方式について並列化した対話プロトコルのアルゴリズム構成を図１４に示した。
【０２６１】
（拡張方式に係る並列化アルゴリズムについて）
以下、図１４を参照しながら、拡張方式に係る並列化アルゴリズムの内容について説明する。なお、鍵生成アルゴリズムＧｅｎの構成については本手法に係る並列化アルゴリズムと同じであるため、詳細な説明を省略する。
【０２６２】
Ｓｔｅｐ．１：
まず、証明者アルゴリズムＰは、ｉ＝１〜Ｎについて、以下の処理（１）〜処理（５）を実行する。（処理１）証明者アルゴリズムＰは、任意に数ｗｉを選択する。（処理２）証明者アルゴリズムＰは、擬似乱数生成器Ｇに数ｗｉを適用して１変数多項式ｒ１，ｉ（ｔ），…，ｒｎ−１，ｉ（ｔ）と多項式ｆ’ｉ（ｘ１，…，ｘｎ）を生成する。つまり、証明者アルゴリズムＰは、（ｒ１，ｉ，…，ｒｎ−１，ｉ，ｆ’ｉ）←Ｇ（ｗｉ）を計算する。（処理３）証明者アルゴリズムＰは、（ｚ１，ｉ（ｔ），…，ｚｎ−１，ｉ（ｔ））←（ｕ１，ｉ（ｔ）−ｒ１，ｉ（ｔ），…，ｕｎ−１，ｉ（ｔ）−ｒｎ−１，ｉ（ｔ））を計算する。この計算は、秘密鍵（ｕ１，ｉ，…，ｕｎ−１，ｉ）を１変数多項式（ｒ１，ｉ，…，ｒｎ−１，ｉ）によりマスクする操作に相当する。
【０２６３】
Ｓｔｅｐ．１（続き）：
（処理４）証明者アルゴリズムＰは、ｆ”ｉ（ｚ１，ｉ（ｔ），…，ｚｎ−１，ｉ（ｔ），ｔ）とｚ１，ｉ，…，ｚｎ−１，ｉのハッシュ値ｃ１，ｉを生成する。つまり、証明者アルゴリズムＰは、ｃ１，ｉ←Ｈ１（ｆ”ｉ（ｚ１，ｉ（ｔ），…，ｚｎ−１，ｉ（ｔ），ｔ），ｚ１，ｉ，…，ｚｎ−１，ｉ）を計算する。（処理５）証明者アルゴリズムＰは、数ｗ’ｉのハッシュ値ｃ２，ｉを生成する。つまり、証明者アルゴリズムＰは、ｃ２，ｉ←Ｈ２（ｗ’ｉ）を計算する。
【０２６４】
ｉ＝１〜Ｎについて、上記の（処理１）〜（処理５）が実行された後、Ｓｔｅｐ．１で生成されたメッセージ（ｃ１，ｉ、ｃ２，ｉ）（ｉ＝１〜Ｎ）は、検証者に送られる。
【０２６５】
Ｓｔｅｐ．２：
検証者アルゴリズムＶは、ｑ通り存在する環Ｋの元からＮ個の乱数α１，…，αＮを選択する。そして、検証者アルゴリズムＶは、選択した乱数α１，…，αＮを証明者に送る。
【０２６６】
Ｓｔｅｐ．３：
検証者アルゴリズムＶは、ｉ−１〜Ｎについて、ｆ”ｉ（ｘ１，…，ｘｎ）←αｉｆ（ｘ１＋ｒ１，ｉ（ｘｎ），…，ｘｎ−１＋ｒｎ−１，ｉ（ｘｎ），ｘｎ）＋ｆ’ｉ（ｘ１，…，ｘｎ）を計算する。この計算は、ｘ１，…，ｘｎについての多項式ｆ（ｘ１＋ｒ１，ｉ（ｘｎ），…，ｘｎ−１＋ｒｎ−１，ｉ（ｘｎ），ｘｎ）を多項式ｆ’ｉ（ｘ１，…，ｘｎ）によりマスクする操作に相当する。次いで、検証者アルゴリズムＶは、多項式ｆ”１，…，ｆ”Ｎのハッシュ値ｃ３を生成する。つまり、証明者アルゴリズムＰは、ｃ３←Ｈ３（ｆ”１，…，ｆ”Ｎ）を計算する。なお、上記のＨ３（…）は、ハッシュ関数である。また、ハッシュ値ｃ３はメッセージである。
【０２６７】
Ｓｔｅｐ．３で生成されたメッセージｃ３は、検証者に送られる。
【０２６８】
Ｓｔｅｐ．４：
検証者アルゴリズムＶは、ｉ＝１〜Ｎのそれぞれについて、２つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムＶは、選択した検証パターンを表す要求ｄｉ∈｛０，１｝（ｉ＝１〜Ｎ）を証明者に送る。
【０２６９】
Ｓｔｅｐ．５：
証明者アルゴリズムＰは、検証者から受けた要求ｄｉに応じて検証者に送り返す情報σｉを生成する。ここで、証明者アルゴリズムＰは、ｉ＝１〜Ｎについて、以下の（処理１）又は（処理２）を実行する。（処理１）ｄｉ＝０の場合、証明者アルゴリズムＰは、情報σｉ＝ｗｉを生成する。（処理２）ｄｉ＝１の場合、証明者アルゴリズムＰは、情報σｉ＝（ｗ’ｉ，ｚ１，ｉ，…，ｚｎ−１，ｉ，ｆ”ｉ）を生成する。上記（処理１）又は（処理２）の判定及び処理が実行された後、情報σｉ（ｉ＝１〜Ｎ）は、証明者アルゴリズムＰにより検証者に送られる。
【０２７０】
Ｓｔｅｐ．６：
検証者アルゴリズムＶは、証明者から受け取った情報σｉ（ｉ＝１〜Ｎ）を利用して以下の検証処理を実行する。なお、以下の処理は、ｉ＝１〜Ｎについて実行される。
【０２７１】
ｄｉ＝０の場合、検証者アルゴリズムＶは、（ｒ’１，ｉ，…，ｒ’ｎ−１，ｉ，ｆ'''ｉ）←Ｇ１（σｉ）を計算する。さらに、検証者アルゴリズムＶは、ｆ''''ｉ←αｉｆ（ｘ１＋ｒ’１，ｉ（ｘｎ），…，ｘｎ−１＋ｒ’ｎ−１，ｉ（ｘｎ），ｘｎ）＋ｆ'''ｉ（ｘ１，…，ｘｎ）を計算する。そして、検証者アルゴリズムＶは、ｃ２，ｉ＝Ｈ２（σｉ）の等号が成り立つか否かを検証する。また、検証者アルゴリズムＶは、ｃ３＝Ｈ３（ｆ''''１，…，ｆ''''Ｎ）の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、これらの検証が全て成功した場合に認証成功を示す値１を出力し、検証に失敗があった場合に認証失敗を示す値０を出力する。
【０２７２】
ｄｉ＝１の場合、検証者アルゴリズムＶは、（ｚ’１，ｉ，…，ｚ’ｎ−１，ｉ，ｆ''''ｉ）←σｉを計算する。そして、検証者アルゴリズムＶは、ｃ１，ｉ＝Ｈ１（ｆ'''ｉ（ｚ’１，ｉ（ｔ），…，ｚ’ｎ−１，ｉ（ｔ），ｔ），ｚ’１，ｉ，…，ｚ’ｎ−１，ｉ））の等号が成り立つか否かを検証する。さらに、検証者アルゴリズムＶは、ｃ３＝Ｈ３（ｆ''''１，…，ｆ''''Ｎ）の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、これらの検証が全て成功した場合に認証成功を示す値１を出力し、検証に失敗があった場合に認証失敗を示す値０を出力する。
【０２７３】
以上、拡張方式に係る並列化アルゴリズムの内容について説明した。
【０２７４】
［３−４：非対話型アルゴリズム］
これまで５パスの公開鍵認証方式について説明してきた。しかし、本手法においては、検証者から証明者に送られる情報が実際には単なる乱数だけであるため、１パスの公開鍵認証方式（以下、非対話型方式）に変形することができる。なお、非対話型方式に係る各アルゴリズムの内容を図１５に示した。以下、図１５を参照しながら、非対話型方式に係る各アルゴリズムの内容について説明する。
【０２７５】
（鍵生成アルゴリズムＧｅｎ）
鍵生成アルゴリズムＧｅｎは、環Ｋ上で定義されるｎ変数の多次多項式ｆ０（ｘ１，…，ｘｎ）と、１変数の多次多項式ｕ１（ｔ），…，ｕｎ−１（ｔ）を生成する。次に、鍵生成アルゴリズムＧｅｎは、ｃ（ｔ）←ｆ０（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）を計算する。そして、鍵生成アルゴリズムＧｅｎは、ｆ（ｘ１，…，ｘｎ）＝ｆ０（ｘ１，…，ｘｎ）−ｃ（ｘｎ）を計算し、ｆを公開鍵ｐｋに設定する。また、鍵生成アルゴリズムＧｅｎは、（ｕ１，…，ｕｎ−１）を秘密鍵ｓｋに設定する。ここで、ｆ０（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たすことに注意されたい。
【０２７６】
（証明者アルゴリズムＰ、検証者アルゴリズムＶ）
次に、図１５を参照しながら、対話プロトコルにおける証明者アルゴリズムＰと検証者アルゴリズムＶによる処理について説明する。この対話プロトコルは、「証明者がｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）を満たす（ｕ１，…，ｕｎ−１）を知っていること」を（ｕ１，…，ｕｎ−１）の情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムＧｅｎにより生成された公開鍵ｐｋは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムＧｅｎにより生成された秘密鍵ｓｋは、証明者により秘密に管理されているものとする。
【０２７７】
Ｓｔｅｐ．１：
まず、証明者アルゴリズムＰは、ｉ＝１〜Ｎについて、以下の処理（１）〜処理（５）を実行する。（処理１）証明者アルゴリズムＰは、任意に数ｗｉを選択する。（処理２）証明者アルゴリズムＰは、擬似乱数生成器Ｇに数ｗｉを適用して１変数多項式ｒ１，ｉ（ｔ），…，ｒｎ−１，ｉ（ｔ）と多項式ｆ’ｉ（ｘ１，…，ｘｎ）を生成する。つまり、証明者アルゴリズムＰは、（ｒ１，ｉ，…，ｒｎ−１，ｉ，ｆ’ｉ）←Ｇ（ｗｉ）を計算する。（処理３）証明者アルゴリズムＰは、（ｚ１，ｉ（ｔ），…，ｚｎ−１，ｉ（ｔ））←（ｕ１，ｉ（ｔ）−ｒ１，ｉ（ｔ），…，ｕｎ−１，ｉ（ｔ）−ｒｎ−１，ｉ（ｔ））を計算する。この計算は、秘密鍵（ｕ１，ｉ，…，ｕｎ−１，ｉ）を１変数多項式（ｒ１，ｉ，…，ｒｎ−１，ｉ）によりマスクする操作に相当する。
【０２７８】
Ｓｔｅｐ．１（続き）：
（処理４）証明者アルゴリズムＰは、ｆ”ｉ（ｚ１，ｉ（ｔ），…，ｚｎ−１，ｉ（ｔ），ｔ）とｚ１，ｉ，…，ｚｎ−１，ｉのハッシュ値ｃ１，ｉを生成する。つまり、証明者アルゴリズムＰは、ｃ１，ｉ←Ｈ１（ｆ”ｉ（ｚ１，ｉ（ｔ），…，ｚｎ−１，ｉ（ｔ），ｔ），ｚ１，ｉ，…，ｚｎ−１，ｉ）を計算する。（処理５）証明者アルゴリズムＰは、数ｗ’ｉのハッシュ値ｃ２，ｉを生成する。つまり、証明者アルゴリズムＰは、ｃ２，ｉ←Ｈ２（ｗ’ｉ）を計算する。
【０２７９】
Ｓｔｅｐ．１（続き）：
次に、検証者アルゴリズムＶは、乱数ＲＡ，ＲＢを選択する。そして、検証者アルゴリズムＶは、乱数ＲＡと上記の（処理４）及び（処理５）で計算されたハッシュ値ｃ１，ｉ，ｃ２，ｉをハッシュ関数ＨＡに適用してハッシュ値α１，…，αＮを生成する。つまり、検証者アルゴリズムＶは、（α１，…，αＮ）←ＨＡ（ＲＡ，ｃ１，１，…，ｃ２，Ｎ）を計算する。
【０２８０】
Ｓｔｅｐ．１（続き）：
次に、検証者アルゴリズムＶは、ｉ＝１〜Ｎについて、以下の（処理１）及び（処理２）を実行する。（処理１）証明者アルゴリズムＰは、ｆ”ｉ（ｘ１，…，ｘｎ）←αｉｆ（ｘ１＋ｒ１，ｉ（ｘｎ），…，ｘｎ−１＋ｒｎ−１，ｉ（ｘｎ），ｘｎ）＋ｆ’ｉ（ｘ１，…，ｘｎ）を計算する。この計算は、ｘ１，…，ｘｎについての多項式ｆ（ｘ１＋ｒ１，ｉ（ｘｎ），…，ｘｎ−１＋ｒｎ−１，ｉ（ｘｎ），ｘｎ）を多項式ｆ’ｉ（ｘ１，…，ｘｎ）によりマスクする操作に相当する。（処理２）証明者アルゴリズムＰは、ｉ＝１〜Ｎについて、乱数ＲＡ，ＲＢ、ハッシュ値（ｃ１，ｉ、ｃ２，ｉ）、αｉ，ｆ”ｉをハッシュ関数ＨＢに適用してｄ＝（ｄ１，…，ｄＮ）を生成する。つまり、証明者アルゴリズムＰは、（ｄ１，…，ｄＮ）←ＨＢ（ＲＡ，ＲＢ，ｃ１，１，…，ｃ２，Ｎ，α１，…，αＮ，ｆ”１，…，ｆ”Ｎ）を計算する。
【０２８１】
Ｓｔｅｐ．１（続き）：
次に、検証者アルゴリズムＶは、
次に、証明者アルゴリズムＰは、生成したｄｉに応じて検証者に送り返す情報σｉを生成する。ここで、証明者アルゴリズムＰは、ｉ＝１〜Ｎについて、以下の（処理１）又は（処理２）を実行する。（処理１）ｄｉ＝０の場合、証明者アルゴリズムＰは、情報σｉ＝ｗｉを生成する。（処理２）ｄｉ＝１の場合、証明者アルゴリズムＰは、情報σｉ＝（ｚ１，ｉ，…，ｚｎ−１，ｉ）を生成する。上記（処理１）又は（処理２）の判定及び処理が実行された後、ＲＡ、ＲＢ、αｉ、ｃ１，ｉ、ｃ２，ｉ、σｉ（ｉ＝１〜Ｎ）は、証明者アルゴリズムＰにより検証者に送られる。
【０２８２】
Ｓｔｅｐ．２：
検証者アルゴリズムＶは、まず、証明者から受け取ったＲＡ、ｃ１，ｉ、ｃ２，ｉをハッシュ関数ＨＡに適用してαｉを生成する。つまり、検証者アルゴリズムＶは、（α１，…，αＮ）←ＨＡ（ＲＡ，ｃ１，１，…，ｃ２，Ｎ）を計算する。次いで、検証者アルゴリズムＶは、ｄ＝（ｄ１，…，ｄＮ）←ＨＢ（ＲＡ，ＲＢ，ｃ１，１，…，ｃ２，Ｎ，α１，…，αＮ，ｆ”１，…，ｆ”Ｎ）を計算する。次いで、検証者アルゴリズムＶは、情報σｉ（ｉ＝１〜Ｎ）を利用して以下の検証処理を実行する。なお、以下の処理は、ｉ＝１〜Ｎについて実行される。
【０２８３】
ｄｉ＝０の場合、検証者アルゴリズムＶは、（ｒ’１，ｉ，…，ｒ’ｎ−１，ｉ，ｆ'''ｉ）←Ｇ１（σｉ）を計算する。そして、検証者アルゴリズムＶは、ｃ２，ｉ＝Ｈ２（σｉ）の等号が成り立つか否かを検証する。また、検証者アルゴリズムＶは、ｆ”ｉ（ｘ１，…，ｘｎ＝αｉｆ（ｘ１＋ｒ’１，ｉ（ｘｎ），…，ｘｎ−１，ｉ＋ｒ’ｎ−１，ｉ（ｘｎ），ｘｎ）＋ｆ'''ｉ（ｘ１，…，ｘｎ）の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、これらの検証が全て成功した場合に認証成功を示す値１を出力し、検証に失敗があった場合に認証失敗を示す値０を出力する。
【０２８４】
ｄｉ＝１の場合、検証者アルゴリズムＶは、（ｚ’１，ｉ，…，ｚ’ｎ−１，ｉ，ｆ'''ｉ）←σｉを計算する。そして、検証者アルゴリズムＶは、ｃ１，ｉ＝Ｈ１（ｆ'''ｉ（ｚ’１，ｉ（ｔ），…，ｚ’ｎ−１，ｉ（ｔ），ｔ），ｚ’１，ｉ，…，ｚ’ｎ−１，ｉ））の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、この検証が成功した場合に認証成功を示す値１を出力し、検証に失敗があった場合に認証失敗を示す値０を出力する。
【０２８５】
以上、非対話型方式に係る各アルゴリズムの内容について説明した。なお、理想的なハッシュ関数ＨＡ、ＨＢを仮定すれば、ハッシュ値αｉ，ｄｉがランダムに振る舞うため、証明者に都合の良いハッシュ値αｉ，ｄｉが出ることはない。そのため、上記のような変形を行っても、十分な安全性が確保される。なお、このような変形は、拡張方式などに対しても同様に適用することが可能である。
【０２８６】
［３−５：電子署名方式への変形］
ここで、本手法を電子署名方式へと変形する方法について説明する。なお、ここでは簡単のために、上記の非対話型方式を電子署名方式に変形する方法について述べる。上記の非対話型方式における証明者と検証者を電子署名方式における署名者と検証者に対応させると、証明者のみが検証者を納得させられるという点において、電子署名方式のモデルと近似していることが分かるであろう。こうした考えをもとに、非対話型方式に基づく電子署名方式のアルゴリズム構成について詳細に説明する。
【０２８７】
（鍵生成アルゴリズムＧｅｎ）
鍵生成アルゴリズムＧｅｎは、環Ｋ上で定義されるｎ変数の多次多項式ｆ０（ｘ１，…，ｘｎ）と、１変数の多次多項式ｕ１（ｔ），…，ｕｎ−１（ｔ）を生成する。次に、鍵生成アルゴリズムＧｅｎは、ｃ（ｔ）←ｆ０（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）を計算する。そして、鍵生成アルゴリズムＧｅｎは、ｆ（ｘ１，…，ｘｎ）＝ｆ０（ｘ１，…，ｘｎ）−ｃ（ｘｎ）を計算し、ｆを検証鍵ｐｋに設定する。また、鍵生成アルゴリズムＧｅｎは、（ｕ１，…，ｕｎ−１）を署名鍵ｓｋに設定する。ここで、ｆ０（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たすことに注意されたい。
【０２８８】
（署名生成アルゴリズムＳｉｇ）
署名生成アルゴリズムＳｉｇは、ｉ＝１〜Ｎについて、以下の（処理１）〜（処理１１）を実行する。なお、署名生成アルゴリズムＳｉｇには、署名鍵ｓｋ＝（ｕ１，…，ｕｎ−１）と文書Ｍが入力されているものとする。
【０２８９】
（処理１）署名生成アルゴリズムＳｉｇは、任意に数ｗｉを選択する。（処理２）署名生成アルゴリズムＳｉｇは、擬似乱数生成器Ｇに数ｗｉを適用して１変数多項式ｒ１，ｉ（ｔ），…，ｒｎ−１，ｉ（ｔ）とｎ変数多項式ｆ’ｉ（ｘ１，…，ｘｎ）を生成する。つまり、署名生成アルゴリズムＳｉｇは、（ｒ１，ｉ，…，ｒｎ−１，ｉ，ｆ’ｉ）←Ｇ（ｗｉ）を計算する。（処理２）署名生成アルゴリズムＳｉｇは、（ｚ１，ｉ（ｔ），…，ｚｎ−１，ｉ（ｔ））←（ｕ１，ｉ（ｔ）−ｒ１，ｉ（ｔ），…，ｕｎ−１，ｉ（ｔ）−ｒｎ−１，ｉ（ｔ））を計算する。この計算は、秘密鍵（ｕ１，ｉ，…，ｕｎ−１，ｉ）を１変数多項式（ｒ１，ｉ，…，ｒｎ−１，ｉ）によりマスクする操作に相当する。
【０２９０】
（処理３）署名生成アルゴリズムＳｉｇは、ｆ”ｉ（ｚ１，ｉ（ｔ），…，ｚｎ−１，ｉ（ｔ），ｔ）とｚ１，ｉ，…，ｚｎ−１，ｉのハッシュ値ｃ１，ｉを生成する。つまり、署名生成アルゴリズムＳｉｇは、ｃ１，ｉ←Ｈ１（ｆ”ｉ（ｚ１，ｉ（ｔ），…，ｚｎ−１，ｉ（ｔ），ｔ），ｚ１，ｉ，…，ｚｎ−１，ｉ）を計算する。（処理４）署名生成アルゴリズムＳｉｇは、数ｗ’ｉのハッシュ値ｃ２，ｉを生成する。つまり、署名生成アルゴリズムＳｉｇは、ｃ２，ｉ←Ｈ２（ｗ’ｉ）を計算する。なお、上記のＨ１（…）、Ｈ２（…）は、ハッシュ関数である。
【０２９１】
（処理４）署名生成アルゴリズムＳｉｇは、乱数ＲＡを任意に選択する。（処理５）署名生成アルゴリズムＳｉｇは、α＝（α１，…，αＮ）←ＨＡ（ＲＡ，Ｍ，ｃ１，１，…，ｃ２，Ｎ）を計算する。（処理６）署名生成アルゴリズムＳｉｇは、ｉ＝１〜Ｎについて、ｆ”ｉ（ｘ１，…，ｘｎ）＝αｉｆ（ｘ１＋ｒ’１，ｉ（ｘｎ），…，ｘｎ−１，ｉ＋ｒ’ｎ−１，ｉ（ｘｎ），ｘｎ）＋ｆ’ｉ（ｘ１，…，ｘｎ）を計算する。（処理７）署名生成アルゴリズムＳｉｇは、乱数ＲＢを任意に選択する。（処理８）署名生成アルゴリズムＳｉｇは、ｄ＝（ｄ１，…，ｄＮ）←ＨＢ（ＲＢ，Ｍ，ｃ１，１，…，ｃ２，Ｎ，α，ｆ”１，…，ｆ”Ｎ）を計算する。
【０２９２】
次に、署名生成アルゴリズムＳｉｇは、ｉ＝１〜Ｎについて、ｄｉに応じた次の（処理９）又は（処理１０）を実行する。（処理９）ｄｉ＝０の場合、署名生成アルゴリズムＳｉｇは、σｉ←ｗｉを計算する。（処理１０）ｄｉ＝１の場合、署名生成アルゴリズムＳｉｇは、σｉ←（ｚ１，ｉ，…，ｚｎ−１，ｉ）を計算する。
【０２９３】
（処理１１）ｉ＝１〜Ｎについて、上記（処理９）又は（処理１０）の判定及び処理が実行された後、署名生成アルゴリズムＳｉｇは、電子署名σ＝（ＲＡ，ＲＢ，ｃ１，１，…，ｃ２，Ｎ，α１，…，αＮ，ｆ”１，…，ｆ”Ｎ）を出力する。
【０２９４】
（署名検証アルゴリズムＶｅｒ）
署名検証アルゴリズムＶｅｒは、ｉ＝１〜Ｎについて、以下の全ての検証を通過すれば、電子署名σを受理し、１つでも検証を通過しなかった場合には電子署名σを拒否する。なお、署名検証アルゴリズムＶｅｒには、電子署名σと文書Ｍが入力されているものとする。まず、署名検証アルゴリズムＶｅｒは、α＝（α１，…，αＮ）←ＨＡ（ＲＡ，Ｍ，ｃ１，１，…，ｃ３，Ｎ）を計算する。次いで、署名検証アルゴリズムＶｅｒは、ｄ＝（ｄ１，…，ｄＮ）←Ｈ（Ｒ，Ｍ，ｃ１，１，…，ｃ３，Ｎ，α，ｆ”１，…，ｆ”Ｎ）を計算する。次いで、署名検証アルゴリズムＶｅｒは、ｉ＝１〜Ｎについて、以下の（検証１）〜（検証３）を実行する。
【０２９５】
（検証１）ｄｉ＝０の場合、署名検証アルゴリズムＶｅｒは、（ｒ’１，ｉ，…，ｒ’ｎ−１，ｉ，ｆ”ｉ）←Ｇ（σｉ）を計算する。そして、署名検証アルゴリズムＶｅｒは、ｃ２，ｉ＝Ｈ２（σｉ）の等号が成り立つか否かを検証する。また、署名検証アルゴリズムＶｅｒは、ｆ”ｉ（ｘ１，…，ｘｎ）＝αｉｆ（ｘ１＋ｒ’１，ｉ（ｘｎ），…，ｘｎ−１，ｉ＋ｒ’ｎ−１，ｉ（ｘｎ），ｘｎ）＋ｆ’ｉ（ｘ１，…，ｘｎ）の等号が成り立つか否かを検証する。署名検証アルゴリズムＶｅｒは、これらの検証が全て成功した場合に電子署名σの受理を示す値１を出力し、検証に失敗があった場合に電子署名σの拒否を示す値０を出力する。
【０２９６】
（検証２）ｄｉ＝１の場合、署名検証アルゴリズムＶｅｒは、（ｚ’１，ｉ，…，ｚ’ｎ−１，ｉ，ｆ'''ｉ）←σｉを計算する。そして、署名検証アルゴリズムＶｅｒは、ｃ１，ｉ＝Ｈ１（ｆ'''ｉ（ｚ’１，ｉ（ｔ），…，ｚ’ｎ−１，ｉ（ｔ），ｔ），ｚ’１，ｉ，…，ｚ’ｎ−１，ｉ））の等号が成り立つか否かを検証する。署名検証アルゴリズムＶｅｒは、この検証が成功した場合に電子署名σの受理を示す値１を出力し、検証に失敗があった場合に電子署名σの拒否を示す値０を出力する。
【０２９７】
以上、本手法に基づく電子署名方式の各アルゴリズム構成について説明した。上記の電子署名方式は、代数曲面上の求セクション問題に安全性の根拠をおくものであるが、ＡＳＳ−ＣＣ電子署名方式のような安全性の問題を内包しない。なお、同様にして、上記の拡張方式に基づく電子署名方式を構築することも可能である。
【０２９８】
［３−６：具体例］
次に、図１６を参照しながら、本手法を実施する際に想定される具体的なアルゴリズム構成について説明する。図１６は、本手法の具体例を説明するための説明図である。
【０２９９】
（鍵生成アルゴリズムＧｅｎ）
鍵生成アルゴリズムＧｅｎは、環Ｋ上で定義される３変数のＤ次多項式ｆ０（ｘ，ｙ，ｔ）と、１変数の多次多項式ｕｘ（ｔ），ｕｙ（ｔ）を生成する。但し、Ｄ次多項式ｆ０（ｘ，ｙ，ｔ）は、下記の式（１４）により表現される。また、１変数の多次多項式ｕｘ（ｔ）は、下記の式（１５）により表現される。さらに、１変数の多次多項式ｕｙ（ｔ）は、下記の式（１６）により表現される。
【０３００】
【数９】
0005593850.tif 000010
【０３０１】
次に、鍵生成アルゴリズムＧｅｎは、ｃ（ｔ）←ｆ０（ｕｘ（ｔ），ｕｙ（ｔ），ｔ）を計算する。そして、鍵生成アルゴリズムＧｅｎは、ｆ（ｘ，ｙ，ｔ）＝ｆ０（ｘ，ｙ，ｔ）−ｃ（ｔ）を計算し、ｆを公開鍵ｐｋに設定する。また、鍵生成アルゴリズムＧｅｎは、（ｕｘ，ｕｙ）を秘密鍵ｓｋに設定する。なお、鍵生成アルゴリズムＧｅｎにより生成されるｆは、ｘ０ｙ０ｔｋの項以外については最大でＤ次となるが、ｘ０ｙ０ｔｋの項については最大で（Ｄ＋Ｄｓ）次になる。
【０３０２】
（証明者アルゴリズムＰ、検証者アルゴリズムＶ）
次に、図１６を参照しながら、対話プロトコルにおける証明者アルゴリズムＰと検証者アルゴリズムＶによる処理について説明する。この対話プロトコルは、「証明者がｆ（ｕｘ（ｔ），ｕｙ（ｔ），ｔ）を満たす（ｕｘ，ｕｙ）を知っていること」を（ｕｘ，ｕｙ）の情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムＧｅｎにより生成された公開鍵ｐｋは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムＧｅｎにより生成された秘密鍵ｓｋは、証明者により秘密に管理されているものとする。
【０３０３】
Ｓｔｅｐ．１：
まず、証明者アルゴリズムＰは、任意に数ｗを選択する。次いで、証明者アルゴリズムＰは、擬似乱数生成器Ｇに数ｗを適用して１変数多項式ｒｘ（ｔ），ｒｙ（ｔ）と、３変数多項式ｆ’（ｘ，ｙ，ｔ）を生成する。つまり、証明者アルゴリズムＰは、（ｒｘ，ｒｙ，ｆ’）←Ｇ（ｗ）を計算する。次いで、証明者アルゴリズムＰは、（ｚｘ（ｔ），ｚｙ（ｔ））←（ｕｘ（ｔ）−ｒｘ（ｔ），ｕｙ（ｔ）−ｒｙ（ｔ））を計算する。この計算は、秘密鍵（ｕｘ，ｕｙ）を１変数多項式（ｒｘ，ｒｙ）によりマスクする操作に相当する。
【０３０４】
Ｓｔｅｐ．１（続き）：
次いで、証明者アルゴリズムＰは、ｆ”（ｚｘ（ｔ），ｚｙ（ｔ），ｔ）とｚｘ，ｚｙのハッシュ値ｃ１を生成する。つまり、証明者アルゴリズムＰは、ｃ１←Ｈ１（ｆ”（ｚｘ（ｔ），ｚｙ（ｔ），ｔ），ｚｘ，ｚｙ）を計算する。また、証明者アルゴリズムＰは、数ｗのハッシュ値ｃ２を生成する。つまり、証明者アルゴリズムＰは、ｃ２←Ｈ２（ｗ）を計算する。なお、上記のＨ１（…）、Ｈ２（…）は、ハッシュ関数である。また、ハッシュ値（ｃ１，ｃ２）はメッセージである。
【０３０５】
Ｓｔｅｐ．１で生成されたメッセージ（ｃ１，ｃ２）は、検証者に送られる。
【０３０６】
Ｓｔｅｐ．２：
検証者アルゴリズムＶは、環Ｋの元から１つの乱数αを選択する。そして、検証者アルゴリズムＶは、選択した乱数αを証明者に送る。
【０３０７】
Ｓｔｅｐ．３：
証明者アルゴリズムＰは、ｆ”（ｘ，ｙ，ｔ）←αｆ（ｘ＋ｒｘ（ｔ），ｙ＋ｒｙ（ｔ），ｔ）＋ｆ’（ｘ，ｙ，ｔ）を計算する。この計算は、ｘ，ｙ，ｔについての多項式ｆ（ｘ＋ｒｘ（ｔ），…，ｙ＋ｒｙ（ｔ），ｔ）を多項式ｆ’（ｘ，ｙ，ｔ）によりマスクする操作に相当する。
【０３０８】
Ｓｔｅｐ．３で生成されたメッセージｆ”は、検証者に送られる。
【０３０９】
Ｓｔｅｐ．４：
検証者アルゴリズムＶは、２つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。次いで、検証者アルゴリズムＶは、選択した検証パターンを表す要求ｄ∈｛０，１｝を証明者に送る。
【０３１０】
Ｓｔｅｐ．５：
証明者アルゴリズムＰは、検証者から受けた要求ｄに応じて検証者に送り返す情報σを生成する。もしｄ＝０の場合、証明者アルゴリズムＰは、情報σ＝ｗを生成する。また、ｄ＝１の場合、証明者アルゴリズムＰは、情報σ＝（ｚｘ，ｚｙ）を生成する。このようにして生成された情報σは、証明者アルゴリズムＰにより検証者に送られる。
【０３１１】
Ｓｔｅｐ．６：
検証者アルゴリズムＶは、証明者から受け取った情報σを利用して以下の検証処理を実行する。
【０３１２】
ｄ＝０の場合、検証者アルゴリズムＶは、（ｒ’ｘ，ｒ’ｙ，ｆ'''）←Ｇ（σ）を計算する。そして、検証者アルゴリズムＶは、ｃ２＝Ｈ２（σ）の等号が成り立つか否かを検証する。また、検証者アルゴリズムＶは、ｆ”（ｘ，ｙ，ｔ）＝αｆ（ｘ＋ｒ’ｘ（ｔ），ｙ＋ｒ’ｙ（ｔ），ｔ）＋ｆ'''（ｘ，ｙ，ｔ）の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、これらの検証が全て成功した場合に認証成功を示す値１を出力し、検証に失敗があった場合に認証失敗を示す値０を出力する。
【０３１３】
ｄ＝１の場合、検証者アルゴリズムＶは、（ｚ’ｘ，ｚ’ｙ）←σを計算する。そして、検証者アルゴリズムＶは、ｃ１＝Ｈ１（ｆ'''（ｚ’ｘ（ｔ），ｚ’ｙ（ｔ），ｔ），ｚ’ｘ，ｚ’ｙ））の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、この検証が成功した場合に認証成功を示す値１を出力し、検証に失敗があった場合に認証失敗を示す値０を出力する。
【０３１４】
以上、本手法を実施する際に想定される具体的なアルゴリズム構成について説明した。
【０３１５】
＜４：ハードウェア構成例＞
上記の各アルゴリズムは、例えば、図１７に示す情報処理装置のハードウェア構成を用いて実行することが可能である。つまり、当該各アルゴリズムの処理は、コンピュータプログラムを用いて図１７に示すハードウェアを制御することにより実現される。なお、このハードウェアの形態は任意であり、例えば、パーソナルコンピュータ、携帯電話、ＰＨＳ、ＰＤＡ等の携帯情報端末、ゲーム機、接触式又は非接触式のＩＣチップ、接触式又は非接触式のＩＣカード、又は種々の情報家電がこれに含まれる。但し、上記のＰＨＳは、Ｐｅｒｓｏｎａｌ  Ｈａｎｄｙ−ｐｈｏｎｅ  Ｓｙｓｔｅｍの略である。また、上記のＰＤＡは、Ｐｅｒｓｏｎａｌ  Ｄｉｇｉｔａｌ  Ａｓｓｉｓｔａｎｔの略である。
【０３１６】
図１７に示すように、このハードウェアは、主に、ＣＰＵ９０２と、ＲＯＭ９０４と、ＲＡＭ９０６と、ホストバス９０８と、ブリッジ９１０と、を有する。さらに、このハードウェアは、外部バス９１２と、インターフェース９１４と、入力部９１６と、出力部９１８と、記憶部９２０と、ドライブ９２２と、接続ポート９２４と、通信部９２６と、を有する。但し、上記のＣＰＵは、Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔの略である。また、上記のＲＯＭは、Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙの略である。そして、上記のＲＡＭは、Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙの略である。
【０３１７】
ＣＰＵ９０２は、例えば、演算処理装置又は制御装置として機能し、ＲＯＭ９０４、ＲＡＭ９０６、記憶部９２０、又はリムーバブル記録媒体９２８に記録された各種プログラムに基づいて各構成要素の動作全般又はその一部を制御する。ＲＯＭ９０４は、ＣＰＵ９０２に読み込まれるプログラムや演算に用いるデータ等を格納する手段である。ＲＡＭ９０６には、例えば、ＣＰＵ９０２に読み込まれるプログラムや、そのプログラムを実行する際に適宜変化する各種パラメータ等が一時的又は永続的に格納される。
【０３１８】
これらの構成要素は、例えば、高速なデータ伝送が可能なホストバス９０８を介して相互に接続される。一方、ホストバス９０８は、例えば、ブリッジ９１０を介して比較的データ伝送速度が低速な外部バス９１２に接続される。また、入力部９１６としては、例えば、マウス、キーボード、タッチパネル、ボタン、スイッチ、及びレバー等が用いられる。さらに、入力部９１６としては、赤外線やその他の電波を利用して制御信号を送信することが可能なリモートコントローラ（以下、リモコン）が用いられることもある。
【０３１９】
出力部９１８としては、例えば、ＣＲＴ、ＬＣＤ、ＰＤＰ、又はＥＬＤ等のディスプレイ装置、スピーカ、ヘッドホン等のオーディオ出力装置、プリンタ、携帯電話、又はファクシミリ等、取得した情報を利用者に対して視覚的又は聴覚的に通知することが可能な装置である。但し、上記のＣＲＴは、Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅの略である。また、上記のＬＣＤは、Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙの略である。そして、上記のＰＤＰは、Ｐｌａｓｍａ  ＤｉｓｐｌａｙＰａｎｅｌの略である。さらに、上記のＥＬＤは、Ｅｌｅｃｔｒｏ−Ｌｕｍｉｎｅｓｃｅｎｃｅ  Ｄｉｓｐｌａｙの略である。
【０３２０】
記憶部９２０は、各種のデータを格納するための装置である。記憶部９２０としては、例えば、ハードディスクドライブ（ＨＤＤ）等の磁気記憶デバイス、半導体記憶デバイス、光記憶デバイス、又は光磁気記憶デバイス等が用いられる。但し、上記のＨＤＤは、Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅの略である。
【０３２１】
ドライブ９２２は、例えば、磁気ディスク、光ディスク、光磁気ディスク、又は半導体メモリ等のリムーバブル記録媒体９２８に記録された情報を読み出し、又はリムーバブル記録媒体９２８に情報を書き込む装置である。リムーバブル記録媒体９２８は、例えば、ＤＶＤメディア、Ｂｌｕ−ｒａｙメディア、ＨＤ  ＤＶＤメディア、各種の半導体記憶メディア等である。もちろん、リムーバブル記録媒体９２８は、例えば、非接触型ＩＣチップを搭載したＩＣカード、又は電子機器等であってもよい。但し、上記のＩＣは、Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔの略である。
【０３２２】
接続ポート９２４は、例えば、ＵＳＢポート、ＩＥＥＥ１３９４ポート、ＳＣＳＩ、ＲＳ−２３２Ｃポート、又は光オーディオ端子等のような外部接続機器９３０を接続するためのポートである。外部接続機器９３０は、例えば、プリンタ、携帯音楽プレーヤ、デジタルカメラ、デジタルビデオカメラ、又はＩＣレコーダ等である。但し、上記のＵＳＢは、Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓの略である。また、上記のＳＣＳＩは、Ｓｍａｌｌ  Ｃｏｍｐｕｔｅｒ  Ｓｙｓｔｅｍ  Ｉｎｔｅｒｆａｃｅの略である。
【０３２３】
通信部９２６は、ネットワーク９３２に接続するための通信デバイスであり、例えば、有線又は無線ＬＡＮ、Ｂｌｕｅｔｏｏｔｈ（登録商標）、又はＷＵＳＢ用の通信カード、光通信用のルータ、ＡＤＳＬ用のルータ、又は接触又は非接触通信用のデバイス等である。また、通信部９２６に接続されるネットワーク９３２は、有線又は無線により接続されたネットワークにより構成され、例えば、インターネット、家庭内ＬＡＮ、赤外線通信、可視光通信、放送、又は衛星通信等である。但し、上記のＬＡＮは、Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋの略である。また、上記のＷＵＳＢは、Ｗｉｒｅｌｅｓｓ  ＵＳＢの略である。そして、上記のＡＤＳＬは、Ａｓｙｍｍｅｔｒｉｃ  Ｄｉｇｉｔａｌ  Ｓｕｂｓｃｒｉｂｅｒ  Ｌｉｎｅの略である。
【０３２４】
＜５：まとめ＞
最後に、本発明の実施形態に係る技術内容について簡単に纏める。ここで述べる技術内容は、例えば、ＰＣ、携帯電話、携帯ゲーム機、携帯情報端末、情報家電、カーナビゲーションシステム等、種々の情報処理装置に対して適用することができる。
【０３２５】
上記の情報処理装置の機能構成は次のように表現することができる。当該情報処理装置は、次に示すような鍵設定部と、メッセージ送信部と、検証パターン受信部と、回答送信部とを有する。上記の鍵設定部は、多次多項式ｕｉ（ｔ）（ｉ＝１〜ｎ−１）を秘密鍵に設定し、ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｆを公開鍵に設定するものである。ｆ（ｕ１（ｔ），…，ｕｎ−１（ｔ），ｔ）＝０を満たす多次多項式ｕｉ（ｔ）を求める問題は、代数曲面上の求セクション問題に他ならない。つまり、上記の情報処理装置は、代数曲面上の求セクション問題に安全性の根拠をおく認証の仕組みを提供するものである。
【０３２６】
また、上記のメッセージ送信部は、検証者に対してメッセージｃを送信するものである。さらに、上記の検証パターン受信部は、１つの前記メッセージｃに対するｋ通り（ｋ≧３）の検証パターンの中から前記検証者により選択された１つの検証パターンの情報を受信するものである。そして、上記の回答送信部は、ｋ通りの回答情報の中から、前記検証パターン受信部により受信された検証パターンの情報に対応する回答情報を前記検証者に送信するものである。但し、前記回答情報は、前記ｋ通りの回答情報を用いて実施した前記メッセージｃに対するｋ通りの検証パターンが全て成功した場合に秘密鍵ｕｉが計算可能となる情報である。
【０３２７】
上記のメッセージｃには、例えば、３つのメッセージｃ１、ｃ２、ｃ３が含まれている。そして、各検証パターンでは、ｃ１、ｃ２、ｃ３のいずれか２つに対する検証が行われる。また、上記の回答情報は、各検証パターンに応じて、上記いずれか２つのメッセージに対する検証を行うために必要な情報である。但し、上記のメッセージｃを検証者に渡しても、秘密鍵の情報が一切漏れないことが１つの条件である。もう１つの条件は、メッセージｃと回答情報が揃っても秘密鍵の情報が一切漏れないことである。これらの条件を満たすメッセージｃの構成、及び回答情報の構成については、図６などを参照しながら、既に具体的に説明した通りである。
【０３２８】
（備考）
上記の鍵生成アルゴリズムＧｅｎは、鍵設定部の一例である。上記の証明者アルゴリズムＰは、メッセージ送信部、検証パターン受信部、回答送信部、応答受信部、多項式生成部、多項式送信部の一例である。上記の情報σは、回答情報の一例である。上記の検証者アルゴリズムＶは、メッセージ受信部、検証パターン選択部、検証パターン送信部、回答受信部、検証部、応答送信部、多項式受信部の一例である。上記の署名生成アルゴリズムＳｉｇは、メッセージ生成部、検証パターン選択部、署名生成部の一例である。
【０３２９】
以上、添付図面を参照しながら本発明の好適な実施形態について説明したが、本発明は係る例に限定されないことは言うまでもない。当業者であれば、特許請求の範囲に記載された範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、それらについても当然に本発明の技術的範囲に属するものと了解される。
【符号の説明】
【０３３０】
Ｇｅｎ    鍵生成アルゴリズム
Ｐ        証明者アルゴリズム
Ｖ        検証者アルゴリズム
Ｓｉｇ    署名生成アルゴリズム
Ｖｅｒ    署名検証アルゴリズム
【図１】
0005593850.tif 000011
【図２】
0005593850.tif 000012
【図３】
0005593850.tif 000013
【図４】
0005593850.tif 000014
【図５】
0005593850.tif 000015
【図６】
0005593850.tif 000016
【図７】
0005593850.tif 000017
【図８】
0005593850.tif 000018
【図９】
0005593850.tif 000019
【図１０】
0005593850.tif 000020
【図１１】
0005593850.tif 000021
【図１２】
0005593850.tif 000022
【図１３】
0005593850.tif 000023
【図１４】
0005593850.tif 000024
【図１５】
0005593850.tif 000025
【図１６】
0005593850.tif 000026
【図１７】
0005593850.tif 000027
【図１８】
0005593850.tif 000028