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