説明

認証装置、認証方法、及びプログラム

【課題】能動的攻撃に対する安全性レベルを実現すること。
【解決手段】L個(L≧2)の秘密鍵s(i=1〜L)、及びn次多変数多項式F(n≧2)についてy=F(s)を満たすL個の公開鍵yを保持する鍵保持部と、(L−1)個のy=F(s)を満たす秘密鍵sを知っていることを証明するための対話プロトコルを検証者との間で実行する対話プロトコル実行部と、を備え、前記対話プロトコル実行部は、前記検証者との間で前記対話プロトコルを実行する際に、どの秘密鍵sを使用したかを当該検証者に知られないようにする、認証装置が提供される。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、認証装置、認証方法、及びプログラムに関する。
【背景技術】
【0002】
情報処理技術や通信技術の急速な発展に伴い、公文書、私文書を問わず、文書の電子化が急速に進んでいる。これに伴い、多くの個人や企業は、電子文書の安全管理に大きな関心を寄せている。こうした関心の高まりを受け、各方面で電子文書の盗聴や偽造等のタンパリング行為に対する安全性が盛んに議論されるようになってきた。電子文書の盗聴に対する安全性は、例えば、電子文書を暗号化することにより確保される。また、電子文書の偽造に対する安全性は、例えば、電子署名を利用することにより確保される。但し、暗号や電子署名には十分なタンパリング耐性が求められる。
【0003】
電子署名は、電子文書の作成者を特定するために利用される。そのため、電子署名は、電子文書の作成者しか生成できないようにすべきである。仮に、悪意ある第三者が同じ電子署名を生成できてしまうと、その第三者が電子文書の作成者に成りすますことができてしまう。つまり、悪意ある第三者により電子文書が偽造されてしまう。こうした偽造を防止するため、電子署名の安全性については様々な議論が交わされてきた。現在広く利用されている電子署名方式としては、例えば、RSA署名方式やDSA署名方式を利用する方式が知られている。
【0004】
RSA署名方式は、「大きな合成数に対する素因数分解の困難性(以下、素因数分解問題)」を安全性の根拠とする。また、DSA署名方式は、「離散対数問題に対する解の導出の困難性」を安全性の根拠とする。これらの根拠は、古典的なコンピュータを利用して素因数分解問題や離散対数問題を効率的に解くアルゴリズムが存在しないことに起因する。つまり、上記の困難性は、古典的なコンピュータにおける計算量的な困難性を意味する。しかしながら、量子コンピュータを用いると、素因数分解問題や離散対数問題に対する解答が効率的に算出されてしまうと言われている。
【0005】
現在利用されている電子署名方式や公開鍵認証方式の多くは、RSA署名方式やDSA署名方式と同様、素因数分解問題や離散対数問題の困難性に安全性の根拠をおいている。そのため、こうした電子署名方式や公開鍵認証方式は、量子コンピュータが実用化された場合に、その安全性が確保されないことになる。そこで、素因数分解問題や離散対数問題など、量子コンピュータにより容易に解かれてしまう問題とは異なる問題に安全性の根拠をおく新たな電子署名方式及び公開鍵認証方式が求められている。量子コンピュータにより容易に解くことが難しい問題としては、例えば、多変数多項式に対する解答の困難性(以下、多変数多項式問題)がある。
【0006】
その他にも、量子コンピュータにより解くことが困難とされている問題として、Syndrome Decoding問題、Constrained Linear Equation問題、Permuted Kernel問題、Permuted Perception問題、代数曲面上の求セクション問題などがある。
【0007】
これらの問題のうち、代数曲面上の求セクション問題以外の問題はNP困難であることが知られている。その応用例として、例えば、下記の非特許文献1、2には、Syndrome Decoding問題に基づく公開鍵認証方式が開示されている。また、下記の非特許文献3には、Permuted Kernel問題に基づく公開鍵認証方式が開示されている。これら以外にも、Constrained Linear Equations問題に基づく公開鍵認証方式やPermuted Perceptions問題に基づく公開鍵認証方式などが提案されている。
【先行技術文献】
【非特許文献】
【0008】
【非特許文献1】Jacques Stern, A New Identification Scheme Based on Syndrome Decoding, CRYPTO 1993, p13−21.
【非特許文献2】Jacques Stern, A New Paradigm for Public Key Identification, IEEE Transactions on Information Theory, 1996, p13−21.
【非特許文献3】Adi Shamir, An Efficient Identification Scheme Based on Permuted Kernels (Extended Abstract), CRYPTO 1989, p606−609.
【発明の概要】
【発明が解決しようとする課題】
【0009】
ここで、公開鍵認証方式の安全性レベルについて言及しておきたい。公開鍵認証方式の安全性レベルには、2つの安全性レベルが存在する。その1つは、受動的攻撃(passive attack)に対する安全性レベルである。もう1つは、能動的攻撃(active attack)に対する安全性レベルである。受動的攻撃に対する安全性レベルは、正当なプロトコルに従う証明者と検証者の対話を盗聴することのみが可能な攻撃者を想定した安全性のレベルである。一方、能動的攻撃に対する安全性レベルは、攻撃者自身が直接的に証明者と対話プロトコルを実行することができる状況を想定した安全性のレベルである。つまり、能動的攻撃に対する安全性レベルは、攻撃者が好きなように証明者と対話プロトコルを行なえるということが想定されているのである。
【0010】
上記の非特許文献1〜3に記載されているような従来の公開鍵認証方式は、受動的攻撃に対する安全性レベルを保証している。しかし、これら従来の公開鍵認証方式は、並列的繰り返し構成を行なった場合、能動的攻撃に対する安全性レベルを確実に保証しているか否かが知られていない。なぜならば、並列的繰り返し構成を行なった場合、零知識性は保存されないということが一般に知られているからである。そのため、並列的繰り返し構成において能動的攻撃に対する安全性レベルを確実に保証するためには、さらに別の性質を保証する必要がある。
【0011】
従来の公開鍵認証方式は、1組の鍵ペア(公開鍵y、秘密鍵s)を用いて「yについてy=F(s)となるsを知っていること」を証明者が検証者に対して証明する方式であった。そのため、検証で受理される対話を行った場合、「対話を行った証明者がsを用いた」という情報を検証者に知られてしまうことが避けられなかった。また、この形式の公開鍵認証方式の並列的繰り返し構成では、Fに衝突困難性の保証がない場合、能動的攻撃に対する安全性レベルを確実に保証しているか否かが知られていなかった。実際、前述の公開鍵認証方式で用いられている関数Fでは、衝突困難性は保証されていない。
【0012】
そこで、本発明は、上記問題に鑑みてなされたものであり、本発明の目的とするところは、関数Fに衝突困難性が保証されていなくても、対話プロトコルを並列的に繰り返し実行したとしても、能動的攻撃に対する安全性レベルを保証することが可能な、新規かつ改良された認証装置、認証方法、及びプログラムを提供することにある。
【課題を解決するための手段】
【0013】
上記課題を解決するために、本発明のある観点によれば、L個(L≧2)の秘密鍵si(i=1〜L)、及びn次多変数多項式の組F(n≧2)についてy=F(s)を満たすL個の公開鍵yを保持する鍵保持部と、(L−1)個のy=F(s)を満たす秘密鍵siを知っていることを証明するための対話プロトコルを検証者との間で実行する対話プロトコル実行部と、を備え、前記対話プロトコル実行部は、前記検証者との間で前記対話プロトコルを実行する際に、どの秘密鍵sを使用したかを当該検証者に知られないようにする、認証装置が提供される。
【0014】
また、前記対話プロトコル実行部は、前記検証者からL個のチャレンジChを受信するチャレンジ受信部と、前記チャレンジ受信部により受信されたL個のチャレンジChの中から(L−1)個のチャレンジChを任意に選択するチャレンジ選択部と、前記秘密鍵sを用いて、前記チャレンジ選択部により選択された(L−1)個のチャレンジChのそれぞれに対する(L−1)個の回答Rspを生成する回答生成部と、前記回答生成部により生成された(L−1)個の回答Rspを前記検証者に送信する回答送信部と、を含んでいてもよい。
【0015】
また、前記対話プロトコル実行部は、前記検証者に対し、L個の前記秘密鍵sのそれぞれに対応するメッセージCmtを送信するメッセージ送信部をさらに含んでいてもよい。この場合、前記チャレンジ受信部は、前記メッセージ送信部により送信された各メッセージCmtに応じて、前記検証者によりk通り(k≧2)の検証パターンの中から選択された検証パターンを示すチャレンジChを受信する。
【0016】
また、前記メッセージCmtがCmt=(ci,1,…,ci,N)である場合、前記メッセージ送信部は、一方向性関数Hを用いて新たなメッセージCmt’=H(Cmt,…,Cmt)を算出して当該メッセージCmt’を前記検証者に送信し、前記回答送信部は、前記回答Rspと共に、当該回答Rspを利用しても前記検証者が復元できない前記メッセージCmtの要素を送信する、ように構成されていてもよい。
【0017】
また、前記鍵保持部は、前記L個の秘密鍵sのうち、1つの秘密鍵si0(1≦i≦L)を保持しないようにしてもよい。この場合、前記対話プロトコル実行部は、前記対話プロトコルの中で実行される前記秘密鍵si0に関する処理を偽証アルゴリズムに基づいて実行する。
【0018】
また、上記課題を解決するために、本発明の別の観点によれば、L個の秘密鍵s(i=1〜L)、n次多変数多項式の組F(n≧2)についてy=F(s)を満たすL個の公開鍵yを保持する鍵保持部と、検証者からQ組(Q≧2)のL個のチャレンジCh(j)(j=1〜Q)を受信するチャレンジ受信部と、前記チャレンジ受信部により受信されたQ組のL個のチャレンジCh(j)の中から1組のL個のチャレンジCh(j)を任意に選択するチャレンジ選択部と、前記秘密鍵sを用いて、前記チャレンジ選択部により選択されたL個のチャレンジCh(j)のそれぞれに対するL個の回答Rspを生成する回答生成部と、前記回答生成部により生成されたL個の回答Rspを前記検証者に送信する回答送信部と、を備える、認証装置が提供される。
【0019】
また、前記対話プロトコル実行部は、前記検証者に対し、L個の前記秘密鍵sのそれぞれに対応するメッセージCmtを送信するメッセージ送信部をさらに含んでいてもよい。この場合、前記チャレンジ受信部は、前記メッセージ送信部により送信された各メッセージCmtに応じて、前記検証者によりk通り(k≧2)の検証パターンの中から選択された検証パターンを示すチャレンジCh(j)を受信する。
【0020】
また、前記メッセージCmtがCmt=(ci,1,…,ci,N)である場合、前記メッセージ送信部は、一方向性関数Hを用いて新たなメッセージCmt’=H(Cmt,…,Cmt)を算出して当該メッセージCmt’を前記検証者に送信し、前記回答送信部は、前記回答Rspと共に、当該回答Rspを利用しても前記検証者が復元できない前記メッセージCmtの要素を送信する、ように構成されていてもよい。
【0021】
また、上記課題を解決するために、本発明の別の観点によれば、L個(L≧2)の秘密鍵s(i=1〜L)、及びn次多変数多項式の組F(n≧2)についてy=F(s)を満たすL個の公開鍵yを生成する鍵生成ステップと、(L−1)個のy=F(s)を満たす秘密鍵sを知っていることを証明するための対話プロトコルを検証者との間で実行する対話プロトコル実行ステップと、を含み、前記対話プロトコル実行ステップでは、前記検証者との間で前記対話プロトコルを実行する際に、どの秘密鍵sを使用したかを当該検証者に知られないようにする、認証方法が提供される。
【0022】
また、上記課題を解決するために、本発明の別の観点によれば、L個(L≧2)の秘密鍵s(i=1〜L)、及びn次多変数多項式の組F(n≧2)についてy=F(s)を満たすL個の公開鍵yを保持する鍵保持機能と、(L−1)個のy=F(s)を満たす秘密鍵sを知っていることを証明するための対話プロトコルを検証者との間で実行する対話プロトコル実行機能と、をコンピュータに実現させるためのプログラムであり、前記対話プロトコル実行機能は、前記検証者との間で前記対話プロトコルを実行する際に、どの秘密鍵sを使用したかを当該検証者に知られないようにする、プログラムが提供される。
【0023】
また、上記課題を解決するために、本発明の別の観点によれば、L個の秘密鍵s(i=1〜L)、n次多変数多項式の組F(n≧2)についてy=F(s)を満たすL個の公開鍵yを生成する鍵生成ステップと、検証者からQ組(Q≧2)のL個のチャレンジCh(j)(j=1〜Q)を受信するチャレンジ受信ステップと、前記チャレンジ受信ステップで受信されたQ組のL個のチャレンジCh(j)の中から1組のL個のチャレンジCh(j)を任意に選択するチャレンジ選択ステップと、前記秘密鍵sを用いて、前記チャレンジ選択ステップで選択されたL個のチャレンジCh(j)のそれぞれに対するL個の回答Rspを生成する回答生成ステップと、前記回答生成ステップで生成されたL個の回答Rspを前記検証者に送信する回答送信ステップと、を含む、認証方法が提供される。
【0024】
また、上記課題を解決するために、本発明の別の観点によれば、L個の秘密鍵s(i=1〜L)、n次多変数多項式の組F(n≧2)についてy=F(s)を満たすL個の公開鍵yを保持する鍵保持機能と、検証者からQ組(Q≧2)のL個のチャレンジCh(j)(j=1〜Q)を受信するチャレンジ受信機能と、前記チャレンジ受信機能により受信されたQ組のL個のチャレンジCh(j)の中から1組のL個のチャレンジCh(j)を任意に選択するチャレンジ選択機能と、前記秘密鍵sを用いて、前記チャレンジ選択機能により選択されたL個のチャレンジCh(j)のそれぞれに対するL個の回答Rspを生成する回答生成機能と、前記回答生成機能により生成されたL個の回答Rspを前記検証者に送信する回答送信機能と、をコンピュータに実現させるためのプログラムが提供される。また、上記課題を解決するために、本発明の別の観点によれば、上記のプログラムが記録された、コンピュータにより読み取り可能な記録媒体が提供される。
【発明の効果】
【0025】
以上説明したように本発明によれば、対話プロトコルを並列的に繰り返し実行したとしても、能動的攻撃に対する安全性レベルを保証することが可能になる。
【図面の簡単な説明】
【0026】
【図1】公開鍵認証方式のアルゴリズム構成について説明するための説明図である。
【図2】nパスの公開鍵認証方式について説明するための説明図である。
【図3】SSH10a公開鍵認証方式の対話プロトコルについて説明するための説明図である。
【図4】SSH10b公開鍵認証方式の対話プロトコルについて説明するための説明図である。
【図5】対話プロトコルの直列的繰り返し構成について説明するための説明図である。
【図6】対話プロトコルの並列的繰り返し構成について説明するための説明図である。
【図7】SSH10a公開鍵認証方式の対話プロトコルに対する偽証アルゴリズムについて説明するための説明図である。
【図8】SSH10b公開鍵認証方式の対話プロトコルに対する偽証アルゴリズムについて説明するための説明図である。
【図9】SSH10a公開鍵認証方式の対話プロトコルに対する本手法#1の適用方法について説明するための説明図である。
【図10】SSH10a公開鍵認証方式の対話プロトコルに対する本手法#1の適用方法(変形例1)について説明するための説明図である。
【図11】SSH10a公開鍵認証方式の対話プロトコルに対する本手法#1の適用方法(変形例2)について説明するための説明図である。
【図12】SSH10a公開鍵認証方式の対話プロトコルに対する本手法#1の適用方法(変形例3)について説明するための説明図である。
【図13】SSH10b公開鍵認証方式の対話プロトコルに対する本手法#1の適用方法について説明するための説明図である。
【図14】SSH10b公開鍵認証方式の対話プロトコルに対する本手法#1の適用方法(変形例)について説明するための説明図である。
【図15】SSH10a公開鍵認証方式の対話プロトコルに対する本手法#2の適用方法について説明するための説明図である。
【図16】SSH10a公開鍵認証方式の対話プロトコルに対する本手法#2の適用方法(変形例)について説明するための説明図である。
【図17】SSH10b公開鍵認証方式の対話プロトコルに対する本手法#2の適用方法について説明するための説明図である。
【図18】SSH10b公開鍵認証方式の対話プロトコルに対する本手法#2の適用方法(変形例)について説明するための説明図である。
【図19】SSH10a公開鍵認証方式の対話プロトコルにおける通信量の削減方法について説明するための説明図である。
【図20】SSH10b公開鍵認証方式の対話プロトコルにおける通信量の削減方法について説明するための説明図である。
【図21】本実施形態に係る対話プロトコルを実現することが可能な情報処理装置のハードウェア構成例について説明するための説明図である。
【発明を実施するための形態】
【0027】
以下に添付図面を参照しながら、本発明の好適な実施の形態について詳細に説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。
【0028】
[説明の流れについて]
ここで、以下に記載する本発明の実施形態に関する説明の流れについて簡単に述べる。まず、図1を参照しながら、公開鍵認証方式のアルゴリズム構成について説明する。次いで、図2を参照しながら、nパスの公開鍵認証方式について説明する。次いで、図3を参照しながら、SSH10a公開鍵認証方式の対話プロトコルについて説明する。次いで、図4を参照しながら、SSH10b公開鍵認証方式の対話プロトコルについて説明する。次いで、図5、図6を参照しながら、対話プロトコルの繰り返し構成について説明する。この中で、能動的攻撃に対する安全性レベルについて簡単に説明する。
【0029】
次いで、図7を参照しながら、SSH10a公開鍵認証方式の対話プロトコルに対する偽証アルゴリズムについて説明する。次いで、図8を参照しながら、SSH10b公開鍵認証方式の対話プロトコルに対する偽証アルゴリズムについて説明する。次いで、図9〜図12を参照しながら、本発明の第1実施形態に係る手法(本手法#1)をSSH10a公開鍵認証方式の対話プロトコルに適用する方法について説明する。次いで、図13、図14を参照しながら、本手法#1をSSH10b公開鍵認証方式の対話プロトコルに適用する方法について説明する。
【0030】
次いで、図15、図16を参照しながら、本発明の第2実施形態に係る手法(本手法#2)をSSH10a公開鍵認証方式の対話プロトコルに適用する方法について説明する。次いで、図17、図18を参照しながら、本手法#2をSSH10b公開鍵認証方式の対話プロトコルに適用する方法について説明する。次いで、図19、図20を参照しながら、本実施形態に係る対話プロトコルにおける通信量の削減方法について説明する。次いで、図21を参照しながら、本実施形態に係る対話プロトコルを実現することが可能な情報処理装置のハードウェア構成例について説明する。最後に、同実施形態の技術的思想について纏め、当該技術的思想から得られる作用効果について簡単に説明する。
【0031】
(説明項目)
1:はじめに
1−1:公開鍵認証方式のアルゴリズム構成
1−2:nパスの公開鍵認証方式について
1−3:SSH10a公開鍵認証方式の対話プロトコル
1−4:SSH10b公開鍵認証方式の対話プロトコル
1−5:対話プロトコルの繰り返し構成
1−6:SSH10a公開鍵認証方式に対する偽証アルゴリズム
1−7:SSH10b公開鍵認証方式に対する偽証アルゴリズム
2:第1実施形態(本手法#1)
2−1:概要
2−2:SSH10a公開鍵認証方式への適用
2−3:SSH10a公開鍵認証方式への適用(変形例1)
2−4:SSH10a公開鍵認証方式への適用(変形例2)
2−5:SSH10a公開鍵認証方式への適用(変形例3)
2−6:SSH10b公開鍵認証方式への適用
2−7:SSH10b公開鍵認証方式への適用(変形例)
3:第2実施形態(本手法#2)
3−1:概要
3−2:SSH10a公開鍵認証方式への適用
3−3:SSH10a公開鍵認証方式への適用(変形例)
3−4:SSH10b公開鍵認証方式への適用
3−5:SSH10b公開鍵認証方式への適用(変形例)
4:補足
4−1:方式の拡張について
4−2:非対話型の公開鍵認証方式について
4−3:通信量の削減方法について
5:ハードウェア構成
6:まとめ
【0032】
<1:はじめに>
はじめに、本発明に係る実施形態について詳細に説明するに先立ち、一般的な公開鍵認証方式のアルゴリズム構成、及びnパスの公開鍵認証方式について簡単に説明する。
【0033】
[1−1:公開鍵認証方式のアルゴリズム構成]
まず、図1を参照しながら、公開鍵認証方式のアルゴリズム構成について説明する。図1は、公開鍵認証方式のアルゴリズム構成について説明するための説明図である。
【0034】
(概要)
公開鍵認証方式とは、ある人(証明者)が、公開鍵pk及び秘密鍵skを利用して、他の人(検証者)に本人であることを納得させるための認証方式である。例えば、証明者Aの公開鍵pkは、検証者に公開される。一方、証明者Aの秘密鍵skは、証明者により秘密に管理される。公開鍵認証方式では、公開鍵pkに対応する秘密鍵skを知る者が証明者A本人であるとみなされる。
【0035】
証明者Aが検証者Bに対して本人であることを証明しようとする場合、証明者Aは、検証者Bと対話プロトコルを実行して、自身が公開鍵pkに対応する秘密鍵skを知っていることを証明すればよい。そして、対話プロトコルにより証明者Aが秘密鍵skを知っていることが検証者Bにより証明された場合、証明者Aの正当性(本人であること)が証明される。
【0036】
なお、公開鍵認証方式の安全性を確保するには、次に示す2つの条件が求められる。
【0037】
1つ目の条件は、対話プロトコルを実行した際に秘密鍵skを持たない偽証者により偽証が成立してしまう確率を限りなく小さくすることである。この1つ目の条件が成り立つことを「健全性」と呼ぶ。つまり、健全性を有する対話プロトコルにおいては、秘密鍵skを持たない偽証者により、無視できない確率で偽証が成立することはないと言い換えられる。2つ目の条件は、対話プロトコルを実行したとしても、証明者Aが有する秘密鍵skの情報が検証者Bに一切漏れることがないようにすることである。この2つ目の条件が成り立つことを「零知識性」と呼ぶ。
【0038】
上記の健全性と零知識性を有する対話プロトコルを利用することにより、公開鍵認証方式の安全性が確保される。
【0039】
(モデル)
公開鍵認証方式のモデルには、図1に示すように、証明者と検証者という2つのエンティティが存在する。証明者は、鍵生成アルゴリズムGenを用いて、証明者固有の秘密鍵skと公開鍵pkの組を生成する。次いで、証明者は、鍵生成アルゴリズムGenを用いて生成した秘密鍵skと公開鍵pkの組を利用して検証者と対話プロトコルを実行する。このとき、証明者は、証明者アルゴリズムPを利用して対話プロトコルを実行する。上記の通り、対話プロトコルにおいて、証明者は、証明者アルゴリズムPを利用して、秘密鍵skを保有していることを検証者に証明する。
【0040】
一方、検証者は、検証者アルゴリズムVを利用して対話プロトコルを実行し、証明者が公開している公開鍵に対応する秘密鍵を、その証明者が保有しているか否かを検証する。つまり、検証者は、証明者が公開鍵に対応する秘密鍵を保有しているか否かを検証するエンティティである。このように、公開鍵認証方式のモデルは、証明者と検証者という2つのエンティティ、及び、鍵生成アルゴリズムGen、証明者アルゴリズムP、検証者アルゴリズムVという3つのアルゴリズムにより構成される。
【0041】
なお、以下の説明において、「証明者」「検証者」という表現を用いるが、これらの表現はあくまでもエンティティを意味するものである。従って、鍵生成アルゴリズムGen、証明者アルゴリズムPを実行する主体は、「証明者」のエンティティに対応する情報処理装置である。同様に、検証者アルゴリズムVを実行する主体は、情報処理装置である。これら情報処理装置のハードウェア構成は、例えば、図21に示した通りである。つまり、鍵生成アルゴリズムGen、証明者アルゴリズムP、検証者アルゴリズムVは、ROM904、RAM906、記憶部920、リムーバブル記録媒体928などに記録されたプログラムに基づいてCPU902により実行される。
【0042】
(鍵生成アルゴリズムGen)
鍵生成アルゴリズムGenは、証明者により利用される。そして、鍵生成アルゴリズムGenは、証明者に固有の秘密鍵skと公開鍵pkの組を生成するアルゴリズムである。鍵生成アルゴリズムGenにより生成された公開鍵pkは公開される。そして、公開された公開鍵pkは、検証者により利用される。一方、鍵生成アルゴリズムGenにより生成された秘密鍵skは、証明者が秘密に管理する。そして、秘密に管理される秘密鍵skは、検証者に対して公開鍵pkに対応する秘密鍵skを保有していることを証明するために利用される。形式的に、鍵生成アルゴリズムGenは、セキュリティパラメータ1λ(λは0以上の整数)を入力とし、秘密鍵skと公開鍵pkを出力するアルゴリズムとして、下記の式(1)のように表現される。
【0043】
【数1】

…(1)

【0044】
(証明者アルゴリズムP)
証明者アルゴリズムPは、証明者により利用される。そして、証明者アルゴリズムPは、公開鍵pkに対応する秘密鍵skを保有していることを証明するアルゴリズムである。証明者アルゴリズムPは、証明者の秘密鍵skと公開鍵pkを入力とし、検証者との対話プロトコルを実行するアルゴリズムとして定義される。
【0045】
(検証者アルゴリズムV)
検証者アルゴリズムVは、検証者により利用される。そして、検証者アルゴリズムVは、対話プロトコルの中で、公開鍵pkに対応する秘密鍵skを証明者が保有しているか否かを検証するアルゴリズムである。検証者アルゴリズムVは、証明者の公開鍵pkを入力とし、証明者との間で対話プロトコルを実行した後、0又は1(1bit)を出力するアルゴリズムとして定義される。なお、出力0の場合には証明者が不正なものであるとし、出力1の場合には証明者が正当なものであるとする。
【0046】
(補足)
上記の通り、公開鍵認証方式は、安全性を確保するため、健全性と零知識性という2つの条件を満たすことが求められる。しかし、証明者が秘密鍵skを保有していることを証明者に証明させるためには、証明者が秘密鍵skに依存した手続きを実行し、その結果を検証者に通知して、その通知内容に基づく検証を検証者に実行させる必要がある。秘密鍵skに依存した手続きを実行するのは、健全性を担保するために必要である。一方で、この手続きの結果を検証者に通知しても、秘密鍵skの情報が一切検証者に漏れないようにする必要がある。そのため、これらの要件を満たすように、上記の鍵生成アルゴリズムGen、証明者アルゴリズムP、検証者アルゴリズムVが設計される。
【0047】
以上、公開鍵認証方式のアルゴリズム構成について説明した。
【0048】
[1−2:nパスの公開鍵認証方式について]
次に、図2を参照しながら、nパスの公開鍵認証方式について説明する。図2は、nパスの公開鍵認証方式について説明するための説明図である。
【0049】
上記の通り、公開鍵認証方式は、対話プロトコルの中で、証明者が公開鍵pkに対応する秘密鍵skを保有していることを検証者に証明する認証方式である。また、公開鍵認証方式の安全性を担保するため、健全性と零知識性という2つの条件を満たす必要がある。そのため、対話プロトコルの中では、図2に示すように、証明者と検証者の双方がそれぞれ処理を実行しながら、証明者と検証者との間でn回の情報交換が行われる。
【0050】
nパスの公開鍵認証方式の場合、証明者アルゴリズムPを用いて証明者により処理(Step.1)が実行され、情報Tが検証者に送信される。次いで、検証者アルゴリズムVを用いて検証者により処理(Step.2)が実行され、情報Tが証明者に送信される。同様にして処理(Step.3)〜(Step.n)が実行され、情報T,…,Tが送信され、処理(Step.n+1)が実行される。このように、情報がn回送受信される対話プロトコルに基づく公開鍵認証方式のことを「nパス」の公開鍵認証方式と呼ぶ。
【0051】
以上、nパスの公開鍵認証方式について説明した。
【0052】
[1−3:SSH10a公開鍵認証方式の対話プロトコル]
次に、図3を参照しながら、SSH10a公開鍵認証方式の対話プロトコルについて説明する。図3は、SSH10a公開鍵認証方式の対話プロトコルについて説明するための説明図である。なお、SSH10a公開鍵認証方式とは、本件発明者(作本、白井、樋渡)により考案された多次多変数連立方程式の求解問題に基づく公開鍵認証方式の一つである。また、このSSH10a公開鍵認証方式は、3パスの公開鍵認証方式の一例である。
【0053】
なお、多次多変数連立方程式の求解問題とは、環K上のm本のn変数多次多項式f(x,…,x),…,f(x,…,x)と、ベクトルy∈Kが与えられたとき、(f(s,…,s),…,f(s,…,s))=yとなるベクトル(s,…,s)∈Kを求める問題である。2次以上の多変数連立方程式の求解問題は、NP困難問題と呼ばれ、解くことが非常に困難な問題のクラスに属する。
【0054】
さて、SSH10a公開鍵認証方式の対話プロトコルは、鍵生成アルゴリズムGen、証明者アルゴリズムP、検証者アルゴリズムVにより構成される。以下、各アルゴリズムの内容について説明する。
【0055】
(鍵生成アルゴリズムGen)
まず、鍵生成アルゴリズムGenの構成について説明する。鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数2次多項式f(x,…,x),…,f(x,…,x)と、ベクトルs=(s,…,s)∈Kを生成する。次に、鍵生成アルゴリズムGenは、y=(y,…,y)←(f(s),…,f(s))を計算する。そして、鍵生成アルゴリズムGenは、(f,…,f,y)を公開鍵pkに設定し、sを秘密鍵に設定する。なお、以下では、n変数のベクトル(x,…,x)をxと表記し、m本のn変数2次多項式(f(x),…,f(x))をF(x)と表記する。
【0056】
(証明者アルゴリズムP、検証者アルゴリズムV)
次に、図3を参照しながら、証明者アルゴリズムP、検証者アルゴリズムVの構成について説明する。SSH10a公開鍵認証方式の対話プロトコルは、「証明者がy=F(s)を満たすsを知っていること」をsの情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵skは、証明者により秘密に管理されているものとする。
【0057】
ここで、2次多項式の性質について言及しておきたい。
【0058】
m本のn変数2次多項式の組(f(x),…,f(x))は、下記の式(2)のように表現することができる。但し、x=(x,…,x)は、n個の変数を表すベクトルである。また、A,…,Aは、n×n行列である。さらに、b,…,bはn×1ベクトルである。そして、cは、m×1ベクトルである。
【0059】
【数2】

…(2)

【0060】
この表現を用いると、多項式の組Fは、下記の式(3)及び式(4)のように表現することができる。この表現が成り立つことは、下記の式(5)から容易に確認することができる。
【0061】
【数3】

…(3)


…(4)


…(5)

【0062】
このようにF(x+x)をxに依存する部分と、xに依存する部分と、x,xの両方に依存する部分の3つに分けたとき、xとxの両方に依存する部分F(x,x)は、x,xについて双線形写像になる。なお、以下で説明するSSH10a公開鍵認証方式は、上記のような2次多項式の性質を利用したものである。
【0063】
再びSSH10a公開鍵認証方式の対話プロトコル(図3を参照)における証明者アルゴリズムP、検証者アルゴリズムVの説明に戻る。
【0064】
Step.1:
まず、証明者アルゴリズムPは、任意に数wを選択する。次いで、証明者アルゴリズムPは、擬似乱数生成器Gに数wを適用してベクトルr∈Kと数w’を生成する。つまり、証明者アルゴリズムPは、(r,w’)←G(w)を計算する。次いで、証明者アルゴリズムPは、擬似乱数生成器Gに数w’を適用して2つのベクトルt∈K、e∈Kを生成する。つまり、証明者アルゴリズムPは、(t,e)←G(w’)を計算する。次いで、証明者アルゴリズムPは、z←s−rを計算する。この計算は、秘密鍵sをベクトルrによりマスクする操作に相当する。さらに、証明者アルゴリズムPは、t’←r+tを計算する。次いで、証明者アルゴリズムPは、e’←F(r)−c+eを計算する。
【0065】
次いで、証明者アルゴリズムPは、上記の式(3)及び式(4)に示した関数Fの定義に基づいてF(z,t)を算出し、F(z,t)+eとzのハッシュ値cを生成する。つまり、証明者アルゴリズムPは、c←H(F(z,t)+e,z)を計算する。また、証明者アルゴリズムPは、数w’のハッシュ値cを生成する。つまり、証明者アルゴリズムPは、c←H(w’)を計算する。さらに、証明者アルゴリズムPは、2つのベクトルt’とe’のハッシュ値cを生成する。つまり、証明者アルゴリズムPは、c←H(t’,e’)を計算する。
【0066】
次いで、証明者アルゴリズムPは、St←(F,y,s,r,t,e,z,t’,e’)及びCmt←(c,c,c)を設定する。そして、Step.1で生成されたCmtは、検証者(検証者アルゴリズムV)に送られる。なお、上記のH(…)、H(…)、H(…)は、ハッシュ関数である。また、Step.1における上記の操作を(Cmt;St)←Pa,1(F,y,s;r,t,e)と表現することにする。
【0067】
Step.2:
Cmtを受け取った検証者アルゴリズムVは、3つの検証パターンのうち、どの検証パターンを利用するかを選択する。そして、検証者アルゴリズムVは、選択した検証パターンを表すチャレンジCh∈{0,1,2}を証明者(証明者アルゴリズムP)に送る。
【0068】
Step.3:
Chを受け取った証明者アルゴリズムPは、検証者アルゴリズムVから受け取ったチャレンジChに応じて検証者アルゴリズムVへと送り返す回答Rspを生成する。もしCh=0の場合、証明者アルゴリズムPは、回答Rsp←(r,t,e)を生成する。また、Ch=1の場合、証明者アルゴリズムPは、回答Rsp=(z,t,e)を生成する。そして、Ch=2の場合、証明者アルゴリズムPは、回答Rsp=(z,t’,e’)を生成する。なお、Step.3における上記の操作をRsp←Pa,2(Ch;St)と表現することにする。また、Step.3で生成されたRspは、検証者(検証者アルゴリズムV)に送られる。
【0069】
Step.4:
Rspを受け取った検証者アルゴリズムVは、受け取ったRspに対して次のいずれかの検証を実行する。
【0070】
Ch=0の場合、検証者アルゴリズムVは、(r”,t”,e”)←Rspを実行する。次いで、検証者アルゴリズムVは、c=H(t”,e”)及びc=H(r”+t”,F(r”)−c+e”)が成り立つか否かを検証する。
Ch=1の場合、検証者アルゴリズムVは、(z”,t”,e”)←Rspを実行する。次いで、検証者アルゴリズムVは、c=H(F(z”,t”)+e”,z”)及びc=H(t”,e”)が成り立つか否かを検証する。
Ch=2の場合、検証者アルゴリズムVは、(z”,t''',e''')←Rspを実行する。次いで、検証者アルゴリズムVは、c=H(F(z”)+F(z”,t''')+e'''−y,z”)及びc=H(t''',e''')が成り立つか否かを検証する。
【0071】
なお、Step.4における検証の操作を0/1←Dec(F,y;Cmt,Ch,Rsp)と表現することにする。この操作において、出力1は検証の成功を示し、出力0は検証の失敗を示すものとする。
【0072】
以上、SSH10a公開鍵認証方式における証明者アルゴリズムP及び検証者アルゴリズムVの処理内容について説明した。なお、上記の方式ではハッシュ関数H,H,Hを用いてc,c,cを計算しているが、ハッシュ関数H,H,Hの代わりにコミットメント関数COMを用いてもよい。また、本稿を通して、ハッシュ関数を利用している箇所をコミットメント関数COMに置き換えてもよい。
【0073】
コミットメント関数COMは、文字列Sと乱数ρの2つを引数にとる関数である。コミットメント関数の例としては、Shai HaleviとSilvio Micaliによって国際会議CRYPTO1996で発表された方式などがある。コミットメント関数を用いる場合、c,c,cを計算する前に乱数ρ,ρ,ρを用意し、ハッシュ関数H(・),H(・),H(・)を適用する代わりにコミットメント関数COM(・,ρ),COM(・,ρ),COM(・,ρ)を適用してc,c,cを生成する。また、ρは回答に含めて証明者アルゴリズムPから検証者アルゴリズムVへと送られる。
【0074】
[1−4:SSH10b公開鍵認証方式の対話プロトコル]
次に、図4を参照しながら、SSH10b公開鍵認証方式の対話プロトコルについて説明する。図4は、SSH10b公開鍵認証方式の対話プロトコルについて説明するための説明図である。なお、SSH10b公開鍵認証方式とは、本件発明者(作本、白井、樋渡)により考案された多次多変数連立方程式の求解問題に基づく公開鍵認証方式の一つである。また、このSSH10b公開鍵認証方式は、5パスの公開鍵認証方式の一例である。
【0075】
SSH10b公開鍵認証方式の対話プロトコルは、SSH10a公開鍵認証方式の対話プロトコルと同様に、鍵生成アルゴリズムGen、証明者アルゴリズムP、検証者アルゴリズムVにより構成される。以下、各アルゴリズムの内容について説明する。
【0076】
(鍵生成アルゴリズムGen)
まず、鍵生成アルゴリズムGenの構成について説明する。鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数2次多項式f(x,…,x),…,f(x,…,x)と、ベクトルs=(s,…,s)∈Kを生成する。次に、鍵生成アルゴリズムGenは、y=(y,…,y)←(f(s),…,f(s))を計算する。そして、鍵生成アルゴリズムGenは、(f,…,f,y)を公開鍵pkに設定し、sを秘密鍵に設定する。なお、以下では、n変数のベクトル(x,…,x)をxと表記し、m本のn変数2次多項式(f(x),…,f(x))をF(x)と表記する。
【0077】
(証明者アルゴリズムP、検証者アルゴリズムV)
次に、図4を参照しながら、証明者アルゴリズムP、検証者アルゴリズムVの構成について説明する。SSH10b公開鍵認証方式の対話プロトコルは、「証明者がy=F(s)を満たすsを知っていること」をsの情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵skは、証明者により秘密に管理されているものとする。
【0078】
SSH10b公開鍵認証方式の対話プロトコルは、図4に示すStep.1〜Step.6の処理ステップにより構成される。以下、各ステップの処理について説明する。
【0079】
Step.1:
まず、証明者アルゴリズムPは、任意に数wを選択する。次いで、証明者アルゴリズムPは、擬似乱数生成器Gに数wを適用してベクトルr∈K、t∈K、e∈Kを生成する。つまり、証明者アルゴリズムPは、(r,t,e)←G(w)を計算する。次いで、証明者アルゴリズムPは、z←s−rを計算する。この計算は、秘密鍵sをベクトルrによりマスクする操作に相当する。
【0080】
次いで、証明者アルゴリズムPは、F(z,t)+eとzのハッシュ値cを生成する。つまり、証明者アルゴリズムPは、c←H(F(z,t)+e,z)を計算する。また、証明者アルゴリズムPは、ベクトルr、t、eのハッシュ値cを生成する。つまり、証明者アルゴリズムPは、c←H(r,t,e)を計算する。なお、上記のH(…)、H(…)は、ハッシュ関数である。
【0081】
次いで、証明者アルゴリズムPは、St←(F,y,s,r,t,e,z)及びCmt←(c,c)を設定する。そして、Step.1で生成されたCmtは、検証者(検証者アルゴリズムV)に送られる。なお、上記のH(…)、H(…)は、ハッシュ関数である。また、Step.1における上記の操作を(Cmt;St)←Pb,1(F,y,s;r,t,e)と表現することにする。
【0082】
Step.2:
Cmtを受け取った検証者アルゴリズムVは、q通り存在する環Kの元から1つの乱数αを選択する。そして、検証者アルゴリズムVは、チャレンジCh=αを証明者(証明者アルゴリズムP)に送る。
【0083】
Step.3:
Chを受け取った証明者アルゴリズムPは、t’←αr+tを計算する。さらに、証明者アルゴリズムPは、e’←α(F(r)−c)+eを計算する。そして、証明者アルゴリズムPは、St←(St,Ch,t’,e’)及びCmt←(t’,e’)を設定する。また、証明者アルゴリズムPは、Cmtを検証者(検証者アルゴリズムV)に送る。なお、Step.3における上記の操作を(Cmt;St)←Pb,2(Ch;St)と表現することにする。
【0084】
Step.4:
Cmtを受け取った検証者アルゴリズムVは、2つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。そして、検証者アルゴリズムVは、選択した検証パターンを表すチャレンジCh{0,1}を証明者(証明者アルゴリズムP)に送る。
【0085】
Step.5:
Chを受け取った証明者アルゴリズムPは、検証者アルゴリズムVから受けたチャレンジChに応じて検証者(検証者アルゴリズムV)に送り返す回答Rspを次のようにして生成する。Ch=0の場合、証明者アルゴリズムPは、Rsp←rに設定する。Ch=1の場合、証明者アルゴリズムPは、Rsp←zに設定する。そして、証明者アルゴリズムPは、回答Rspを検証者(検証者アルゴリズムV)に送る。なお、Step.5における上記の操作をRsp←Pb,3(Ch;St)と表現することにする。
【0086】
Step.6:
回答Rspを受け取った検証者アルゴリズムVは、証明者(証明者アルゴリズムP)から受け取った回答Rspを利用して以下の検証処理を実行する。
【0087】
Ch=0の場合、検証者アルゴリズムVは、r”←Rspとして、c=H(r”,t’−αr”,e’−α(F(r”)−c))が成り立つか否かを検証する。
Ch=1の場合、検証者アルゴリズムVは、z”←Rspとして、c=H(α(F(z”)−y)+F(z”,t’)+e’,z”)が成り立つか否かを検証する。
【0088】
なお、Step.6における検証の操作を0/1←Dec(F,y;Cmt,Ch,Cmt,Ch,Rsp)と表現することにする。この操作において、出力1は検証の成功を示し、出力0は検証の失敗を示すものとする。
【0089】
以上、SSH10b公開鍵認証方式における証明者アルゴリズムP及び検証者アルゴリズムVの処理内容について説明した。なお、上記の方式ではハッシュ関数H,Hを用いてc,cを計算しているが、ハッシュ関数H,Hの代わりにコミットメント関数COMを用いてもよい。
【0090】
[1−5:対話プロトコルの繰り返し構成]
さて、上記のSSH10a公開鍵認証方式の対話プロトコルを適用すれば、偽証が成功する確率を2/3以下に抑制することができる。従って、この対話プロトコルを2回実行すれば、偽証が成功する確率を(2/3)以下に抑制することができる。同様に、この対話プロトコルをN回実行すると、偽証が成功する確率は(2/3)となり、Nを十分に大きい数(例えば、N=140)にすれば、偽証が成功する確率は無視できる程度に小さくなる。
【0091】
同様に、上記のSSH10b公開鍵認証方式の対話プロトコルを適用すれば、偽証が成功する確率を(1/2+1/2q)以下に抑制することができる。従って、この対話プロトコルを2回実行すれば、偽証が成功する確率を(1/2+1/2q)以下に抑制することができる。同様に、この対話プロトコルをN回実行すると、偽証が成功する確率は(1/2+1/2q)となり、Nを十分に大きい数(例えば、N=80)にすれば、偽証が成功する確率は無視できる程度に小さくなる。
【0092】
なお、SSH10a公開鍵認証方式、SSH10b公開鍵認証方式に限らず、上記の非特許文献1〜3などに開示されている公開鍵認証方式においても同様であるが、対話プロトコルを1回実行した場合の偽証成功確率が十分に小さくない場合、対話プロトコルを繰り返し実行して偽証成功確率を下げる必要がある。対話プロトコルを繰り返し実行する方法としては、図5に示した直列的繰り返し構成と、図6に示した並列的繰り返し構成がある。
【0093】
直列的繰り返し構成は、図5に示すように、対話プロトコルを1回実行し、1回目が終了した後に2回目を、2回目が終了した後に3回目を実行するといった形で、逐次的に対話プロトコルを実行する方法である。一方、並列的繰り返し構成は、図6に示すように、N回分の1パス目のメッセージm1,1,…,mN,1を同時に送信し、次にN回分の2パス目のメッセージm1,2,…,mN,2を同時に送信し、次にN回分の3パス目のメッセージm1,3,…,mN,3を同時に送信するといった形で、各パスにおいてN回分のメッセージを同時送信する方法である。
【0094】
さて、上記の非特許文献1〜3に開示されている公開鍵認証方式、SSH10a公開鍵認証方式、及びSSH10b公開鍵認証方式は、受動的攻撃に対する安全性レベルを保証している。しかし、これらの公開鍵認証方式は、並列的繰り返し構成を行なった場合、能動的攻撃に対する安全性レベルを確実に保証しているか否かが知られていない。これらの公開鍵認証方式は、1組の鍵ペア(公開鍵y、秘密鍵s)を用いて「yについてy=F(s)となるsを知っていること」を証明者が検証者に対して証明する方式であった。
【0095】
そのため、検証で受理される対話を行った場合、「対話を行った証明者がsを用いた」という情報を検証者に知られてしまうことが避けられなかった。また、これらの方式で用いるFは衝突困難性が保証されてない。その結果、これらの公開鍵認証方式は、並列的繰り返し構成を行なった場合、能動的攻撃に対する安全性レベルを確実に保証しているか否かが知られていなかったのである。特に、これらの公開鍵認証方式を上記の並列的繰り返し構成により実施する場合には能動的攻撃に対する安全性レベルを保証するための手立てが知られていなかった。
【0096】
そこで、本件発明者は、これらの公開鍵認証方式を上記の並列的繰り返し構成により実施する際に能動的攻撃に対する安全性レベルが保証されるようにする仕組みを考案した。この仕組み(本手法#1、#2)については、後段において、SSH10a公開鍵認証方式、SSH10b公開鍵認証方式を例に挙げて詳細に説明する。
【0097】
[1−6:SSH10a公開鍵認証方式に対する偽証アルゴリズム]
ここで、図7を参照しながら、SSH10a公開鍵認証方式(1回の対話プロトコル)において2/3の確率で成功する偽証アルゴリズムについて考えてみたい。図7は、SSH10a公開鍵認証方式(1回の対話プロトコル)において2/3の確率で成功する偽証アルゴリズムについて説明するための説明図である。この偽証アルゴリズムは、偽証者が検証者に対して「y=F(s)を満たすsを知っているふり」をするアルゴリズムである。但し、この偽証アルゴリズムを適用しても、1/3の確率で偽証が失敗する。
【0098】
Step.1:
まず、偽証者(偽証アルゴリズム)は、ベクトルs,r,t∈K、e∈Kを生成する。次いで、偽証アルゴリズムは、Ch∈{0,1,2}を任意に選択する。このChは、偽証アルゴリズムが回答できない検証パターンに対応する。なお、ここで用いるsは正当な秘密鍵でない。しかし、証明者(証明者アルゴリズムP)は、Ch以外の検証パターンならば正当な秘密鍵を利用せずに正しく回答することができる。
【0099】
次に、偽証アルゴリズムは、z←s−r、t’←r+tを計算する。また、偽証アルゴリズムは、Ch=0の場合、e’←y−F(s)+F(r)−c+eを計算する。一方、Ch=1,2の場合、偽証アルゴリズムは、e’←F(r)−c+eを計算する。次いで、偽証アルゴリズムは、Ch=0,2の場合、c←H(F(z,t)+e,z)を計算する。一方、Ch=1の場合、偽証アルゴリズムは、c←H(F(z)+F(z,t’)+e’−y,z)を計算する。
【0100】
次いで、偽証アルゴリズムは、c←H(t,e)、c←H(t’,e’)を計算する。そして、偽証アルゴリズムは、St←(Ch,F,y,s,r,t,e,z,t’,e’)及びCmt←(c,c,c)を設定する。次いで、偽証アルゴリズムは、Cmtを検証者(検証者アルゴリズムV)に送る。なお、Step.1における上記の操作を(Cmt;St)←Ma,1(F,y;Ch,s,r,t,e)と表現することにする。
【0101】
Step.2:
Cmtを受け取った検証者アルゴリズムVは、3つの検証パターンのうち、どの検証パターンを利用するかを選択する。そして、検証者アルゴリズムVは、選択した検証パターンを表すチャレンジCh∈{0,1,2}を偽証者(偽証アルゴリズム)に送る。
【0102】
Step.3:
Chを受け取った偽証アルゴリズムは、検証者アルゴリズムVから受け取ったチャレンジChに応じて検証者アルゴリズムVへと送り返す回答Rspを生成する。なお、Ch=Chの場合、偽証アルゴリズムは、エラーを出力して対話プロトコルを終了する。Ch≠ChであってCh=0の場合、偽証アルゴリズムは、回答Rsp←(r,t,e)を生成する。また、Ch=1の場合、偽証アルゴリズムは、回答Rsp=(z,t,e)を生成する。そして、Ch=2の場合、偽証アルゴリズムは、回答Rsp=(z,t’,e’)を生成する。
【0103】
なお、Step.3における上記の操作をRsp←Ma,2(Ch;St)と表現することにする。また、Step.3で生成されたRspは、検証者(検証者アルゴリズムV)に送られる。
【0104】
Step.4:
Ch≠Chの場合、回答Rspが検証者アルゴリズムVに送られるため、検証者アルゴリズムVによって検証処理0/1←Dec(F,y;Cmt,Ch,Rsp)が実施される。
【0105】
以上、SSH10a公開鍵認証方式に対する偽証アルゴリズムについて説明した。このように、sを任意に選択したとしても、2/3の確率(Ch≠Chとなる確率)で検証を通過するRspを検証者に送り返すことができる。従って、1回の対話プロトコルにおいて2/3の確率で偽証が成功してしまう。そこで、先に説明した繰り返し構成が適用される。
【0106】
[1−7:SSH10b公開鍵認証方式に対する偽証アルゴリズム]
次に、図8を参照しながら、SSH10b公開鍵認証方式(1回の対話プロトコル)において1/2の確率で成功する偽証アルゴリズムについて考えてみたい。図8は、SSH10b公開鍵認証方式(1回の対話プロトコル)において1/2の確率で成功する偽証アルゴリズムについて説明するための説明図である。この偽証アルゴリズムは、偽証者が検証者に対して「y=F(s)を満たすsを知っているふり」をするアルゴリズムである。但し、この偽証アルゴリズムを適用しても、1/2の確率で偽証が失敗する。
【0107】
Step.1:
まず、偽証アルゴリズムは、ベクトルs,r,t∈K、e∈Kを生成する。次いで、偽証アルゴリズムは、Ch∈{0,1}を選択する。このChは、iの系列について偽証者(偽証アルゴリズム)が回答できない検証パターンに対応する。なお、ここで用いるsi0は正当な秘密鍵ではないが、偽証アルゴリズムは、Ch以外の検証パターンに対しては正当な秘密鍵を利用せずに正しく回答できる。
【0108】
次いで、偽証アルゴリズムは、z←s−rを計算する。次いで、偽証アルゴリズムは、c←H(F(z,t)+e,z)及びc←H(r,t,e)を計算する。次いで、偽証アルゴリズムは、St←(F,y,Ch,s,r,t,e,z)及びCmt←(c,c)を設定する。そして、Step.1で生成されたCmtは、検証者(検証者アルゴリズムV)に送られる。なお、上記のH(…)、H(…)は、ハッシュ関数である。また、Step.1における上記の操作を(Cmt;St)←Mb,1(F,y;Ch,s,r,t,e)と表現することにする。
【0109】
Step.2:
Cmtを受け取った検証者アルゴリズムVは、q通り存在する環Kの元から1つの乱数αを選択する。そして、検証者アルゴリズムVは、チャレンジCh=αを偽証者(偽証アルゴリズム)に送る。
【0110】
Step.3:
Chを受け取った偽証アルゴリズムは、t’←αr+tを計算する。さらに、偽証アルゴリズムは、Ch=1の場合、e’←α(F(r)−c)+eを計算する。一方、Ch=0の場合、偽証アルゴリズムは、e’←α(y−F(s)+F(r)−c)+eを計算する。そして、偽証アルゴリズムは、St←(St,Ch,t’,e’)及びCmt←(t’,e’)を設定する。また、偽証アルゴリズムは、Cmtを検証者(検証者アルゴリズムV)に送る。なお、Step.3における上記の操作を(Cmt;St)←Mb,2(Ch;St)と表現することにする。
【0111】
Step.4:
Cmtを受け取った検証者アルゴリズムVは、2つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。そして、検証者アルゴリズムVは、選択した検証パターンを表すチャレンジCh{0,1}を偽証者(偽証アルゴリズム)に送る。
【0112】
Step.5:
Chを受け取った偽証アルゴリズムは、Ch=Chの場合、エラーを出力して対話プロトコルを終了する。Ch≠Chの場合、偽証アルゴリズムは、検証者アルゴリズムVから受けたチャレンジChに応じて検証者(検証者アルゴリズムV)に送り返す回答Rspを次のようにして生成する。
【0113】
Ch=0の場合、偽証アルゴリズムは、Rsp←rに設定する。Ch=1の場合、偽証アルゴリズムは、Rsp←zに設定する。そして、偽証アルゴリズムは、回答Rspを検証者(検証者アルゴリズムV)に送る。なお、Step.5における上記の操作をRsp←Mb,3(Ch;St)と表現することにする。
【0114】
Step.6:
Ch≠Chの場合、回答Rspが検証者アルゴリズムVに送られるため、検証者アルゴリズムVによって検証処理0/1←Dec(F,y;Cmt,Ch,Cmt,Ch,Rsp)が実施される。
【0115】
以上、SSH10b公開鍵認証方式に対する偽証アルゴリズムについて説明した。このように、sを任意に選択したとしても、1/2の確率(Ch≠Chとなる確率)で検証を通過するRspを検証者に送り返すことができる。従って、1回の対話プロトコルにおいて1/2の確率で偽証が成功してしまう。そこで、先に説明した繰り返し構成が適用される。
【0116】
(補足)
ここまで、SSH10a公開鍵認証方式、SSH10b公開鍵認証方式、その偽証アルゴリズム、及び対話プロトコルの繰り返し構成について説明してきた。これらの公開鍵認証方式は、1組の鍵ペア(公開鍵y、秘密鍵s)を用いて「yについてy=F(s)となるsを知っていること」を証明者が検証者に対して証明する方式である。そのため、検証で受理される対話を行った場合、「検証を行った証明者がsを用いた」という情報を検証者に知られてしまうことが避けられなかった。また、これらの方式で用いるFは衝突困難性が保証されていない。その結果、これらの公開鍵認証方式は、並列的繰り返し構成を行なった場合、能動的攻撃に対する安全性レベルを確実に保証しているか否かが知られていなかった。
【0117】
そこで、本件発明者は、これらの公開鍵認証方式を上記の並列的繰り返し構成により実施する際に能動的攻撃に対する安全性レベルが保証されるようにする仕組みを考案した。以下、この仕組みについて、具体例を挙げて詳細に説明する。
【0118】
<2:第1実施形態(本手法#1)>
まず、本発明の第1実施形態(以下、本手法#1)について説明する。
【0119】
[2−1:概要]
本手法#1は、SSH10a公開鍵認証方式、SSH10b公開鍵認証方式に対し、並列的繰り返し構成を行なった場合にも能動的攻撃に対する安全性レベルが保証されるようにする仕組みを適用したものである。繰り返しになるが、能動的攻撃に対する安全性レベルが保証されているか否かが知られていなかった理由は、利用する関数Fの衝突困難性が保証されない上、「検証を行った証明者がsを用いた」という情報を検証者に知られてしまうことが避けられなかったからである。従って、対話プロトコルの中で「検証を行った証明者がsを用いた」という情報を検証者に知られないようにすれば、能動的攻撃に対する安全性レベルを保証することができる。
【0120】
そこで、本件発明者は、秘密鍵s、公開鍵yを多重化する方式を考案した。この方式は、L個(L≧2)のs,…,s∈Kを秘密鍵とし、m本のn変数多次多項式F(x)=(f(x),…,f(x))に対して(y,…,y)=(F(s),…,F(s))を満たすy,…,y∈Kを公開鍵とする。さらに、この方式は、「i=1,…,Lのうち、L−1個のiについてy=F(s)となるsを知っていること」を、どのsを対話プロトコルの中で使用したかが分からないように証明する方式である。この方式を適用すると、対話プロトコルの中で「どのsを利用したか」に関する情報が漏れないため、能動的攻撃に対する安全性レベルが保証されるのである。
【0121】
本手法#1の方式は、検証者がi=1,…,LについてチャレンジCh,…,Ch(検証パターン)を証明者に対して送信し、チャレンジCh,…,Chを受け取った証明者がL−1個のチャレンジChを選択して回答するというものである。この方式を用いると、s,…,sを知っている証明者はL個全てのチャレンジChについて回答できるが、s,…,sを知らない偽証者は、ある程度の確率で偽証が失敗する。また、証明者はL−1個のチャレンジChに対して回答すればよいため、ある1つのチャレンジChについてはsを使用せずに認証を成立させることができる。つまり、対話プロトコルの中で、あるsを使用したか否かが検証者には分からないのである。
【0122】
[2−2:SSH10a公開鍵認証方式への適用]
まず、図9を参照しながら、本手法#1の方式をSSH10a公開鍵認証方式に適用した場合の対話プロトコルについて説明する。図9は、本手法#1の方式をSSH10a公開鍵認証方式に適用した場合の対話プロトコルについて説明するための説明図である。この対話プロトコルは、鍵生成アルゴリズムGen、証明者アルゴリズムP、検証者アルゴリズムVにより構成される。以下、各アルゴリズムの内容について説明する。
【0123】
(鍵生成アルゴリズムGen)
まず、鍵生成アルゴリズムGenの構成について説明する。鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数2次多項式f(x,…,x),…,f(x,…,x)と、L個のベクトルs,…,s∈Kを生成する。なお、n変数のベクトル(x,…,x)をxと表記し、m本のn変数2次多項式(f(x),…,f(x))をF(x)と表記する。次に、鍵生成アルゴリズムGenは、y=F(s),…,y=F(s)を計算する。そして、鍵生成アルゴリズムGenは、(F,y,…,y)を公開鍵pkに設定し、(s,…,s)を秘密鍵に設定する。
【0124】
(証明者アルゴリズムP、検証者アルゴリズムV)
次に、図9を参照しながら、証明者アルゴリズムP、検証者アルゴリズムVの構成について説明する。本手法#1の対話プロトコルは、「証明者がL−1個のy=F(s)を満たすsを知っていること」を、「どのsを使用したか否か」という情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵skは、証明者により秘密に管理されているものとする。
【0125】
本手法#1の対話プロトコルは、図9に示すStep.1〜Step.4の処理ステップにより構成される。以下、各ステップの処理について説明する。
【0126】
Step.1:
まず、証明者アルゴリズムPは、i=1,…,Lについて、ベクトルr,t∈Kと、ベクトルe∈Kを生成する。次いで、証明者アルゴリズムPは、(Cmt;St)←Pa,1(F,y,s;r,t,e)を計算する。そして、証明者アルゴリズムPは、Cmt,…,Cmtを検証者(検証者アルゴリズムV)に送る。
【0127】
Step.2:
Cmt,…,Cmtを受け取った検証者アルゴリズムVは、3つの検証パターンのうち、どの検証パターンを利用するかを選択する。そして、検証者アルゴリズムVは、選択した検証パターンを表すチャレンジCh,…,Ch{0,1,2}を証明者(証明者アルゴリズムP)に送る。
【0128】
Step.3:
Ch,…,Chを受け取った証明者アルゴリズムPは、i=1,…,Lから1個だけ回答しないチャレンジChのインデックスi(以下、i)をランダムに選択する。次いで、証明者アルゴリズムPは、i∈{1,…,L}\{i}についてRsp←Pa,2(Ch;St)を計算する。そして、証明者アルゴリズムPは、(Rsp,…,Rspi*−1,Rspi*+1,…,Rsp,i)を検証者(検証者アルゴリズムV)に送る。
【0129】
Step.4:
(Rsp,…,Rspi*−1,Rspi*+1,…,Rsp,i)を受け取った検証者アルゴリズムVは、i∈{1,…,L}\{i}について0/1←Dec(F,y;Cmt,Ch,Rsp)を実行する。そして、検証者アルゴリズムVは、i∈{1,…,L}\{i}について全て受理(出力1)されれば検証が成立したものとみなす。
【0130】
以上、本手法#1の方式をSSH10a公開鍵認証方式に適用した場合の対話プロトコルについて説明した。この対話プロトコルは、SSH10a公開鍵認証方式の安全性により、sを持たない偽証者がi=1,…,Lについて、それぞれ2/3以下の確率でしか、検証者から送られたチャレンジChに正しく回答できないことが保証されている。また、本手法#1を適用したことにより、L−1個以上のiについて検証者から送られたチャレンジChに正しく回答する必要があるため、偽証が成功する確率は、(2/3)+L(1/3)(2/3)L−1=(2+L)2L−1/3である。
【0131】
また、上記の対話プロトコルにおいてはs,…,sの全てを使用しているが、L≦3の場合であれば、i=1,…,Lの1つについてsを使用しなくても、どのsを使用しなかったかを検証者に一切知られずに全く証明者と同様の振る舞いをすることが可能である。そこで、1つのsを使用せずに、上記の対話プロトコルと同じ認証が実現可能な対話プロトコル(変形例1〜3)について説明する。
【0132】
[2−3:SSH10a公開鍵認証方式への適用(変形例1)]
まず、図10を参照しながら、本手法#1の方式をSSH10a公開鍵認証方式に適用した場合の対話プロトコル(変形例1)について説明する。図10は、本手法#1の方式をSSH10a公開鍵認証方式に適用した場合の対話プロトコル(変形例1)について説明するための説明図である。この対話プロトコルは、鍵生成アルゴリズムGen、証明者アルゴリズムP、検証者アルゴリズムVにより構成される。但し、検証者アルゴリズムVにおいて、先に説明した偽証アルゴリズムの構成が利用される。また、L=3の場合について説明する。さらに、使用しないsのインデックスをiとする。以下、各アルゴリズムの内容について説明する。
【0133】
(鍵生成アルゴリズムGen)
まず、鍵生成アルゴリズムGenの構成について説明する。鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数2次多項式f(x,…,x),…,f(x,…,x)と、L個のベクトルs,…,s∈Kを生成する。但し、si0は、適当に選択したベクトルを用いる。なお、n変数のベクトル(x,…,x)をxと表記し、m本のn変数2次多項式(f(x),…,f(x))をF(x)と表記する。次に、鍵生成アルゴリズムGenは、y=F(s),…,y=F(s)を計算する。但し、yi0=F(si0)になることは保証されていなくてもよい。そして、鍵生成アルゴリズムGenは、(F,y,…,y)を公開鍵pkに設定し、(s,…,s)を秘密鍵に設定する。
【0134】
(証明者アルゴリズムP、検証者アルゴリズムV)
次に、図10を参照しながら、証明者アルゴリズムP、検証者アルゴリズムVの構成について説明する。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵skは、証明者により秘密に管理されているものとする。
【0135】
本手法#1の対話プロトコルは、図10に示すStep.1〜Step.4の処理ステップにより構成される。以下、各ステップの処理について説明する。
【0136】
Step.1:
まず、証明者アルゴリズムPは、i=1,2,3について、ベクトルr,t∈Kと、ベクトルe∈Kを生成する。次いで、証明者アルゴリズムPは、Ch∈{0,1,2}を1つ選択する。このChは、iの系列について証明者が回答できない検証パターンに対応する。次いで、証明者アルゴリズムPは、i≠iの場合、(Cmt;St)←Pa,1(F,y,s;r,t,e)を計算する。一方、i=iの場合、証明者アルゴリズムPは、(Cmt;St)←Ma,1(F,y;Ch,s,r,t,e)を計算する。そして、証明者アルゴリズムPは、Cmt,Cmt,Cmtを検証者(検証者アルゴリズムV)に送る。
【0137】
Step.2:
Cmt,Cmt,Cmtを受け取った検証者アルゴリズムVは、3つの検証パターンのうち、どの検証パターンを利用するかを選択する。そして、検証者アルゴリズムVは、選択した検証パターンを表すチャレンジCh,Ch,Ch{0,1,2}を証明者(証明者アルゴリズムP)に送る。
【0138】
Step.3:
Ch,Ch,Chを受け取った証明者アルゴリズムPは、i=1,…,Lから1個だけ回答しないチャレンジChのインデックスi(以下、i)を次のようにして選択する。Chi0=Chの場合、検証者アルゴリズムVは、i←iを設定する。一方、Chi0≠Chの場合、検証者アルゴリズムVは、i∈{1,2,3}\{i}からランダムにiを選択する。このiの設定方法を用いると、検証者がどのような検証パターンを要求してきてもiは、それぞれ1/3の確率で1,2,3の値をとる。つまり、iが1,2,3のどの値であったかという情報が完全に秘匿されているのである。
【0139】
次いで、証明者アルゴリズムPは、i∈{1,2,3}\{i}について次のようにRspを計算する。i≠iの場合、証明者アルゴリズムPは、Rsp←Pa,2(Ch;St)を計算する。i=iの場合、証明者アルゴリズムPは、Rsp←Ma,2(Ch;St)を計算する。そして、証明者アルゴリズムPは、(Rsp,…,Rspi*−1,Rspi*+1,…,Rsp,i)を検証者(検証者アルゴリズムV)に送る。
【0140】
Step.4:
(Rsp,…,Rspi*−1,Rspi*+1,…,Rsp,i)を受け取った検証者アルゴリズムVは、i∈{1,2,3}\{i}について0/1←Dec(F,y;Cmt,Ch,Rsp)を実行する。そして、検証者アルゴリズムVは、i∈{1,2,3}\{i}について全て受理(出力1)されれば検証が成立したものとみなす。
【0141】
以上、本手法#1の方式をSSH10a公開鍵認証方式に適用した場合の対話プロトコル(変形例)について説明した。ここではL=3の場合について説明したが、L=2の場合についても同様である。例えば、次のようにしてi=1,2から1個だけ利用しないi(i)を設定する。Chi0=Chならばi=iに設定する。一方、Chi0≠Chならば1/4の確率でi=iに設定し、3/4の確率でi≠iに設定する。このように設定すると、検証者がどのような検証パターンを要求してきても、iはそれぞれ1/2の確率で1,2の値をとる。そのため、iが1,2のどの値であったかという情報が完全に秘匿される。
【0142】
[2−4:SSH10a公開鍵認証方式への適用(変形例2)]
次に、図11を参照しながら、本手法#1の方式をSSH10a公開鍵認証方式に適用した場合の対話プロトコル(変形例2)について説明する。なお、変形例2は、図9に示した対話プロトコルの一変形例である。図11は、本手法#1の方式をSSH10a公開鍵認証方式に適用した場合の対話プロトコル(変形例2)について説明するための説明図である。この対話プロトコルは、鍵生成アルゴリズムGen、証明者アルゴリズムP、検証者アルゴリズムVにより構成される。以下、各アルゴリズムの内容について説明する。
【0143】
(鍵生成アルゴリズムGen)
まず、鍵生成アルゴリズムGenの構成について説明する。鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数2次多項式f(x,…,x),…,f(x,…,x)と、2個のベクトルs,s∈Kを生成する。なお、n変数のベクトル(x,…,x)をxと表記し、m本のn変数2次多項式(f(x),…,f(x))をF(x)と表記する。次に、鍵生成アルゴリズムGenは、y=F(s),y=F(s)を計算する。そして、鍵生成アルゴリズムGenは、(F,y,y)を公開鍵pkに設定し、(s,s)を秘密鍵に設定する。
【0144】
(証明者アルゴリズムP、検証者アルゴリズムV)
次に、図11を参照しながら、証明者アルゴリズムP、検証者アルゴリズムVの構成について説明する。本手法#1の対話プロトコルは、「証明者が1個のy=F(s)を満たすsを知っていること」を、「どのsを使用したか否か」という情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵skは、証明者により秘密に管理されているものとする。
【0145】
本手法#1の対話プロトコルは、図11に示すStep.1〜Step.4の処理ステップにより構成される。以下、各ステップの処理について説明する。
【0146】
Step.1:
まず、証明者アルゴリズムPは、ベクトルr,t∈Kと、ベクトルe∈Kを生成する。次いで、証明者アルゴリズムPは、(Cmt;St)←Pa,1(F,y,s;r,t,e)、(Cmt;St)←Pa,1(F,y,s;r,t,e)を計算する。但し、Cmt=(c11,c12,c13)、Cmt=(c21,c12,c13)となる。次いで、証明者アルゴリズムPは、c11,c12,c13,c21を検証者(検証者アルゴリズムV)に送る。
【0147】
Step.2:
11,c12,c13,c21を受け取った検証者アルゴリズムVは、どの検証パターンを利用するかを選択する。そして、検証者アルゴリズムVは、選択した検証パターンを表すチャレンジの組(Ch,Ch)∈{0,1,2}×{0,1,2}を証明者(証明者アルゴリズムP)に送る。
【0148】
Step.3:
Ch,Chを受け取った証明者アルゴリズムPは、回答するチャレンジChのインデックスiをランダムに選択する。次いで、証明者アルゴリズムPは、選択したiについて、Rsp←Pa,2(Ch;St,r,t,e)を計算する。そして、証明者アルゴリズムPは、(Rsp,i)を検証者(検証者アルゴリズムV)に送る。
【0149】
Step.4:
Rsp,iを受け取った検証者アルゴリズムVは、0/1←Dec(F,y;(ci1,c12,c13,),Ch,Rsp)を実行する。そして、検証者アルゴリズムVは、出力が1の場合(受理された場合)に検証が成立したものとみなす。
【0150】
以上、本手法#1の方式をSSH10a公開鍵認証方式に適用した場合の対話プロトコル(変形例2)について説明した。本変形例は、Cmt、St、Cmt、Stを生成する際に用いる乱数の組(r、t、e)と(r、t、e)を共通化する点に特徴がある。これらの乱数を共通化することにより、Cmt=(c11,c12,c13)、Cmt=(c21,c22,c23)を構成する要素のうち、(c12,c13)と(c22,c23)が共通の値となる。そのため、証明者から検証者にCmtとCmtを送る際に、4個の値(c11,c12,c13,c21)だけを送れば済むようになり、通信量を低減させることが可能になる。なお、本変形例の場合、3パス目において一方の系列に関する情報しか公開しないため、上記のように乱数の一部を共通化しても零知識性は損なわれない。
【0151】
[2−5:SSH10a公開鍵認証方式への適用(変形例3)]
次に、図12を参照しながら、本手法#1の方式をSSH10a公開鍵認証方式に適用した場合の対話プロトコル(変形例3)について説明する。なお、変形例3は、図11に示した対話プロトコル(変形例2)の一変形例である。図12は、本手法#1の方式をSSH10a公開鍵認証方式に適用した場合の対話プロトコル(変形例3)について説明するための説明図である。この対話プロトコルは、鍵生成アルゴリズムGen、証明者アルゴリズムP、検証者アルゴリズムVにより構成される。以下、各アルゴリズムの内容について説明する。
【0152】
(鍵生成アルゴリズムGen)
まず、鍵生成アルゴリズムGenの構成について説明する。鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数2次多項式f(x,…,x),…,f(x,…,x)と、2個のベクトルs,s∈Kを生成する。なお、n変数のベクトル(x,…,x)をxと表記し、m本のn変数2次多項式(f(x),…,f(x))をF(x)と表記する。次に、鍵生成アルゴリズムGenは、y=F(s),y=F(s)を計算する。そして、鍵生成アルゴリズムGenは、(F,y,y)を公開鍵pkに設定し、(s,s)を秘密鍵に設定する。
【0153】
(証明者アルゴリズムP、検証者アルゴリズムV)
次に、図12を参照しながら、証明者アルゴリズムP、検証者アルゴリズムVの構成について説明する。本手法#1の対話プロトコルは、「証明者が1個のy=F(s)を満たすsを知っていること」を、「どのsを使用したか否か」という情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵skは、証明者により秘密に管理されているものとする。
【0154】
本手法#1の対話プロトコルは、図12に示すStep.1〜Step.4の処理ステップにより構成される。以下、各ステップの処理について説明する。
【0155】
Step.1:
まず、証明者アルゴリズムPは、ベクトルr,t∈Kと、ベクトルe∈Kを生成する。次いで、証明者アルゴリズムPは、(Cmt;St)←Pa,1(F,y,s;r,t,e)、(Cmt;St)←Pa,1(F,y,s;r,t,e)を計算する。但し、Cmt=(c11,c12,c13)、Cmt=(c21,c12,c13)となる。次いで、証明者アルゴリズムPは、c11,c12,c13,c21を検証者(検証者アルゴリズムV)に送る。
【0156】
Step.2:
11,c12,c13,c21を受け取った検証者アルゴリズムVは、どの検証パターンを利用するかを選択する。このとき、検証者アルゴリズムVは、検証パターン(チャレンジの組(Ch,Ch))を(Ch,Ch)∈{(0,0),(1,1),(1,2),(2,1),(2,2)}の中から選択する。そして、検証者アルゴリズムVは、選択した検証パターンを表すチャレンジの組(Ch,Ch)を証明者(証明者アルゴリズムP)に送る。
【0157】
Step.3:
Ch,Chを受け取った証明者アルゴリズムPは、回答するチャレンジChのインデックスiをランダムに選択する。次いで、証明者アルゴリズムPは、選択したiについて、Rsp←Pa,2(Ch;St,r,t,e)を計算する。そして、証明者アルゴリズムPは、(Rsp,i)を検証者(検証者アルゴリズムV)に送る。
【0158】
Step.4:
(Rsp,i)を受け取った検証者アルゴリズムVは、0/1←Dec(F,y;(ci1,c12,c13,),Ch,Rsp)を実行する。そして、検証者アルゴリズムVは、出力が1の場合(受理された場合)に検証が成立したものとみなす。
【0159】
以上、本手法#1の方式をSSH10a公開鍵認証方式に適用した場合の対話プロトコル(変形例3)について説明した。本変形例は、利用可能な検証パターンを(Ch,Ch)∈{(0,0),(1,1),(1,2),(2,1),(2,2)}の5パターンに限定する点に特徴がある。
【0160】
上記のように、Cmtの要素(c12,c13)とCmtの要素(c22,c23)が共通化されている場合、Ch=0に対する回答(c12,c13に対する回答)とCh=0に対する回答(c22,c23に対する回答)は共通になる。そのため、「(Ch,Ch)=(0,0)に回答できること」は、「Ch=0とCh=0の両方に回答できること」を意味する。つまり、(Ch,Ch)=(0,0)に回答できる証明者は、(Ch,Ch)=(0,1),(0,2),(1,0),(2,0)のいずれにも回答できることになる。従って、検証者は、(Ch,Ch)=(0,0),(1,1),(1,2),(2,1),(2,2)の5パターンについて検証を行えば十分である。
【0161】
このような理由から、秘密鍵skを知らない限り、上記の5パターンの全てに回答することはできないことが保証される。つまり、秘密鍵skを知らない者は最大で4パターンにしか回答できないことになるため、偽証確率は最大で4/5になる。図9に示した対話プロトコルの場合、L=2における偽証確率は8/9であった。従って、変形例3の構成を適用することにより、偽証確率が低減する。
【0162】
[2−6:SSH10b公開鍵認証方式への適用]
次に、図13を参照しながら、本手法#1の方式をSSH10b公開鍵認証方式に適用した場合の対話プロトコルについて説明する。図13は、本手法#1の方式をSSH10b公開鍵認証方式に適用した場合の対話プロトコルについて説明するための説明図である。この対話プロトコルは、鍵生成アルゴリズムGen、証明者アルゴリズムP、検証者アルゴリズムVにより構成される。以下、各アルゴリズムの内容について説明する。
【0163】
(鍵生成アルゴリズムGen)
まず、鍵生成アルゴリズムGenの構成について説明する。鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数2次多項式f(x,…,x),…,f(x,…,x)と、L個のベクトルs,…,s∈Kを生成する。なお、n変数のベクトル(x,…,x)をxと表記し、m本のn変数2次多項式(f(x),…,f(x))をF(x)と表記する。次に、鍵生成アルゴリズムGenは、y=F(s),…,y=F(s)を計算する。そして、鍵生成アルゴリズムGenは、(F,y,…,y)を公開鍵pkに設定し、(s,…,s)を秘密鍵に設定する。
【0164】
(証明者アルゴリズムP、検証者アルゴリズムV)
次に、図13を参照しながら、証明者アルゴリズムP、検証者アルゴリズムVの構成について説明する。本手法#1の対話プロトコルは、「証明者がL−1個のy=F(s)を満たすsを知っていること」を、「どのsを使用したか否か」という情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵skは、証明者により秘密に管理されているものとする。
【0165】
本手法#1の対話プロトコルは、図13に示すStep.1〜Step.6の処理ステップにより構成される。以下、各ステップの処理について説明する。
【0166】
Step.1:
まず、証明者アルゴリズムPは、i=1,…,Lについて、ベクトルr,t∈Kと、ベクトルe∈Kを生成する。次いで、証明者アルゴリズムPは、(CmtA,i;StA,i)←Pa,1(F,y,s;r,t,e)を計算する。そして、証明者アルゴリズムPは、(CmtA,1,…,CmtA,L)を検証者(検証者アルゴリズムV)に送る。
【0167】
Step.2:
(CmtA,1,…,CmtA,L)を受け取った検証者アルゴリズムVは、q通り存在する環Kの元からL個の乱数の組(α,…,α)を選択する。そして、検証者アルゴリズムVは、チャレンジ(ChA,1,…,ChA,L)=(α,…,α)を証明者(証明者アルゴリズムP)に送る。
【0168】
Step.3:
(ChA,1,…,ChA,L)を受け取った証明者アルゴリズムPは、i=1,…,Lについて(CmtB,i;StB,i)←Pb,2(ChA,i;StA,i)を計算する。そして、証明者アルゴリズムPは、(CmtB,1,…,CmtB,L)を検証者(検証者アルゴリズムV)に送る。
【0169】
Step.4:
(CmtB,1,…,CmtB,L)を受け取った検証者アルゴリズムVは、2つの検証パターンのうち、どちらの検証パターンを利用するかをi=1,…,Lのそれぞれについて選択する。そして、検証者アルゴリズムVは、選択した検証パターンを表すチャレンジChB,1,…,ChB,L{0,1}を証明者(証明者アルゴリズムP)に送る。
【0170】
Step.5:
ChB,1,…,ChB,Lを受け取った証明者アルゴリズムPは、i=1,…,Lから1個だけ回答しないi(以下、i)をランダムに選択する。そして、証明者アルゴリズムPは、Rsp←Pb,3(ChB,i;StB,i)を計算する。そして、証明者アルゴリズムPは、(Rsp,…,Rspi*−1,Rspi*+1,…,Rsp,i)を検証者(検証者アルゴリズムV)に送る。
【0171】
Step.6:
(Rsp,…,Rspi*−1,Rspi*+1,…,Rsp,i)を受け取った検証者アルゴリズムVは、i∈{1,…,L}\{i}について0/1←Dec(F,y;CmtA,i,ChA,i,CmtB,i,ChB,i,Rsp)を実施する。そして、検証者アルゴリズムVは、i∈{1,…,L}\{i}について全て受理(出力1)されれば検証が成立したものとみなす。
【0172】
以上、本手法#1の方式をSSH10b公開鍵認証方式に適用した場合の対話プロトコルについて説明した。この対話プロトコルは、SSH10b公開鍵認証方式の安全性により、sを持たない偽証者がi=1,…,Lについて、それぞれ1/2+1/2q以下の確率でしか、検証者から送られたチャレンジChに正しく回答できないことが保証されている。また、本手法#1を適用したことにより、L−1個以上のiについて検証者から送られたチャレンジChに正しく回答する必要があるため、偽証が成功する確率は、(1/2+1/2q)+L(1/2−1/2q)(1/2+1/2q)L−1である。
【0173】
また、上記の対話プロトコルにおいてはs,…,sの全てを使用しているが、L=2の場合であれば、i=1,…,Lの1つについてsを使用しなくても、どのsを使用しなかったかを検証者に一切知られずに全く証明者と同様の振る舞いをすることが可能である。そこで、1つのsを使用せずに、上記の対話プロトコルと同じ認証が実現可能な対話プロトコル(変形例)について説明する。
【0174】
[2−7:SSH10b公開鍵認証方式への適用(変形例)]
以下、図14を参照しながら、本手法#1の方式をSSH10b公開鍵認証方式に適用した場合の対話プロトコル(変形例)について説明する。図14は、本手法#1の方式をSSH10b公開鍵認証方式に適用した場合の対話プロトコル(変形例)について説明するための説明図である。この対話プロトコルは、鍵生成アルゴリズムGen、証明者アルゴリズムP、検証者アルゴリズムVにより構成される。但し、検証者アルゴリズムVにおいて、先に説明した偽証アルゴリズムの構成が利用される。また、L=2の場合について説明する。さらに、使用しないsのインデックスをiとする。以下、各アルゴリズムの内容について説明する。
【0175】
(鍵生成アルゴリズムGen)
まず、鍵生成アルゴリズムGenの構成について説明する。鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数2次多項式f(x,…,x),…,f(x,…,x)と、L個のベクトルs,…,s∈Kを生成する。但し、si0は、適当に選択したベクトルを用いる。なお、n変数のベクトル(x,…,x)をxと表記し、m本のn変数2次多項式(f(x),…,f(x))をF(x)と表記する。次に、鍵生成アルゴリズムGenは、y=F(s),…,y=F(s)を計算する。但し、yi0=F(si0)になることは保証されていなくてもよい。そして、鍵生成アルゴリズムGenは、(F,y,…,y)を公開鍵pkに設定し、(s,…,s)を秘密鍵に設定する。
【0176】
(証明者アルゴリズムP、検証者アルゴリズムV)
次に、図14を参照しながら、証明者アルゴリズムP、検証者アルゴリズムVの構成について説明する。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵skは、証明者により秘密に管理されているものとする。
【0177】
本手法#1の対話プロトコルは、図14に示すStep.1〜Step.6の処理ステップにより構成される。以下、各ステップの処理について説明する。
【0178】
Step.1:
まず、証明者アルゴリズムPは、i=1,2について、ベクトルr,t∈Kと、ベクトルe∈Kを生成する。次いで、証明者アルゴリズムPは、Ch∈{0,1}を1つ選択する。このChは、iの系列について証明者が回答できない検証パターンに対応する。次いで、証明者アルゴリズムPは、i≠iの場合について、(CmtA,i;StA,i)←Pb,1(F,y,s;r,t,e)を計算する。また、i=iの場合について、証明者アルゴリズムPは、(CmtA,i;StA,i)←Mb,1(F,y;Ch,s,r,t,e)を計算する。そして、証明者アルゴリズムPは、(CmtA,1,CmtA,2)を検証者(検証者アルゴリズムV)に送る。
【0179】
Step.2:
(CmtA,1,CmtA,2)を受け取った検証者アルゴリズムVは、q通り存在する環Kの元から2つの乱数の組(α,α)を選択する。そして、検証者アルゴリズムVは、チャレンジ(ChA,1,ChA,2)=(α,α)を証明者(証明者アルゴリズムP)に送る。
【0180】
Step.3:
(ChA,1,ChA,2)を受け取った証明者アルゴリズムPは、i=1,2について次のようにCmtB,iを計算する。i≠iの場合、証明者アルゴリズムPは、(CmtB,i;StB,i)←Pb,2(ChA,i;StA,i)を計算する。一方、i=iの場合、証明者アルゴリズムPは、(CmtB,i;StB,i)←Mb,2(ChA,i;StA,i)を計算する。そして、証明者アルゴリズムPは、(CmtB,1,CmtB,2)を検証者(検証者アルゴリズムV)に送る。
【0181】
Step.4:
(CmtB,1,CmtB,2)を受け取った検証者アルゴリズムVは、2つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。そして、検証者アルゴリズムVは、選択した検証パターンを表すチャレンジ(ChB,1,ChB,2)∈{0,1}を証明者(証明者アルゴリズムP)に送る。
【0182】
Step.5:
(ChB,1,ChB,2)を受け取った証明者アルゴリズムPは、i=1,2から1個だけ回答しないi(以下、i)を次のようにして選択する。Chi0=Chの場合、証明者アルゴリズムPは、Chi0≠Chに設定する。一方、i≠iの場合、証明者アルゴリズムPは、i≠iとなるようにランダムに設定する。このiの設定方法を用いると、検証者がどのような検証パターンを要求してきてもiは、それぞれ1/2の確率で1,2の値をとる。つまり、iが1,2のどの値であったかという情報が完全に秘匿されているのである。
【0183】
次いで、証明者アルゴリズムPは、i∈{1,2}\{i}について次のようにRspを計算する。i≠iの場合、証明者アルゴリズムPは、Rsp←Pb,3(Ch;St)を計算する。i=iの場合、証明者アルゴリズムPは、Rsp←Mb,3(Ch;St)を計算する。そして、証明者アルゴリズムPは、(Rsp,Rsp,i)を検証者(検証者アルゴリズムV)に送る。
【0184】
Step.6:
(Rsp,Rsp,i)を受け取った検証者アルゴリズムVは、i∈{1,2}\{i}について0/1←Dec(F,y;CmtA,i,ChA,i,CmtB,i,ChB,i,Rsp)を実行する。そして、検証者アルゴリズムVは、i∈{1,2}\{i}について全て受理(出力1)されれば検証が成立したものとみなす。
【0185】
以上、本手法#1の方式をSSH10b公開鍵認証方式に適用した場合の対話プロトコル(変形例)について説明した。ここではL=2の場合について説明したが、L≧3の場合についても同じ仕組みを実現することは可能である。
【0186】
以上、本発明の第1実施形態について説明した。上記説明においては、SSH10a公開鍵認証方式、SSH10b公開鍵認証方式を例に挙げて述べたが、本手法#1の適用範囲はこれに限定されない。SSH10a公開鍵認証方式やSSH10b公開鍵認証方式の変形例、及びその他の公開鍵認証方式に対しても適用が可能である。例えば、上記の例では公開鍵を(F,y)に設定しているが、Fが秘密鍵によらないパラメータであるため、このFを証明者毎に設定するのではなく、システム全体に共通するパラメータとしてもよい。この場合、個別に公開すべき公開鍵はyだけとなり、公開鍵のサイズが小さくなる。また、上記の対話プロトコルにおいては、i=1,…,Lについて個別に乱数α,…,αを選択しているが、これらの乱数を1つに共通化してもよい。この場合、チャレンジChA,iを送る際の通信コストを削減することが可能になる。
【0187】
<3:第2実施形態(本手法#2)>
次に、本発明の第2実施形態(本手法#2)について説明する。
【0188】
[3−1:概要]
本手法#2は、SSH10a公開鍵認証方式、SSH10b公開鍵認証方式に対し、能動的攻撃に対する安全性レベルが保証されるようにする仕組みを適用したものである。繰り返しになるが、能動的攻撃に対する安全性レベルが保証されているか否かが知られていなかった理由は、利用する関数Fの衝突困難性が保証されない上、「検証を行った証明者がsを用いた」という情報を検証者に知られてしまうことが避けられなかったからである。従って、対話プロトコルの中で「検証を行った証明者がsを用いた」という情報を検証者に知られないようにすれば、能動的攻撃に対する安全性レベルを保証することができる。
【0189】
そこで、本件発明者は、秘密鍵s、公開鍵yを多重化する方式を考案した。この方式は、L個(L≧2)のs,…,s∈Kを秘密鍵とし、m本のn変数多次多項式F(x)=(f(x),…,f(x))に対して(y,…,y)=(F(s),…,F(s))を満たすy,…,y∈Kを公開鍵とする。さらに、この方式は、どのsを対話プロトコルの中で使用したかが分からないように証明する方式である。この方式を適用すると、対話プロトコルの中で「どのsを利用したか」に関する情報が漏れないため、能動的攻撃に対する安全性レベルが保証されるのである。
【0190】
本手法#2の方式は、検証者がi=1,…,Lについてチャレンジの組(Ch(0),…,Ch(0))及び(Ch(1),…,Ch(1))を証明者に送り、証明者が片方のチャレンジの組を選択して回答するというものである。この手法は、一般にQ(Q≧2)組のチャレンジの組を証明者に送り,証明者が1つのチャレンジの組を選択して回答するものであるが,ここではQ=2の場合について述べることにする。s,…,sを知っている証明者は両方のチャレンジの組に対して回答できるが、s,…,sを知らない偽証者は、ある程度の確率でいずれのチャレンジに対しても回答することができずに偽証が失敗する。なお、証明者は、1つのiについてはsを利用しなくても片方のチャレンジの組に対して回答することができるため、検証が受理される対話プロトコルを実行したとしても、この対話プロトコルの中で、どのsを利用したかは検証者に知られることがないのである。
【0191】
[3−2:SSH10a公開鍵認証方式への適用]
まず、図15を参照しながら、本手法#2の方式をSSH10a公開鍵認証方式に適用した場合の対話プロトコルについて説明する。図15は、本手法#2の方式をSSH10a公開鍵認証方式に適用した場合の対話プロトコルについて説明するための説明図である。この対話プロトコルは、鍵生成アルゴリズムGen、証明者アルゴリズムP、検証者アルゴリズムVにより構成される。以下、各アルゴリズムの内容について説明する。
【0192】
(鍵生成アルゴリズムGen)
まず、鍵生成アルゴリズムGenの構成について説明する。鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数2次多項式f(x,…,x),…,f(x,…,x)と、L個のベクトルs,…,s∈Kを生成する。なお、n変数のベクトル(x,…,x)をxと表記し、m本のn変数2次多項式(f(x),…,f(x))をF(x)と表記する。次に、鍵生成アルゴリズムGenは、y=F(s),…,y=F(s)を計算する。そして、鍵生成アルゴリズムGenは、(F,y,…,y)を公開鍵pkに設定し、(s,…,s)を秘密鍵に設定する。
【0193】
次に、図15を参照しながら、証明者アルゴリズムP、検証者アルゴリズムVの構成について説明する。本手法#1の対話プロトコルは、「証明者がL−1個のy=F(s)を満たすsを知っていること」を、「どのsを使用したか否か」という情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵skは、証明者により秘密に管理されているものとする。
【0194】
本手法#2の対話プロトコルは、図15に示すStep.1〜Step.4の処理ステップにより構成される。以下、各ステップの処理について説明する。
【0195】
Step.1:
まず、証明者アルゴリズムPは、i=1,…,Lについて、ベクトルr,t∈Kと、ベクトルe∈Kを生成する。次いで、証明者アルゴリズムPは、(Cmt;St)←Pa,1(F,y,s;r,t,e)を計算する。そして、証明者アルゴリズムPは、Cmt,…,Cmtを検証者(検証者アルゴリズムV)に送る。
【0196】
Step.2:
Cmt,…,Cmtを受け取った検証者アルゴリズムVは、3つの検証パターンのうち、どの検証パターンを利用するかを選択する。このとき、検証者アルゴリズムVは、2組の検証パターンの組み合わせを選択する。そして、検証者アルゴリズムVは、選択した検証パターンを表すチャレンジの組(Ch(0),…,Ch(0)),(Ch(1),…,Ch(1))∈{0,1,2}を証明者(証明者アルゴリズムP)に送る。但し、Ch(0)≠Ch(1)である。
【0197】
Step.3:
(Ch(0),…,Ch(0)),(Ch(1),…,Ch(1))を受け取った証明者アルゴリズムPは、いずれのチャレンジの組に回答するかをランダムに選択する。なお、その選択結果をd∈{0,1}と表現する。そして、証明者アルゴリズムPは、i∈{1,…,L}についてRsp←Pa,2(Ch(d);St)を計算する。その後、証明者アルゴリズムPは、(Rsp,…,Rsp,d)を検証者(検証者アルゴリズムV)に送る。
【0198】
Step.4:
(Rsp,…,Rsp,d)を受け取った検証者アルゴリズムVは、i∈{1,…,L}について0/1←Dec(F,y;Cmt,Ch(d),Rsp)を実行する。そして、検証者アルゴリズムVは、i∈{1,…,L}について全て受理(出力1)されれば検証が成立したものとみなす。
【0199】
以上、本手法#2の方式をSSH10a公開鍵認証方式に適用した場合の対話プロトコルについて説明した。この対話プロトコルは、SSH10a公開鍵認証方式の安全性により、sを持たない偽証者がi=1,…,Lについて、それぞれ2/3以下の確率でしか、検証者から送られたチャレンジChに正しく回答できないことが保証されている。また、本手法#2を適用したことにより、2つのチャレンジの組の一方についてはL個のiについて検証者から送られたチャレンジChに正しく回答する必要があるため、偽証が成功する確率は、(2/3)+(2/3)−(1/3)=(2L+1−1)/3である。
【0200】
また、上記の対話プロトコルにおいてはs,…,sの全てを使用しているが、L≦3の場合であれば、i=1,…,Lの1つについてsを使用しなくても、どのsを使用しなかったかを検証者に一切知られずに全く証明者と同様の振る舞いをすることが可能である。そこで、1つのsを使用せずに、上記の対話プロトコルと同じ認証が実現可能な対話プロトコル(変形例)について説明する。
【0201】
[3−3:SSH10a公開鍵認証方式への適用(変形例)]
以下、図16を参照しながら、本手法#2の方式をSSH10a公開鍵認証方式に適用した場合の対話プロトコル(変形例)について説明する。図16は、本手法#2の方式をSSH10a公開鍵認証方式に適用した場合の対話プロトコル(変形例)について説明するための説明図である。この対話プロトコルは、鍵生成アルゴリズムGen、証明者アルゴリズムP、検証者アルゴリズムVにより構成される。但し、検証者アルゴリズムVにおいて、先に説明した偽証アルゴリズムの構成が利用される。また、使用しないsのインデックスをiとする。以下、各アルゴリズムの内容について説明する。
【0202】
(鍵生成アルゴリズムGen)
まず、鍵生成アルゴリズムGenの構成について説明する。鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数2次多項式f(x,…,x),…,f(x,…,x)と、L個のベクトルs,…,s∈Kを生成する。但し、si0は、適当に選択したベクトルを用いる。なお、n変数のベクトル(x,…,x)をxと表記し、m本のn変数2次多項式(f(x),…,f(x))をF(x)と表記する。次に、鍵生成アルゴリズムGenは、y=F(s),…,y=F(s)を計算する。但し、yi0=F(si0)になることは保証されていなくてもよい。そして、鍵生成アルゴリズムGenは、(F,y,…,y)を公開鍵pkに設定し、(s,…,s)を秘密鍵に設定する。
【0203】
(証明者アルゴリズムP、検証者アルゴリズムV)
次に、図16を参照しながら、証明者アルゴリズムP、検証者アルゴリズムVの構成について説明する。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵skは、証明者により秘密に管理されているものとする。
【0204】
本手法#2の対話プロトコルは、図16に示すStep.1〜Step.4の処理ステップにより構成される。以下、各ステップの処理について説明する。
【0205】
Step.1:
まず、証明者アルゴリズムPは、i=1,…,Lについて、ベクトルr,t∈Kと、ベクトルe∈Kを生成する。次いで、証明者アルゴリズムPは、Ch∈{0,1,2}を1つ選択する。このChは、iの系列について証明者が回答できない検証パターンに対応する。次いで、証明者アルゴリズムPは、i≠iの場合、(Cmt;St)←Pa,1(F,y,s;r,t,e)を計算する。一方、i=iの場合、証明者アルゴリズムPは、(Cmt;St)←Ma,1(F,y;Ch,s,r,t,e)を計算する。そして、証明者アルゴリズムPは、Cmt,…,Cmtを検証者(検証者アルゴリズムV)に送る。
【0206】
Step.2:
Cmt,…,Cmtを受け取った検証者アルゴリズムVは、3つの検証パターンのうち、どの検証パターンを利用するかを選択する。このとき、検証者アルゴリズムVは、2組の検証パターンの組み合わせを選択する。そして、検証者アルゴリズムVは、選択した検証パターンを表すチャレンジの組(Ch(0),…,Ch(0)),(Ch(1),…,Ch(1))∈{0,1,2}を証明者(証明者アルゴリズムP)に送る。但し、Ch(0)≠Ch(1)である。
【0207】
Step.3:
(Ch(0),…,Ch(0)),(Ch(1),…,Ch(1))を受け取った証明者アルゴリズムPは、いずれのチャレンジの組に回答するかを次のようにして選択する。なお、その選択結果をd∈{0,1}と表現する。Chi0(0)=Chの場合(条件1)、証明者アルゴリズムPは、d←1に設定する。一方、Chi0(1)=Chの場合(条件2)、証明者アルゴリズムPは、d←0に設定する。条件1、2以外の場合、証明者アルゴリズムPは、ランダムにd∈{0,1}を設定する。このような設定方法によると、検証者がどのような検証パターンを要求してきても、dは1/2の確率で0,1の値をとるため、iが1,…,Lのいずれであったかという情報は完全に秘匿される。
【0208】
dを設定した後、証明者アルゴリズムPは、i∈{1,…,L}について次のようにRspiを計算する。i≠iの場合、証明者アルゴリズムPは、Rsp←Pa,2(Ch(d);St)を計算する。一方、i=iの場合、証明者アルゴリズムPは、Rsp←Ma,2(Ch(d);St)を計算する。その後、証明者アルゴリズムPは、(Rsp,…,Rsp,d)を検証者(検証者アルゴリズムV)に送る。
【0209】
Step.4:
(Rsp,…,Rsp,d)を受け取った検証者アルゴリズムVは、i∈{1,…,L}について0/1←Dec(F,y;Cmt,Ch(d),Rsp)を実行する。そして、検証者アルゴリズムVは、i∈{1,…,L}について全て受理(出力1)されれば検証が成立したものとみなす。
【0210】
以上、本手法#2の方式をSSH10a公開鍵認証方式に適用した場合の対話プロトコル(変形例)について説明した。なお、上記の説明においては、2つのチャレンジの組を検証者から証明者に送っているが、例えば、2つ目のチャレンジが、Ch(1)=Ch(0)+1 mod 3であると予め決めてしまってもよい。この場合、片方のチャレンジの組を送らなくて済むため、通信量を削減することが可能になる。
【0211】
[3−4:SSH10b公開鍵認証方式への適用]
次に、図17を参照しながら、本手法#2の方式をSSH10b公開鍵認証方式に適用した場合の対話プロトコルについて説明する。図17は、本手法#2の方式をSSH10b公開鍵認証方式に適用した場合の対話プロトコルについて説明するための説明図である。この対話プロトコルは、鍵生成アルゴリズムGen、証明者アルゴリズムP、検証者アルゴリズムVにより構成される。以下、各アルゴリズムの内容について説明する。
【0212】
(鍵生成アルゴリズムGen)
まず、鍵生成アルゴリズムGenの構成について説明する。鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数2次多項式f(x,…,x),…,f(x,…,x)と、L個のベクトルs,…,s∈Kを生成する。なお、n変数のベクトル(x,…,x)をxと表記し、m本のn変数2次多項式(f(x),…,f(x))をF(x)と表記する。次に、鍵生成アルゴリズムGenは、y=F(s),…,y=F(s)を計算する。そして、鍵生成アルゴリズムGenは、(F,y,…,y)を公開鍵pkに設定し、(s,…,s)を秘密鍵に設定する。
【0213】
(証明者アルゴリズムP、検証者アルゴリズムV)
次に、図135を参照しながら、証明者アルゴリズムP、検証者アルゴリズムVの構成について説明する。本手法#2の対話プロトコルは、「証明者がL−1個のy=F(s)を満たすsを知っていること」を、「どのsを使用したか否か」という情報を検証者に一切漏らさずに、検証者に証明させるものである。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵skは、証明者により秘密に管理されているものとする。
【0214】
本手法#2の対話プロトコルは、図17に示すStep.1〜Step.6の処理ステップにより構成される。以下、各ステップの処理について説明する。
【0215】
Step.1:
まず、証明者アルゴリズムPは、i=1,…,Lについて、ベクトルr,t∈Kと、ベクトルe∈Kを生成する。次いで、証明者アルゴリズムPは、(CmtA,i;StA,i)←Pa,1(F,y,s;r,t,e)を計算する。そして、証明者アルゴリズムPは、(CmtA,1,…,CmtA,L)を検証者(検証者アルゴリズムV)に送る。
【0216】
Step.2:
(CmtA,1,…,CmtA,L)を受け取った検証者アルゴリズムVは、q通り存在する環Kの元からL個の乱数の組(α,…,α)を選択する。そして、検証者アルゴリズムVは、チャレンジ(ChA,1,…,ChA,L)=(α,…,α)を証明者(証明者アルゴリズムP)に送る。
【0217】
Step.3:
(ChA,1,…,ChA,L)を受け取った証明者アルゴリズムPは、i=1,…,Lについて(CmtB,i;StB,i)←Pb,2(ChA,i;StA,i)を計算する。そして、証明者アルゴリズムPは、(CmtB,1,…,CmtB,L)を検証者(検証者アルゴリズムV)に送る。
【0218】
Step.4:
(CmtB,1,…,CmtB,L)を受け取った検証者アルゴリズムVは、3つの検証パターンのうち、どの検証パターンを利用するかを選択する。このとき、検証者アルゴリズムVは、2組の検証パターンの組み合わせを選択する。そして、検証者アルゴリズムVは、選択した検証パターンを表すチャレンジの組(ChB,1(0),…,ChB,L(0)),(ChB,1(1),…,ChB,L(1))∈{0,1}Lを証明者(証明者アルゴリズムP)に送る。但し、ChB,i(0)≠ChB,i(1)である。
【0219】
Step.5:
(ChB,1(0),…,ChB,L(0)),(ChB,1(1),…,ChB,L(1))を受け取った証明者アルゴリズムPは、いずれのチャレンジの組に回答するかをランダムに選択する。なお、その選択結果をd∈{0,1}と表現する。そして、証明者アルゴリズムPは、i∈{1,…,L}についてRsp←Pb,2(ChB,i(d);StB,i)を計算する。その後、証明者アルゴリズムPは、(Rsp,…,Rsp,d)を検証者(検証者アルゴリズムV)に送る。
【0220】
Step.6:
(Rsp,…,Rsp,d)を受け取った検証者アルゴリズムVは、i∈{1,…,L}について0/1←Dec(F,y;CmtA,i,ChA,i,CmtB,i,ChB,i(d),Rsp)を実行する。そして、検証者アルゴリズムVは、i∈{1,…,L}について全て受理(出力1)されれば検証が成立したものとみなす。
【0221】
以上、本手法#2の方式をSSH10b公開鍵認証方式に適用した場合の対話プロトコルについて説明した。この対話プロトコルは、SSH10b公開鍵認証方式の安全性により、sを持たない偽証者がi=1,…,Lについて、それぞれ1/2+1/2q以下の確率でしか、検証者から送られたチャレンジに正しく回答できないことが保証されている。また、本手法#2を適用したことにより、2つのチャレンジの組の一方に対し、L個のiについて検証者から送られたチャレンジに正しく回答する必要があるため、偽証が成功する確率は、(1/2+1/2q)+(1/2+1/2q)=2(1/2+1/2q)である。
【0222】
また、上記の対話プロトコルにおいてはs,…,sの全てを使用しているが、i=1,…,Lの1つについてsを使用しなくても、どのsを使用しなかったかを検証者に一切知られずに全く証明者と同様の振る舞いをすることが可能である。そこで、1つのsを使用せずに、上記の対話プロトコルと同じ認証が実現可能な対話プロトコル(変形例)について説明する。
【0223】
[3−5:SSH10b公開鍵認証方式への適用(変形例)]
以下、図18を参照しながら、本手法#2の方式をSSH10b公開鍵認証方式に適用した場合の対話プロトコル(変形例)について説明する。図18は、本手法#2の方式をSSH10b公開鍵認証方式に適用した場合の対話プロトコル(変形例)について説明するための説明図である。この対話プロトコルは、鍵生成アルゴリズムGen、証明者アルゴリズムP、検証者アルゴリズムVにより構成される。但し、検証者アルゴリズムVにおいて、先に説明した偽証アルゴリズムの構成が利用される。また、使用しないsのインデックスをiとする。以下、各アルゴリズムの内容について説明する。
【0224】
(鍵生成アルゴリズムGen)
まず、鍵生成アルゴリズムGenの構成について説明する。鍵生成アルゴリズムGenは、環K上で定義されるm本のn変数2次多項式f(x,…,x),…,f(x,…,x)と、L個のベクトルs,…,s∈Kを生成する。但し、si0は、適当に選択したベクトルを用いる。なお、n変数のベクトル(x,…,x)をxと表記し、m本のn変数2次多項式(f(x),…,f(x))をF(x)と表記する。次に、鍵生成アルゴリズムGenは、y=F(s),…,y=F(s)を計算する。但し、yi0=F(si0)になることは保証されていなくてもよい。そして、鍵生成アルゴリズムGenは、(F,y,…,y)を公開鍵pkに設定し、(s,…,s)を秘密鍵に設定する。
【0225】
(証明者アルゴリズムP、検証者アルゴリズムV)
次に、図18を参照しながら、証明者アルゴリズムP、検証者アルゴリズムVの構成について説明する。なお、鍵生成アルゴリズムGenにより生成された公開鍵pkは、証明者と検証者の間で共有されているものとする。また、鍵生成アルゴリズムGenにより生成された秘密鍵skは、証明者により秘密に管理されているものとする。
【0226】
本手法#2の対話プロトコルは、図18に示すStep.1〜Step.6の処理ステップにより構成される。以下、各ステップの処理について説明する。
【0227】
Step.1:
まず、証明者アルゴリズムPは、i=1,…,Lについて、ベクトルr,t∈Kと、ベクトルe∈Kを生成する。次いで、証明者アルゴリズムPは、Ch∈{0,1}を1つ選択する。このChは、iの系列について証明者が回答できない検証パターンに対応する。次いで、証明者アルゴリズムPは、i≠iの場合について、(CmtA,i;StA,i)←Pb,1(F,y,s;r,t,e)を計算する。また、i=iの場合について、証明者アルゴリズムPは、(CmtA,i;StA,i)←Mb,1(F,y;Ch,s,r,t,e)を計算する。そして、証明者アルゴリズムPは、(CmtA,1,…,CmtA,L)を検証者(検証者アルゴリズムV)に送る。
【0228】
Step.2:
(CmtA,1,…,CmtA,L)を受け取った検証者アルゴリズムVは、q通り存在する環Kの元からL個の乱数の組(α,…,α)を選択する。そして、検証者アルゴリズムVは、チャレンジ(ChA,1,…,ChA,L)=(α,…,α)を証明者(証明者アルゴリズムP)に送る。
【0229】
Step.3:
(ChA,1,…,ChA,L)を受け取った証明者アルゴリズムPは、i=1,…,Lについて次のようにCmtB,iを計算する。まず、i≠iの場合について、証明者アルゴリズムPは、(CmtB,i;StB,i)←Pb,2(ChA,i;StA,i)を計算する。一方、i=iの場合について、証明者アルゴリズムPは、(CmtB,i;StB,i)←Mb,2(ChA,i;StA,i)を計算する。そして、証明者アルゴリズムPは、(CmtB,1,…,CmtB,L)を検証者(検証者アルゴリズムV)に送る。
【0230】
Step.4:
(CmtB,1,…,CmtB,L)を受け取った検証者アルゴリズムVは、3つの検証パターンのうち、どの検証パターンを利用するかを選択する。このとき、検証者アルゴリズムVは、2組の検証パターンの組み合わせを選択する。そして、検証者アルゴリズムVは、選択した検証パターンを表すチャレンジの組(ChB,1(0),…,ChB,L(0)),(ChB,1(1),…,ChB,L(1))∈{0,1}Lを証明者(証明者アルゴリズムP)に送る。但し、ChB,i(0)≠ChB,i(1)である。
【0231】
Step.5:
(ChB,1(0),…,ChB,L(0)),(ChB,1(1),…,ChB,L(1))を受け取った証明者アルゴリズムPは、いずれのチャレンジの組に回答するかを次のようにして選択する。なお、その選択結果をd∈{0,1}と表現する。ChB,i0(0)=Chの場合、証明者アルゴリズムPは、d←1に設定する。一方、ChB,i0(1)=Chの場合、証明者アルゴリズムPは、d←0に設定する。この設定方法を用いると、検証者がどのような検証パターンを要求してきてもdは、それぞれ1/2の確率で0,1の値をとる。つまり、dが0,1のどの値であったかという情報が完全に秘匿されているのである。
【0232】
次いで、証明者アルゴリズムPは、i=1,…,Lについて次のようにRspを計算する。i≠iの場合について、証明者アルゴリズムPは、Rsp←Pb,3(ChB,i(d);StB,i)を計算する。また、i=iの場合について、証明者アルゴリズムPは、Rsp←Mb,3(ChB,i(d);StB,i)を計算する。その後、証明者アルゴリズムPは、(Rsp,…,Rsp,d)を検証者(検証者アルゴリズムV)に送る。
【0233】
Step.6:
(Rsp,…,Rsp,d)を受け取った検証者アルゴリズムVは、i=1,…,Lについて0/1←Dec(F,y;CmtA,i,ChA,i,CmtB,i,ChB,i(d),Rsp)を実行する。そして、検証者アルゴリズムVは、i=1,…,Lについて全て受理(出力1)されれば検証が成立したものとみなす。
【0234】
以上、本手法#2の方式をSSH10b公開鍵認証方式に適用した場合の対話プロトコル(変形例)について説明した。なお、上記の説明においては、2つのチャレンジの組を検証者から証明者に送っているが、例えば、2つ目のチャレンジが、Ch(1)=Ch(0)+1 mod 2であると予め決めてしまってもよい。この場合、片方のチャレンジの組を送らなくて済むため、通信量を削減することが可能になる。
【0235】
以上、本発明の第2実施形態について説明した。上記説明においては、SSH10a公開鍵認証方式、SSH10b公開鍵認証方式を例に挙げて述べたが、本手法#2の適用範囲はこれに限定されない。SSH10a公開鍵認証方式やSSH10b公開鍵認証方式の変形例、及びその他の公開鍵認証方式に対しても適用が可能である。例えば、上記の例では公開鍵を(F,y)に設定しているが、Fが秘密鍵によらないパラメータであるため、このFを証明者毎に設定するのではなく、システム全体に共通するパラメータとしてもよい。この場合、個別に公開すべき公開鍵はyだけとなり、公開鍵のサイズが小さくなる。また、上記の対話プロトコルにおいては、i=1,…,Lについて個別に乱数α,…,αを選択しているが、これらの乱数を1つの共通化してもよい。この場合、チャレンジChA,iを送る際の通信コストを削減することが可能になる。
【0236】
<4:補足>
ここで、本手法#1、#2について説明を補足する。
【0237】
[4−1:方式の拡張について]
これまでは多次多変数連立方程式の求解問題に基づく公開鍵認証方式について説明してきた。しかし、本手法#1、#2の考え方は、その他の公開鍵認証方式に対しても同様に適用することが可能である。そこで、一例として、Syndrome Decoding問題に基づく公開鍵認証方式への適用方法、Constrained Linear Equations問題に基づく公開鍵認証方式への適用方法、Permuted Kernel問題に基づく公開鍵認証方式への適用方法、代数曲面上の求セクション問題に基づく公開鍵認証方式への適用方法、Permuted Perceptrons問題に基づく公開鍵認証方式への適用方法について紹介する。
【0238】
(Syndrome Decoding問題への適用)
Syndrome Decoding問題に基づく公開鍵認証方式は、例えば、「Jacques Stern, A New Identification Scheme Based on Syndrome Decoding, CRYPTO 1993, p13−21.」や「Jacques Stern, A New Paradigm for Public Key Identification, IEEE Transactions on Information Theory, 1996, p13−21.」に記載されている。これによると、この公開鍵認証方式には、3パスの方式と5パスの方式がある。
【0239】
3パスの方式は、SSH10a公開鍵認証方式と同様に、検証パターンが3パターンあり、そのうちの2パターンまでは対応可能な偽証アルゴリズムが存在する。また、5パスの方式も、SSH10b公開鍵認証方式と同様に、検証パターンが2パターンあり、そのうちの1パターンまでには対応可能な偽証アルゴリズムが存在する。そのため、3パスの方式にはSSH10a公開鍵認証方式について先に説明した方法が、5パスの方式にはSSH10b公開鍵認証方式について先に説明した方法が適用可能である。
【0240】
(Constrained Linear Equations問題への適用)
Constrained Linear Equations問題に基づく公開鍵認証方式は、例えば、「Jacques Stern, Designing Identification Schemes with Keys of Short Size, CRYPTO 1994, p164−173.」に記載されている。これによると、この公開鍵認証方式にも3パスの方式と5パスの方式がある。
【0241】
3パスの方式は、SSH10a公開鍵認証方式と同様に、検証パターンが3パターンあり、そのうちの2パターンまでは対応可能な偽証アルゴリズムが存在する。また、5パスの方式も、SSH10b公開鍵認証方式と同様に、検証パターンが2パターンあり、そのうちの1パターンまでには対応可能な偽証アルゴリズムが存在する。そのため、3パスの方式にはSSH10a公開鍵認証方式について先に説明した方法が、5パスの方式にはSSH10b公開鍵認証方式について先に説明した方法が適用可能である。
【0242】
(Permuted Kernel問題への適用)
Permuted Kernel問題に基づく公開鍵認証方式は、例えば、「Adi Shamir, An Efficient Identification Scheme Based on Permuted Kernels (Extended Abstract),CRYPTO 1989, p606−609.」に記載されている。これによると、この公開鍵認証方式には、検証パターンが2パターンあり、そのうち1パターンまでには対応可能な偽証アルゴリズムが存在する。そのため、この公開鍵認証方式にはSSH10b公開鍵認証方式について先に説明した方法が適用可能である。
【0243】
(代数曲面上の求セクション問題への適用)
代数曲面上の求セクション問題に基づく公開鍵認証方式には、3パスと5パスの方式がある(例えば、特願2010−125026号などを参照)。3パスの方式は、SSH10a公開鍵認証方式と同様に、検証パターンが3パターンあり、そのうちの2パターンまでは対応可能な偽証アルゴリズムが存在する。また、5パスの方式も、SSH10b公開鍵認証方式と同様に、検証パターンが2パターンあり、そのうちの1パターンまでには対応可能な偽証アルゴリズムが存在する。そのため、3パスの方式にはSSH10a公開鍵認証方式について先に説明した方法が、5パスの方式にはSSH10b公開鍵認証方式について先に説明した方法が適用可能である。
【0244】
(Permuted Perceptrons問題への適用)
Permuted Perceptrons問題に基づく公開鍵認証方式は、例えば、「David Pointcheval, A New Identification Scheme Based on the Perceptrons Problem, EUROCRYPT 1995, p319−328.」や「David Pointcheval and Guillaume Poupard, A New NP−Complete Problem and Public−Key Identification, Des. Codes Cryptography, 2003, p5−31.」に記載されている。これによると、この公開鍵認証方式には、3パスの方式と5パスの方式がある。
【0245】
3パスの方式は検証パターンが4パターンあり、そのうち3パターンまでには対応可能な偽証アルゴリズムが存在する。一方、5パスの方式は検証パターンが3パターンあり、そのうち2パターンまでには対応可能な偽証アルゴリズムが存在する。そのため、SSH10a公開鍵認証方式やSSH10b公開鍵認証方式と同様に、この公開鍵認証方式に対しても本手法#1、#2の技術を適用することが可能である。但し、この公開鍵認証方式に対して本手法#1を適用する際には以下の変更が必要になる。
【0246】
検証パターンがkパターンある方式に対し、秘密鍵をL=k個に多重化して本手法#1を適用する場合、i=1,…,Lから1個だけ回答しないi(以下、i)を次のように選択することが必要になる。つまり、iの選択方法は、Chi0=Chならばi←iが選択され、Chi0≠Chならばi∈{1,…,L}\{i}からランダムにiが選択されるというものになる。
【0247】
また、検証パターンがkパターンある方式に対し、秘密鍵をL(L<k)個に多重化して本手法#1を適用する場合、i=1,…,Lから1個だけ回答しないi(以下、i)を次のように選択することが必要になる。つまり、iの選択方法は、Chi0=Chならばi←iが選択され、Chi0≠Chならば確率(1−1/k)−1(1/L−1/k)でi←iが選択され、かつ、確率1−(1−1/k)−1(1/L−1/k)でi∈{1,…,L}\{i}からランダムにiが選択されるというものになる。
【0248】
上記の方法によれば検証者がどのような検証パターンを要求してきてもiが1/Lの確率で1,…,Lの値をとることになり、iが1,…,Lのいずれであったかという情報が完全に秘匿される。
【0249】
以上説明したように、本手法#1、#2は、SSH10a公開鍵認証方式、SSH10b公開鍵認証方式に限らず、様々な公開鍵認証方式に適用可能である。
【0250】
[4−2:非対話型の公開鍵認証方式について]
上記の本手法#1、#2を適用した公開鍵認証方式は、検証者が乱数しか送信しない方式であるため、1パス(非対話型)の公開鍵認証方式に変形することが可能である。例えば、N回の並列的繰り返し構成において検証者との間でやりとりした内容にハッシュ関数を適用したものを、検証者から送信される乱数の代わりに用いればよい。また、ハッシュ関数の引数に、証明者が選んだ乱数を加えてもよい。このように、検証者が乱数を選択する代わりに証明者自身がハッシュ関数を利用することで、検証者が乱数を選択した場合と同じ振る舞いが実現される。但し、理想的なハッシュ関数を利用することが望ましい。また、偽証を不可能にするために繰り返し回数Nを十分に大きくとることが望ましい。このような工夫により、非対話型の公開鍵認証方式に変形することが可能になる。
【0251】
[4−3:通信量の削減方法について]
ここで、図19、図20を参照しながら、対話プロトコルにおける通信量の削減方法について簡単に説明を補足する。
【0252】
既に説明したように、SSH10a公開鍵認証方式の1パス目において、証明者から検証者にメッセージの組(c,c,c)が送られる。但し、上記説明においてはCmtという表現を用いていた。N回の並列的繰り返し構成の場合、このメッセージの組は、図19に示すように、(c1,1,c1,2,c1,3,…,cN,1,cN,2,cN,3)となり、通信量が非常に大きくなってしまう。そこで、本件発明者は、これらのメッセージを1つのハッシュ値にまとめて送る構成を考案した。
【0253】
図19に示すように、この構成を適用すると、1パス目で送るメッセージが1つのハッシュ値だけとなり、大幅に通信量を削減することが可能になる。但し、このハッシュ値、及び証明者から送られるチャレンジに対する回答から復元できないハッシュ値については、回答と併せて証明者から送ってもらうようにする。この構成によると、N回の並列的繰り返し構成の場合、送るべき情報の数を2N−1個削減することが可能になる。図20に示すように、SSH10b公開鍵認証方式に対しても同様の構成を適用することが可能である。この場合、送るべき情報の数をN−1個削減することが可能になる。
【0254】
以上、本手法#1、#2について説明を補足した。
【0255】
<5:ハードウェア構成>
上記の各アルゴリズムは、例えば、図21に示す情報処理装置のハードウェア構成を用いて実行することが可能である。つまり、当該各アルゴリズムの処理は、コンピュータプログラムを用いて図21に示すハードウェアを制御することにより実現される。なお、このハードウェアの形態は任意であり、例えば、パーソナルコンピュータ、携帯電話、PHS、PDA等の携帯情報端末、ゲーム機、接触式又は非接触式のICチップ、接触式又は非接触式のICカード、又は種々の情報家電がこれに含まれる。但し、上記のPHSは、Personal Handy−phone Systemの略である。また、上記のPDAは、Personal Digital Assistantの略である。
【0256】
図21に示すように、このハードウェアは、主に、CPU902と、ROM904と、RAM906と、ホストバス908と、ブリッジ910と、を有する。さらに、このハードウェアは、外部バス912と、インターフェース914と、入力部916と、出力部918と、記憶部920と、ドライブ922と、接続ポート924と、通信部926と、を有する。但し、上記のCPUは、Central Processing Unitの略である。また、上記のROMは、Read Only Memoryの略である。そして、上記のRAMは、Random Access Memoryの略である。
【0257】
CPU902は、例えば、演算処理装置又は制御装置として機能し、ROM904、RAM906、記憶部920、又はリムーバブル記録媒体928に記録された各種プログラムに基づいて各構成要素の動作全般又はその一部を制御する。ROM904は、CPU902に読み込まれるプログラムや演算に用いるデータ等を格納する手段である。RAM906には、例えば、CPU902に読み込まれるプログラムや、そのプログラムを実行する際に適宜変化する各種パラメータ等が一時的又は永続的に格納される。
【0258】
これらの構成要素は、例えば、高速なデータ伝送が可能なホストバス908を介して相互に接続される。一方、ホストバス908は、例えば、ブリッジ910を介して比較的データ伝送速度が低速な外部バス912に接続される。また、入力部916としては、例えば、マウス、キーボード、タッチパネル、ボタン、スイッチ、及びレバー等が用いられる。さらに、入力部916としては、赤外線やその他の電波を利用して制御信号を送信することが可能なリモートコントローラが用いられることもある。
【0259】
出力部918としては、例えば、CRT、LCD、PDP、又はELD等のディスプレイ装置、スピーカ、ヘッドホン等のオーディオ出力装置、プリンタ、携帯電話、又はファクシミリ等、取得した情報を利用者に対して視覚的又は聴覚的に通知することが可能な装置である。但し、上記のCRTは、Cathode Ray Tubeの略である。また、上記のLCDは、Liquid Crystal Displayの略である。そして、上記のPDPは、Plasma DisplayPanelの略である。さらに、上記のELDは、Electro−Luminescence Displayの略である。
【0260】
記憶部920は、各種のデータを格納するための装置である。記憶部920としては、例えば、ハードディスクドライブ(HDD)等の磁気記憶デバイス、半導体記憶デバイス、光記憶デバイス、又は光磁気記憶デバイス等が用いられる。但し、上記のHDDは、Hard Disk Driveの略である。
【0261】
ドライブ922は、例えば、磁気ディスク、光ディスク、光磁気ディスク、又は半導体メモリ等のリムーバブル記録媒体928に記録された情報を読み出し、又はリムーバブル記録媒体928に情報を書き込む装置である。リムーバブル記録媒体928は、例えば、DVDメディア、Blu−rayメディア、HD DVDメディア、各種の半導体記憶メディア等である。もちろん、リムーバブル記録媒体928は、例えば、非接触型ICチップを搭載したICカード、又は電子機器等であってもよい。但し、上記のICは、Integrated Circuitの略である。
【0262】
接続ポート924は、例えば、USBポート、IEEE1394ポート、SCSI、RS−232Cポート、又は光オーディオ端子等のような外部接続機器930を接続するためのポートである。外部接続機器930は、例えば、プリンタ、携帯音楽プレーヤ、デジタルカメラ、デジタルビデオカメラ、又はICレコーダ等である。但し、上記のUSBは、Universal Serial Busの略である。また、上記のSCSIは、Small Computer System Interfaceの略である。
【0263】
通信部926は、ネットワーク932に接続するための通信デバイスであり、例えば、有線又は無線LAN、Bluetooth(登録商標)、又はWUSB用の通信カード、光通信用のルータ、ADSL用のルータ、又は接触又は非接触通信用のデバイス等である。また、通信部926に接続されるネットワーク932は、有線又は無線により接続されたネットワークにより構成され、例えば、インターネット、家庭内LAN、赤外線通信、可視光通信、放送、又は衛星通信等である。但し、上記のLANは、Local Area Networkの略である。また、上記のWUSBは、Wireless USBの略である。そして、上記のADSLは、Asymmetric Digital Subscriber Lineの略である。
【0264】
<6:まとめ>
最後に、本発明の実施形態に係る技術内容について簡単に纏める。ここで述べる技術内容は、例えば、PC、携帯電話、携帯ゲーム機、携帯情報端末、情報家電、カーナビゲーションシステム等、種々の情報処理装置に対して適用することができる。
【0265】
上記の情報処理装置の機能構成は次のように表現することができる。当該情報処理装置は、次のような鍵保持部と、対話プロトコル実行部とを有する。当該鍵保持部は、L個(L≧2)の秘密鍵s(i=1〜L)、及びn次多変数多項式の組F(n≧2)についてy=F(s)を満たすL個の公開鍵yを保持するものである。また、上記の対話プロトコル実行部は、(L−1)個のy=F(s)を満たす秘密鍵sを知っていることを証明するための対話プロトコルを検証者との間で実行するものである。また、前記対話プロトコル実行部は、前記検証者との間で前記対話プロトコルを実行する際に、どの秘密鍵sを使用したかを当該検証者に知られないようにする。
【0266】
上記のように、秘密鍵sを多重化し、対話プロトコルを実行する際に、そのうちの一部の秘密鍵を利用し、さらに、どの秘密鍵sが利用されたのかを対話プロトコルの中で知られないようにすることにより、並列的繰り返し構成の場合にも、能動的攻撃に対する安全性レベルを保証することが可能になる。つまり、偽証者が検証者に成りすまして認証に利用される秘密鍵sの情報を得ようとしても、対話プロトコルの中で、どの秘密鍵sが利用されたかが検証者にも分からない。つまり、任意の回数だけ対話プロトコルを実行できる状況にあっても、秘密鍵sの情報が証明者から漏れないため、能動的攻撃に対する安全性レベルを保証することができるのである。
【0267】
(備考)
上記の情報処理装置は、証明者側及び検証者側の認証装置の一例である。また、上記のROM904、RAM906、記憶部920、リムーバブル記録媒体928は、鍵保持部の一例である。なお、この鍵保持部に保持される秘密鍵si、公開鍵yiは、鍵生成アルゴリズムGenにより生成される。また、証明者アルゴリズムP、検証者アルゴリズムVは、対話プロトコル実行部の一例である。なお、実際には、証明者アルゴリズムP、検証者アルゴリズムVがCPU902の機能により実行されることにより対話プロトコル実行部の機能が実現される。また、証明者アルゴリズムPによって実現される機能により、チャレンジ受信部、チャレンジ選択部、回答生成部、回答送信部、メッセージ送信部の機能が実現される。なお、情報の送受信には、通信部926の機能が利用される。
【0268】
以上、添付図面を参照しながら本発明の好適な実施形態について説明したが、本発明は係る例に限定されないことは言うまでもない。当業者であれば、特許請求の範囲に記載された範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、それらについても当然に本発明の技術的範囲に属するものと了解される。
【符号の説明】
【0269】
Gen 鍵生成アルゴリズム
P 証明者アルゴリズム
V 検証者アルゴリズム


【特許請求の範囲】
【請求項1】
L個(L≧2)の秘密鍵s(i=1〜L)、及びn次多変数多項式の組F(n≧2)についてy=F(s)を満たすL個の公開鍵yを保持する鍵保持部と、
(L−1)個のy=F(s)を満たす秘密鍵sを知っていることを証明するための対話プロトコルを検証者との間で実行する対話プロトコル実行部と、
を備え、
前記対話プロトコル実行部は、
前記検証者からL個のチャレンジChを受信するチャレンジ受信部と、
前記チャレンジ受信部により受信されたL個のチャレンジChの中から(L−1)個のチャレンジChを任意に選択するチャレンジ選択部と、
前記秘密鍵sを用いて、前記チャレンジ選択部により選択された(L−1)個のチャレンジChのそれぞれに対する(L−1)個の回答Rspを生成する回答生成部と、
前記回答生成部により生成された(L−1)個の回答Rspを前記検証者に送信する回答送信部と、
を含む、
認証装置。
【請求項2】
前記対話プロトコル実行部は、
前記検証者に対し、L個の前記秘密鍵sのそれぞれに対応するメッセージCmtを送信するメッセージ送信部をさらに含み、
前記チャレンジ受信部は、前記メッセージ送信部により送信された各メッセージCmtに応じて、前記検証者によりk通り(k≧2)の検証パターンの中から選択された検証パターンを示すチャレンジChを受信する、
請求項1に記載の認証装置。
【請求項3】
前記メッセージCmtがCmt=(ci,1,…,ci,N)である場合、
前記メッセージ送信部は、一方向性関数Hを用いて新たなメッセージCmt’=H(Cmt,…,Cmt)を算出して当該メッセージCmt’を前記検証者に送信し、
前記回答送信部は、前記回答Rspと共に、当該回答Rspを利用しても前記検証者が復元できない前記メッセージCmtの要素を送信する、
請求項2に記載の認証装置。
【請求項4】
前記鍵保持部は、前記L個の秘密鍵sのうち、1つの秘密鍵si0(1≦i≦L)を保持しないようにし、
前記対話プロトコル実行部は、前記対話プロトコルの中で実行される前記秘密鍵si0に関する処理を偽証アルゴリズムに基づいて実行する、
請求項2に記載の認証装置。
【請求項5】
L個の秘密鍵s(i=1〜L)、n次多変数多項式の組F(n≧2)についてy=F(s)を満たすL個の公開鍵yを保持する鍵保持部と、
検証者からQ組(Q≧2)のL個のチャレンジCh(j)(j=1〜Q)を受信するチャレンジ受信部と、
前記チャレンジ受信部により受信されたQ組のL個のチャレンジCh(j)の中から1組のL個のチャレンジCh(j)を任意に選択するチャレンジ選択部と、
前記秘密鍵sを用いて、前記チャレンジ選択部により選択されたL個のチャレンジCh(j)のそれぞれに対するL個の回答Rspを生成する回答生成部と、
前記回答生成部により生成されたL個の回答Rspを前記検証者に送信する回答送信部と、
を備える、
認証装置。
【請求項6】
前記対話プロトコル実行部は、
前記検証者に対し、L個の前記秘密鍵sのそれぞれに対応するメッセージCmtを送信するメッセージ送信部をさらに含み、
前記チャレンジ受信部は、前記メッセージ送信部により送信された各メッセージCmtに応じて、前記検証者によりk通り(k≧2)の検証パターンの中から選択された検証パターンを示すチャレンジCh(j)を受信する、
請求項5に記載の認証装置。
【請求項7】
前記メッセージCmtがCmt=(ci,1,…,ci,N)である場合、
前記メッセージ送信部は、一方向性関数Hを用いて新たなメッセージCmt’=H(Cmt,…,Cmt)を算出して当該メッセージCmt’を前記検証者に送信し、
前記回答送信部は、前記回答Rspと共に、当該回答Rspを利用しても前記検証者が復元できない前記メッセージCmtの要素を送信する、
請求項6に記載の認証装置。
【請求項8】
L個(L≧2)の秘密鍵s(i=1〜L)、及びn次多変数多項式の組F(n≧2)についてy=F(s)を満たすL個の公開鍵yを生成する鍵生成ステップと、
(L−1)個のy=F(s)を満たす秘密鍵sを知っていることを証明するための対話プロトコルを検証者との間で実行する対話プロトコル実行ステップと、
を含み、
前記対話プロトコル実行ステップは、
前記検証者からL個のチャレンジChを受信するチャレンジ受信ステップと、
前記チャレンジ受信ステップで受信されたL個のチャレンジChの中から(L−1)個のチャレンジChを任意に選択するチャレンジ選択ステップと、
前記秘密鍵sを用いて、前記チャレンジ選択ステップで選択された(L−1)個のチャレンジChのそれぞれに対する(L−1)個の回答Rspを生成する回答生成ステップと、
前記回答生成ステップで生成された(L−1)個の回答Rspを前記検証者に送信する回答送信ステップと、
を含む、
認証方法。
【請求項9】
L個(L≧2)の秘密鍵s(i=1〜L)、及びn次多変数多項式の組F(n≧2)についてy=F(s)を満たすL個の公開鍵yを保持する鍵保持機能と、
(L−1)個のy=F(s)を満たす秘密鍵sを知っていることを証明するための対話プロトコルを検証者との間で実行する対話プロトコル実行機能と、
をコンピュータに実現させるためのプログラムであり、
前記対話プロトコル実行機能は、
前記検証者からL個のチャレンジChを受信するチャレンジ受信機能と、
前記チャレンジ受信機能により受信されたL個のチャレンジChの中から(L−1)個のチャレンジChを任意に選択するチャレンジ選択機能と、
前記秘密鍵sを用いて、前記チャレンジ選択機能により選択された(L−1)個のチャレンジChのそれぞれに対する(L−1)個の回答Rspを生成する回答生成機能と、
前記回答生成機能により生成された(L−1)個の回答Rspを前記検証者に送信する回答送信機能と、
を含む、
プログラム。
【請求項10】
L個の秘密鍵s(i=1〜L)、n次多変数多項式の組F(n≧2)についてy=F(s)を満たすL個の公開鍵yを生成する鍵生成ステップと、
検証者からQ組(Q≧2)のL個のチャレンジCh(j)(j=1〜Q)を受信するチャレンジ受信ステップと、
前記チャレンジ受信ステップで受信されたQ組のL個のチャレンジCh(j)の中から1組のL個のチャレンジCh(j)を任意に選択するチャレンジ選択ステップと、
前記秘密鍵sを用いて、前記チャレンジ選択ステップで選択されたL個のチャレンジCh(j)のそれぞれに対するL個の回答Rspを生成する回答生成ステップと、
前記回答生成ステップで生成されたL個の回答Rspを前記検証者に送信する回答送信ステップと、
を含む、
認証方法。
【請求項11】
L個の秘密鍵s(i=1〜L)、n次多変数多項式F(n≧2)についてy=F(s)を満たすL個の公開鍵yを保持する鍵保持機能と、
検証者からQ組(Q≧2)のL個のチャレンジCh(j)(j=1〜Q)を受信するチャレンジ受信機能と、
前記チャレンジ受信機能により受信されたQ組のL個のチャレンジCh(j)の中から1組のL個のチャレンジCh(j)を任意に選択するチャレンジ選択機能と、
前記秘密鍵sを用いて、前記チャレンジ選択機能により選択されたL個のチャレンジCh(j)のそれぞれに対するL個の回答Rspを生成する回答生成機能と、
前記回答生成機能により生成されたL個の回答Rspを前記検証者に送信する回答送信機能と、
をコンピュータに実現させるためのプログラム。


【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate