説明

情報処理装置、署名生成装置、署名検証装置、情報処理方法、署名生成方法、及び署名検証方法

【課題】高い安全性を有する効率的な電子署名方式を実現すること。
【解決手段】
環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及び署名鍵s∈Kを用いて文書Mに対する電子署名を生成する署名生成部と、前記2次多変数多項式の組F及びベクトルy=(f(s),…,f(s))を保持する検証者へと前記電子署名を提供する署名提供部と、を備え、前記署名生成部は、前記電子署名を生成する過程で実行する、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算を式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行する、署名生成装置が提供される。

【発明の詳細な説明】
【技術分野】
【0001】
本技術は、情報処理装置、署名生成装置、署名検証装置、情報処理方法、署名生成方法、及び署名検証方法に関する。
【背景技術】
【0002】
情報処理技術や通信技術の急速な発展に伴い、公文書、私文書を問わず、文書の電子化が急速に進んでいる。これに伴い、多くの個人や企業は、電子文書の安全管理に大きな関心を寄せている。こうした関心の高まりを受け、各方面で電子文書の盗聴や偽造等のタンパリング行為に対する対抗策が盛んに研究されるようになってきた。電子文書の盗聴に対しては、例えば、電子文書を暗号化することにより安全性が確保される。また、電子文書の偽造に対しては、例えば、電子署名を利用することにより安全性が確保される。但し、利用する暗号や電子署名が高いタンパリング耐性を有していなければ、十分な安全性が保証されない。
【0003】
電子署名は、電子文書の作成者を特定するために利用される。そのため、電子署名は、電子文書の作成者しか生成できないようにすべきである。仮に、悪意ある第三者が同じ電子署名を生成できてしまうと、その第三者が電子文書の作成者に成りすますことができてしまう。つまり、悪意ある第三者により電子文書が偽造されてしまう。こうした偽造を防止するため、電子署名の安全性については様々な議論が交わされてきた。現在広く利用されている電子署名方式としては、例えば、RSA署名方式やDSA署名方式などが知られている。
【0004】
RSA署名方式は、「大きな合成数に対する素因数分解の困難性(以下、素因数分解問題)」を安全性の根拠とする。また、DSA署名方式は、「離散対数問題に対する解の導出の困難性」を安全性の根拠とする。これらの根拠は、古典的なコンピュータを利用して素因数分解問題や離散対数問題を効率的に解くアルゴリズムが存在しないことに起因する。つまり、上記の困難性は、古典的なコンピュータにおける計算量的な困難性を意味する。しかしながら、量子コンピュータを用いると、素因数分解問題や離散対数問題に対する解答が効率的に算出されてしまうと言われている。
【0005】
現在利用されている電子署名方式や公開鍵認証方式の多くは、RSA署名方式やDSA署名方式と同様、素因数分解問題や離散対数問題の困難性に安全性の根拠をおいている。そのため、こうした電子署名方式や公開鍵認証方式は、量子コンピュータが実用化された場合に、その安全性が確保されないことになる。そこで、素因数分解問題や離散対数問題など、量子コンピュータにより容易に解かれてしまう問題とは異なる問題に安全性の根拠をおく新たな電子署名方式及び公開鍵認証方式の実現が求められている。量子コンピュータにより容易に解くことが難しい問題としては、例えば、多変数多項式問題がある。
【0006】
多変数多項式問題に安全性の根拠をおく電子署名方式としては、例えば、MI(Matsumoto−Imai cryptography)、HFE(Hidden Field Equation cryptography)、OV(Oil−Vinegar signature scheme)、TTM(Tamed Transformation Method cryptography)に基づく方式が知られている。例えば、下記の非特許文献1、2には、HFEに基づく電子署名方式が開示されている。
【先行技術文献】
【非特許文献】
【0007】
【非特許文献1】Jacques Patarin Asymmetric Cryptography with a Hidden Monomial. CRYPTO 1996, pp.45−60.
【非特許文献2】Patarin, J., Courtois, N., and Goubin, L. QUARTZ, 128−Bit Long Digital Signatures. In Naccache,D., Ed. Topics in Cryptology − CT−RSA 2001 (San Francisco, CA, USA, April 2001), vol. 2020 of Lecture Notes in Computer Science, Springer−Verlag., pp.282−297.
【発明の概要】
【発明が解決しようとする課題】
【0008】
上記の通り、多変数多項式問題は、量子コンピュータを用いても解くことが困難なNP困難問題と呼ばれる問題の一例である。通常、HFEなどに代表される多変数多項式問題を利用した公開鍵認証方式は、特殊なトラップドアが仕込まれた多次多変数連立方程式を利用している。例えば、x,…,xに関する多次多変数連立方程式F(x,…,x)=yと線形変換A及びBが用意され、線形変換A及びBが秘密に管理される。この場合、多次多変数連立方程式F、線形変換A及びBがトラップドアとなる。
【0009】
トラップドアF,A,Bを知っているエンティティは、x,…,xに関する方程式B(F(A(x,…,x)))=y’を解くことができる。一方、トラップドアF,A,Bを知らないエンティティは、x,…,xに関する方程式B(F(A(x,…,x)))=y’を解くことができない。この仕組みを利用することにより、多次多変数連立方程式の解答困難性を安全性の根拠とする公開鍵認証方式や電子署名方式が実現される。
【0010】
上記の通り、こうした公開鍵認証方式や電子署名方式を実現するには、B(F(A(x,…,x)))=yを満たすような特殊な多次多変数連立方程式を用意する必要がある。また、署名生成時に多次多変数連立方程式Fを解く必要がある。そのため、利用可能な多次多変数連立方程式Fは、比較的容易に解けるものに限られていた。すなわち、これまでの方式においては、比較的容易に解ける3つの関数(トラップドア)B、F、Aを合成した形の多次多変数連立方程式B(F(A(x,…,x)))=yしか用いることができず、十分な安全性を確保することが難しかった。
【0011】
本技術は、上記の事情に鑑みて、効率的に解く手段(トラップドア)が知られていない多次多変数連立方程式を用いて高い安全性を有する効率的な公開鍵認証方式又は電子署名方式を実現することが可能な、新規かつ改良された情報処理装置、署名生成装置、署名検証装置、情報処理方法、署名生成方法、及び署名検証方法の提供を意図して考案されたものである。
【課題を解決するための手段】
【0012】
本技術のある観点によれば、環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及びベクトルs∈Kに基づいてメッセージを生成するメッセージ生成部と、前記2次多変数多項式の組F及びベクトルy=(y,…,y)=(f(s),…,f(s))を保持する検証者に前記メッセージを提供するメッセージ提供部と、k通り(k≧3)の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供部と、を備え、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージ生成部は、前記メッセージを生成する際、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算を式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行する、情報処理装置が提供される。
【0013】
また、本技術の別の観点によれば、環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及びベクトルy=(y,…,y)=(f(s),…,f(s))を保持する情報保持部と、前記2次多変数多項式の組F及びベクトルs∈Kに基づいて生成されたメッセージを取得するメッセージ取得部と、前記メッセージを提供した証明者に対し、k通り(k≧3)の検証パターンの中からランダムに選択した1つの検証パターンの情報を提供するパターン情報提供部と、前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得部と、前記メッセージ、前記2次多変数多項式の組F、前記ベクトルy、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証する検証部と、を備え、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記検証部は、前記検証に用いるメッセージを再生する際、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算を式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行する、情報処理装置が提供される。
【0014】
また、本技術の別の観点によれば、環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及びベクトルs∈Kに基づいてメッセージを生成するメッセージ生成部と、前記2次多変数多項式の組F及びベクトルy=(y,…,y)=(f(s),…,f(s))を保持する検証者に前記メッセージを提供するメッセージ提供部と、前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成する中間情報生成部と、前記検証者に前記第3の情報を提供する中間情報提供部と、k通り(k≧2)の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供部と、を備え、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージ生成部は、前記メッセージを生成する際、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算を式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行する、情報処理装置が提供される。
【0015】
また、本技術の別の観点によれば、環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及びベクトルy=(y,…,y)=(f(s),…,f(s))を保持する情報保持部と、前記2次多変数多項式の組F及びベクトルs∈Kに基づいて生成されたメッセージを取得するメッセージ取得部と、前記メッセージを提供した証明者に対し、ランダムに選択した第1の情報を提供する情報提供部と、前記第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて前記証明者が生成した第3の情報を取得する中間情報取得部と、k通り(k≧3)の検証パターンの中からランダムに選択した1つの検証パターンの情報を前記証明者に提供するパターン情報提供部と、前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得部と、前記メッセージ、前記第1の情報、前記第3の情報、前記2次多変数多項式の組F、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証する検証部と、を備え、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記検証部は、前記検証に用いるメッセージを再生する際、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算を式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行する、情報処理装置が提供される。
【0016】
また、本技術の別の観点によれば、環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及び署名鍵s∈Kを用いて文書Mに対する電子署名を生成する署名生成部と、前記2次多変数多項式の組F及びベクトルy=(f(s),…,f(s))を保持する検証者へと前記電子署名を提供する署名提供部と、を備え、前記署名生成部は、前記電子署名を生成する過程で実行する、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算を式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行する、署名生成装置が提供される。
【0017】
また、本技術の別の観点によれば、環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及びベクトルy=(f(s),…,f(s))を保持する情報保持部と、文書Mについて、前記2次多変数多項式の組F及び署名鍵s∈Kを用いて生成された電子署名に基づいて前記文書Mの正当性を検証する署名検証部と、を備え、前記署名検証部は、前記電子署名を検証する過程で実行する、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算を式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行する、署名検証装置が提供される。
【0018】
また、本技術の別の観点によれば、環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及びベクトルs∈Kに基づいてメッセージを生成するステップと、前記2次多変数多項式の組F及びベクトルy=(y,…,y)=(f(s),…,f(s))を保持する検証者に前記メッセージを提供するステップと、k通り(k≧3)の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供するステップと、を含み、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記生成するステップでは、前記メッセージを生成する際、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算が式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行される、情報処理方法が提供される。
【0019】
また、本技術の別の観点によれば、環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及びベクトルy=(y,…,y)=(f(s),…,f(s))を保持する情報処理装置が、前記2次多変数多項式の組F及びベクトルs∈Kに基づいて生成されたメッセージを取得するステップと、前記メッセージを提供した証明者に対し、k通り(k≧3)の検証パターンの中からランダムに選択した1つの検証パターンの情報を提供するステップと、前記選択した検証パターンに対応する回答情報を前記証明者から取得するステップと、前記メッセージ、前記2次多変数多項式の組F、前記ベクトルy、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証するステップと、を含み、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記検証するステップでは、前記検証に用いるメッセージを再生する際、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算が式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行される、情報処理方法が提供される。
【0020】
また、本技術の別の観点によれば、環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及びベクトルs∈Kに基づいてメッセージを生成するステップと、前記2次多変数多項式の組F及びベクトルy=(y,…,y)=(f(s),…,f(s))を保持する検証者に前記メッセージを提供するステップと、前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成するステップと、前記検証者に前記第3の情報を提供するステップと、k通り(k≧2)の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供するステップと、を含み、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージを生成するステップでは、前記メッセージを生成する際、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算が式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行される、情報処理方法が提供される。
【0021】
また、本技術の別の観点によれば、環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及びベクトルy=(y,…,y)=(f(s),…,f(s))を保持する情報処理装置が、前記2次多変数多項式の組F及びベクトルs∈Kに基づいて生成されたメッセージを取得するステップと、前記メッセージを提供した証明者に対し、ランダムに選択した第1の情報を提供するステップと、前記第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて前記証明者が生成した第3の情報を取得するステップと、k通り(k≧3)の検証パターンの中からランダムに選択した1つの検証パターンの情報を前記証明者に提供するステップと、前記選択した検証パターンに対応する回答情報を前記証明者から取得するステップと、前記メッセージ、前記第1の情報、前記第3の情報、前記2次多変数多項式の組F、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証するステップと、を含み、前記ベクトルsは秘密鍵であり、前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、前記検証するステップでは、前記検証に用いるメッセージを再生する際、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算が式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行される、情報処理方法が提供される。
【0022】
また、本技術の別の観点によれば、環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及び署名鍵s∈Kを用いて文書Mに対する電子署名を生成するステップと、前記2次多変数多項式の組F及びベクトルy=(f(s),…,f(s))を保持する検証者へと前記電子署名を提供するステップと、を含み、前記生成するステップでは、前記電子署名を生成する過程で実行される、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算が式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行される、署名生成方法が提供される。
【0023】
また、本技術の別の観点によれば、環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及びベクトルy=(f(s),…,f(s))を保持する情報処理装置が、文書Mについて、前記2次多変数多項式の組F及び署名鍵s∈Kを用いて生成された電子署名に基づいて前記文書Mの正当性を検証するステップを含み、前記検証するステップでは、前記電子署名を検証する過程で実行される、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算が式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行される、署名検証方法が提供される。
【0024】
また、本技術の別の観点によれば、上記の情報処理装置、署名生成装置、署名検証装置が有する各部の機能をコンピュータに実現させるためのプログラムが提供される。また、本技術の別の観点によれば、当該プログラムが記録された、コンピュータにより読み取り可能な記録媒体が提供される。
【0025】
また、本技術の別の観点によれば、上記のプログラムが記録された、コンピュータにより読み取り可能な記録媒体が提供される。
【発明の効果】
【0026】
以上説明したように本技術によれば、効率的に解く手段(トラップドア)が知られていない多次多変数連立方程式を用いて、高い安全性を有する効率的な公開鍵認証方式又は電子署名方式を実現することが可能になる。
【図面の簡単な説明】
【0027】
【図1】公開鍵認証方式に係るアルゴリズムの構成について説明するための説明図である。
【図2】電子署名方式に係るアルゴリズムの構成について説明するための説明図である。
【図3】nパスの公開鍵認証方式に係るアルゴリズムの構成について説明するための説明図である。
【図4】3パスの公開鍵認証方式に係る効率的なアルゴリズムについて説明するための説明図である。
【図5】3パスの公開鍵認証方式に係る効率的なアルゴリズムの並列化について説明するための説明図である。
【図6】5パスの公開鍵認証方式に係る効率的なアルゴリズムの構成例について説明するための説明図である。
【図7】5パスの公開鍵認証方式に係る効率的なアルゴリズムの並列化について説明するための説明図である。
【図8】3パスの公開鍵認証方式に係る効率的なアルゴリズムを電子署名方式のアルゴリズムに変形する方法について説明するための説明図である。
【図9】5パスの公開鍵認証方式に係る効率的なアルゴリズムを電子署名方式のアルゴリズムに変形する方法について説明するための説明図である。
【図10】本技術の各実施形態に係るアルゴリズムを実行することが可能な情報処理装置のハードウェア構成例について説明するための説明図である。
【発明を実施するための形態】
【0028】
以下に添付図面を参照しながら、本技術の好適な実施の形態について詳細に説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。
【0029】
[説明の流れについて]
ここで、以下に記載する本技術の実施形態に関する説明の流れについて簡単に述べる。まず、図1を参照しながら、公開鍵認証方式のアルゴリズム構成について説明する。次いで、図2を参照しながら、電子署名方式のアルゴリズム構成について説明する。次いで、図3を参照しながら、nパスの公開鍵認証方式について説明する。
【0030】
次いで、図4及び図5を参照しながら、3パスの公開鍵認証方式に係るアルゴリズムの構成例について説明する。次いで、図6及び図7を参照しながら、5パスの公開鍵認証方式に係るアルゴリズムの構成例について説明する。次いで、図8及び図9を参照しながら、3パス及び5パスの公開鍵認証方式に係る効率的なアルゴリズムを電子署名方式のアルゴリズムに変形する方法について説明する。
【0031】
次いで、図10を参照しながら、本技術の第1及び第2実施形態に係る各アルゴリズムを実現することが可能な情報処理装置のハードウェア構成例について説明する。最後に、本実施形態の技術的思想について纏め、当該技術的思想から得られる作用効果について簡単に説明する。
【0032】
(説明項目)
1:はじめに
1−1:公開鍵認証方式のアルゴリズム
1−2:電子署名方式のアルゴリズム
1−3:nパスの公開鍵認証方式
2:3パスの公開鍵認証方式に係るアルゴリズムの構成
2−1:具体的なアルゴリズムの構成例
2−2:並列化アルゴリズムの構成例
3:5パスの公開鍵認証方式に係るアルゴリズムの構成
3−1:具体的なアルゴリズムの構成例
3−2:並列化アルゴリズムの構成例
4:電子署名方式への変形
4−1:3パスの公開鍵認証方式から電子署名方式への変形
4−2:5パスの公開鍵認証方式から電子署名方式への変形
5:双線形項Gの効率的な計算方法
5−1:原理説明
5−2:適用例#1(3パス方式への適用)
5−3:適用例#2(5パス方式への適用)
5−4:適用例#3(電子署名方式への適用)
6:ハードウェア構成例
7:まとめ
【0033】
<1:はじめに>
本実施形態は、多次多変数連立方程式に対する求解問題の困難性に安全性の根拠をおく公開鍵認証方式及び電子署名方式に関する。但し、本実施形態は、HFE電子署名方式などの従来手法とは異なり、効率的に解く手段(トラップドア)を持たない多次多変数連立方程式を利用する公開鍵認証方式及び電子署名方式に関する。まず、公開鍵認証方式のアルゴリズム、電子署名方式のアルゴリズム、及びnパスの公開鍵認証方式について、その概要を簡単に説明する。
【0034】
[1−1:公開鍵認証方式のアルゴリズム]
まず、図1を参照しながら、公開鍵認証方式のアルゴリズムについて概要を説明する。図1は、公開鍵認証方式のアルゴリズムについて概要を説明するための説明図である。
【0035】
公開鍵認証は、ある人(証明者)が、公開鍵pk及び秘密鍵skを利用して、他の人(検証者)に本人であることを納得させるために利用される。例えば、証明者Aの公開鍵pkは、検証者Bに公開される。一方、証明者Aの秘密鍵skは、証明者Aにより秘密に管理される。公開鍵認証の仕組みにおいては、公開鍵pkに対応する秘密鍵skを知る者が証明者A本人であるとみなされる。
【0036】
公開鍵認証の仕組みを利用して証明者Aが証明者A本人であることを検証者Bに証明するには、対話プロトコルを介して、証明者Aが公開鍵pkに対応する秘密鍵skを知っているという証拠を検証者Bに提示すればよい。そして、証明者Aが秘密鍵skを知っているという証拠が検証者Bに提示され、その証拠を検証者Bが確認し終えた場合、証明者Aの正当性(本人であること)が証明されたことになる。
【0037】
但し、公開鍵認証の仕組みには、安全性を担保するために以下の条件が求められる。
【0038】
1つ目の条件は、「対話プロトコルを実行した際に秘密鍵skを持たない偽証者により偽証が成立してしまう確率を限りなく小さくする」ことである。この1つ目の条件が成り立つことを「健全性」と呼ぶ。つまり、健全性とは、「秘密鍵skを持たない偽証者により、対話プロトコルの実行中に無視できない確率で偽証が成立することはないこと」と言い換えられる。2つ目の条件は、「対話プロトコルを実行したとしても、証明者Aが有する秘密鍵skの情報が検証者Bに一切漏れることがない」ことである。この2つ目の条件が成り立つことを「零知識性」と呼ぶ。
【0039】
安全に公開鍵認証を行うには、健全性及び零知識性を有する対話プロトコルを利用する必要がある。仮に、健全性及び零知識性を有しない対話プロトコルを用いて認証処理を行った場合には、偽証された可能性及び秘密鍵の情報が漏れてしまった可能性が否定できないため、処理自体が成功裡に完了しても証明者の正当性を証明したことにはならない。従って、対話プロトコルの健全性及び零知識性を如何に保証するかが重要になる。
【0040】
(モデル)
公開鍵認証方式のモデルには、図1に示すように、証明者と検証者という2つのエンティティが存在する。証明者は、鍵生成アルゴリズムGenを用いて、証明者固有の秘密鍵skと公開鍵pkの組を生成する。次いで、証明者は、鍵生成アルゴリズムGenを用いて生成した秘密鍵skと公開鍵pkの組を利用して検証者と対話プロトコルを実行する。このとき、証明者は、証明者アルゴリズムPを利用して対話プロトコルを実行する。上記の通り、証明者は、証明者アルゴリズムPを利用し、対話プロトコルの中で秘密鍵skを保有している証拠を検証者に提示する。
【0041】
一方、検証者は、検証者アルゴリズムVを利用して対話プロトコルを実行し、証明者が公開している公開鍵に対応する秘密鍵を、その証明者が保有しているか否かを検証する。つまり、検証者は、証明者が公開鍵に対応する秘密鍵を保有しているか否かを検証するエンティティである。このように、公開鍵認証方式のモデルは、証明者と検証者という2つのエンティティ、及び、鍵生成アルゴリズムGen、証明者アルゴリズムP、検証者アルゴリズムVという3つのアルゴリズムにより構成される。
【0042】
なお、以下の説明において、「証明者」「検証者」という表現を用いるが、これらの表現はあくまでもエンティティを意味するものである。従って、鍵生成アルゴリズムGen、証明者アルゴリズムPを実行する主体は、「証明者」のエンティティに対応する情報処理装置である。同様に、検証者アルゴリズムVを実行する主体は、情報処理装置である。これら情報処理装置のハードウェア構成は、例えば、図10に示した通りである。つまり、鍵生成アルゴリズムGen、証明者アルゴリズムP、検証者アルゴリズムVは、ROM904、RAM906、記憶部920、リムーバブル記録媒体928などに記録されたプログラムに基づいてCPU902などにより実行される。
【0043】
(鍵生成アルゴリズムGen)
鍵生成アルゴリズムGenは、証明者により利用される。鍵生成アルゴリズムGenは、証明者に固有の秘密鍵skと公開鍵pkとの組を生成するアルゴリズムである。鍵生成アルゴリズムGenにより生成された公開鍵pkは公開される。そして、公開された公開鍵pkは、検証者により利用される。一方、鍵生成アルゴリズムGenにより生成された秘密鍵skは、証明者が秘密に管理する。そして、証明者により秘密に管理される秘密鍵skは、公開鍵pkに対応する秘密鍵skを証明者が保有していることを検証者に対して証明するために利用される。形式的に、鍵生成アルゴリズムGenは、セキュリティパラメータ1λ(λは0以上の整数)を入力とし、秘密鍵skと公開鍵pkを出力するアルゴリズムとして、下記の式(1)のように表現される。
【0044】
【数1】

【0045】
(証明者アルゴリズムP)
証明者アルゴリズムPは、証明者により利用される。証明者アルゴリズムPは、公開鍵pkに対応する秘密鍵skを証明者が保有していることを検証者に対して証明するためのアルゴリズムである。つまり、証明者アルゴリズムPは、秘密鍵skと公開鍵pkとを入力とし、対話プロトコルを実行するアルゴリズムである。
【0046】
(検証者アルゴリズムV)
検証者アルゴリズムVは、検証者により利用される。検証者アルゴリズムVは、対話プロトコルの中で、公開鍵pkに対応する秘密鍵skを証明者が保有しているか否かを検証するアルゴリズムである。検証者アルゴリズムVは、公開鍵pkを入力とし、対話プロトコルの実行結果に応じて0又は1(1bit)を出力するアルゴリズムである。なお、検証者は、検証者アルゴリズムVが0を出力した場合には証明者が不正なものであると判断し、1を出力した場合には証明者が正当なものであると判断する。形式的に、検証者アルゴリズムVは、下記の式(2)のように表現される。
【0047】
【数2】

【0048】
上記の通り、意味のある公開鍵認証を実現するには、対話プロトコルが健全性及び零知識性という2つの条件を満たしている必要がある。しかし、証明者が秘密鍵skを保有していることを証明するためには、証明者が秘密鍵skに依存した手続きを実行し、その結果を検証者に通知した上で、その通知内容に基づく検証を検証者に実行させる必要がある。秘密鍵skに依存した手続きを実行するのは、健全性を担保するために必要である。一方で、秘密鍵skの情報が一切検証者に漏れないようにする必要がある。そのため、これらの要件を満たすように、上記の鍵生成アルゴリズムGen、証明者アルゴリズムP、検証者アルゴリズムVを巧妙に設計する必要がある。
【0049】
以上、公開鍵認証方式のアルゴリズムについて、その概要を説明した。
【0050】
[1−2:電子署名方式のアルゴリズム]
次に、図2を参照しながら、電子署名方式のアルゴリズムについて概要を説明する。図2は、電子署名方式のアルゴリズムについて概要を説明するための説明図である。
【0051】
紙文書とは異なり、ある電子化されたデータに対して押印したり署名を記載したりすることはできない。そのため、電子化されたデータの作成者を証明するためには、紙文書に押印したり署名を記載したりするのと同等の効果が得られる電子的な仕組みを必要とする。この仕組みが電子署名である。電子署名とは、データの作成者しか知らない署名データをデータに関連付けて受領者に提供し、その署名データを受領者側で検証する仕組みのことを言う。
【0052】
(モデル)
電子署名方式のモデルには、図2に示すように、署名者及び検証者という2つのエンティティが存在する。そして、電子署名方式のモデルは、鍵生成アルゴリズムGen、署名生成アルゴリズムSig、署名検証アルゴリズムVerという3つのアルゴリズムにより構成される。
【0053】
署名者は、鍵生成アルゴリズムGenを利用して署名者固有の署名鍵skと検証鍵pkとの組を生成する。また、署名者は、署名生成アルゴリズムSigを利用して文書Mに付与する電子署名σを生成する。つまり、署名者は、文書Mに電子署名を付与するエンティティである。一方、検証者は、署名検証アルゴリズムVerを利用して文書Mに付与された電子署名σを検証する。つまり、検証者は、文書Mの作成者が署名者であるか否かを確認するために、電子署名σを検証するエンティティである。
【0054】
なお、以下の説明において、「署名者」「検証者」という表現を用いるが、これらの表現はあくまでもエンティティを意味するものである。従って、鍵生成アルゴリズムGen、署名生成アルゴリズムSigを実行する主体は、「署名者」のエンティティに対応する情報処理装置である。同様に、署名検証アルゴリズムVerを実行する主体は、情報処理装置である。これら情報処理装置のハードウェア構成は、例えば、図10に示した通りである。つまり、鍵生成アルゴリズムGen、署名生成アルゴリズムSig、署名検証アルゴリズムVerは、ROM904、RAM906、記憶部920、リムーバブル記録媒体928などに記録されたプログラムに基づいてCPU902などにより実行される。
【0055】
(鍵生成アルゴリズムGen)
鍵生成アルゴリズムGenは、署名者により利用される。鍵生成アルゴリズムGenは、署名者固有の署名鍵skと検証鍵pkとの組を生成するアルゴリズムである。鍵生成アルゴリズムGenにより生成された検証鍵pkは公開される。一方、鍵生成アルゴリズムGenにより生成された署名鍵skは、署名者により秘密に管理される。そして、署名鍵skは、文書Mに付与される電子署名σの生成に利用される。例えば、鍵生成アルゴリズムGenは、セキュリティパラメータ1λ(λは0以上の整数)を入力とし、署名鍵sk及び公開鍵pkを出力する。この場合、鍵生成アルゴリズムGenは、形式的に、下記の式(3)のように表現することができる。
【0056】
【数3】

【0057】
(署名生成アルゴリズムSig)
署名生成アルゴリズムSigは、署名者により利用される。署名生成アルゴリズムSigは、文書Mに付与される電子署名σを生成するアルゴリズムである。署名生成アルゴリズムSigは、署名鍵skと文書Mとを入力とし、電子署名σを出力するアルゴリズムである。この署名生成アルゴリズムSigは、形式的に、下記の式(4)のように表現することができる。
【0058】
【数4】

【0059】
(署名検証アルゴリズムVer)
署名検証アルゴリズムVerは、検証者により利用される。署名検証アルゴリズムVerは、電子署名σが文書Mに対する正当な電子署名であるか否かを検証するアルゴリズムである。署名検証アルゴリズムVerは、署名者の検証鍵pk、文書M、電子署名σを入力とし、0又は1(1bit)を出力するアルゴリズムである。この署名検証アルゴリズムVerは、形式的に、下記の式(5)のように表現することができる。なお、検証者は、署名検証アルゴリズムVerが0を出力した場合(公開鍵pkが文書Mと電子署名σを拒否する場合)に電子署名σが不当であると判断し、1を出力した場合(公開鍵pkが文書Mと電子署名σを受理する場合)に電子署名σが正当であると判断する。
【0060】
【数5】

【0061】
以上、電子署名方式のアルゴリズムについて、その概要を説明した。
【0062】
[1−3:nパスの公開鍵認証方式]
次に、図3を参照しながら、nパスの公開鍵認証方式について説明する。図3は、nパスの公開鍵認証方式について説明するための説明図である。
【0063】
上記の通り、公開鍵認証方式は、対話プロトコルの中で、証明者が公開鍵pkに対応する秘密鍵skを保有していることを検証者に証明する認証方式である。また、対話プロトコルは、健全性及び零知識性という2つの条件を満たす必要がある。そのため、対話プロトコルの中では、図3に示すように、証明者及び検証者の双方がそれぞれ処理を実行しながらn回の情報交換を行う。
【0064】
nパスの公開鍵認証方式の場合、証明者アルゴリズムPを用いて証明者により処理(工程#1)が実行され、情報Tが検証者に送信される。次いで、検証者アルゴリズムVを用いて検証者により処理(工程#2)が実行され、情報Tが証明者に送信される。さらに、k=3〜nについて処理の実行及び情報Tの送信が順次行われ、最後に処理(工程#n+1)が実行される。このように、情報がn回送受信される方式のことを「nパス」の公開鍵認証方式と呼ぶ。
【0065】
以上、nパスの公開鍵認証方式について説明した。
【0066】
<2:3パスの公開鍵認証方式に係るアルゴリズムの構成>
以下、3パスの公開鍵認証方式に係るアルゴリズムについて説明する。なお、以下の説明において、3パスの公開鍵認証方式のことを「3パス方式」と呼ぶ場合がある。
【0067】
[2−1:具体的なアルゴリズムの構成例(図4)]
まず、図4を参照しながら、3パス方式に係る具体的なアルゴリズムの構成例について紹介する。図4は、3パス方式に係る具体的なアルゴリズムの構成について説明するための説明図である。ここでは、公開鍵pkの一部として2次多項式の組(f(x),…,f(x))を利用する場合について考える。但し、2次多項式f(x)は、下記の式(6)のように表現されるものとする。また、ベクトル(x,…,x)をxと表記し、2次多項式の組(f(x),…,f(x))を多変数多項式F(x)と表記することにする。
【0068】
【数6】

【0069】
また、2次多項式の組(f(x),…,f(x))は、下記の式(7)のように表現することができる。また、A,…,Aは、n×n行列である。さらに、b,…,bはそれぞれn×1ベクトルである。
【0070】
【数7】

【0071】
この表現を用いると、多変数多項式Fは、下記の式(8)及び式(9)のように表現することができる。この表現が成り立つことは、下記の式(10)から容易に確認することができる。
【0072】
【数8】

【0073】
このようにF(x+y)をxに依存する第1の部分と、yに依存する第2の部分と、x及びyの両方に依存する第3の部分とに分けたとき、第3の部分に対応する項G(x,y)は、x及びyについて双線形になる。以下、項G(x,y)を双線形項と呼ぶ場合がある。この性質を利用すると、効率的なアルゴリズムを構築することが可能になる。
【0074】
例えば、ベクトルt∈K、e∈Kを用いて、多変数多項式F(x+r)のマスクに利用する多変数多項式F(x)をF(x)=G(x,t)+eと表現する。この場合、多変数多項式F(x+r)とG(x)との和は、下記の式(11)のように表現される。ここで、t=r+t、e=F(r)+eとおけば、多変数多項式F(x)=F(x+r)+F(x)は、ベクトルt∈K、e∈Kにより表現することができる。そのため、F(x)=G(x,t)+eに設定すれば、K上のベクトル及びK上のベクトルを用いてF及びFを表現できるようになり、通信に必要なデータサイズの少ない効率的なアルゴリズムを実現することが可能になる。
【0075】
【数9】

【0076】
なお、F(或いはF)からrに関する情報が一切漏れることはない。例えば、e及びt(或いはe及びt)を与えられても、e及びt(或いはe及びt)を知らない限り、rの情報を一切知ることはできない。従って、零知識性が担保される。以下、上記の論理に基づいて構築された3パス方式のアルゴリズムについて説明する。ここで説明する3パス方式のアルゴリズムは、以下のような鍵生成アルゴリズムGen、証明者アルゴリズムP、検証者アルゴリズムVにより構成される。
【0077】
(鍵生成アルゴリズムGen)
鍵生成アルゴリズムGenは、環K上で定義されるm本の多変数多項式f(x,…,x),…,f(x,…,x)、及びベクトルs=(s,…,s)∈Kを生成する。次に、鍵生成アルゴリズムGenは、y=(y,…,y)←(f(s),…,f(s))を計算する。そして、鍵生成アルゴリズムGenは、(f(x,…,x),…,f(x,…,x),y)を公開鍵pkに設定し、sを秘密鍵に設定する。
【0078】
(証明者アルゴリズムP、検証者アルゴリズムV)
以下、図4を参照しながら、対話プロトコルの中で証明者アルゴリズムPが実行する処理及び検証者アルゴリズムVが実行する処理について説明する。この対話プロトコルの中で、証明者は、秘密鍵sの情報を検証者に一切漏らさずに、「自身がy=F(s)を満たすsを知っていること」を検証者に示す。一方、検証者は、証明者がy=F(s)を満たすsを知っているか否かを検証する。なお、公開鍵pkは、検証者に公開されているものとする。また、秘密鍵sは、証明者により秘密に管理されているものとする。以下、図4に示したフローチャートに沿って説明を進める。
【0079】
工程#1:
図4に示すように、まず、証明者アルゴリズムPは、ランダムにベクトルr,t∈K及びe∈Kを生成する。次いで、証明者アルゴリズムPは、r←s−rを計算する。この計算は、秘密鍵sをベクトルrによりマスクする操作に相当する。さらに、証明者アルゴリズムPは、t←r−tを計算する。次いで、証明者アルゴリズムPは、e←F(r)−eを計算する。
【0080】
工程#1(続き):
次いで、証明者アルゴリズムPは、c←H(r,G(t,r)+e)を計算する。次いで、証明者アルゴリズムPは、c←H(t,e)を計算する。次いで、証明者アルゴリズムPは、c←H(t,e)を計算する。工程#1で生成されたメッセージ(c,c,c)は、検証者アルゴリズムVに送られる。
【0081】
工程#2:
メッセージ(c,c,c)を受け取った検証者アルゴリズムVは、3つの検証パターンのうち、どの検証パターンを利用するかを選択する。例えば、検証者アルゴリズムVは、検証パターンの種類を表す3つの数値{0,1,2}の中から1つの数値を選択し、選択した数値を要求Chに設定する。この要求Chは証明者アルゴリズムPに送られる。
【0082】
工程#3:
要求Chを受け取った証明者アルゴリズムPは、受け取った要求Chに応じて検証者アルゴリズムVに送る返答Rspを生成する。Ch=0の場合、証明者アルゴリズムPは、返答Rsp=(r,t,e)を生成する。Ch=1の場合、証明者アルゴリズムPは、返答Rsp=(r,t,e)を生成する。Ch=2の場合、証明者アルゴリズムPは、返答Rsp=(r,t,e)を生成する。工程#3で生成された返答Rspは、検証者アルゴリズムVに送られる。
【0083】
工程#4:
返答Rspを受け取った検証者アルゴリズムVは、受け取った返答Rspを利用して以下の検証処理を実行する。
【0084】
Ch=0の場合、検証者アルゴリズムVは、c=H(r−t,F(r)−e)の等号が成り立つか否かを検証する。さらに、検証者アルゴリズムVは、c=H(t,e)の等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。
【0085】
Ch=1の場合、検証者アルゴリズムVは、c=H(r,G(t,r)+e)の等号が成り立つか否かを検証する。さらに、検証者アルゴリズムVは、c=H(t,e)の等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。
【0086】
Ch=2の場合、検証者アルゴリズムVは、c=H(r,y−F(r)−G(t,r)−e)の等号が成り立つか否かを検証する。さらに、検証者アルゴリズムVは、c=H(t,e)の等号が成り立つか否かを検証する。検証者アルゴリズムVは、これらの検証が全て成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。
【0087】
以上、3パス方式に係る効率的なアルゴリズムの構成例について説明した。
【0088】
[2−2:並列化アルゴリズムの構成例(図5)]
次に、図5を参照しながら、図4に示した3パス方式のアルゴリズムを並列化する方法について説明する。なお、鍵生成アルゴリズムGenの構成については説明を省略する。
【0089】
さて、上記の対話プロトコルを適用すれば、偽証が成功する確率を2/3以下に抑制することができる。従って、この対話プロトコルを2回実行すれば、偽証が成功する確率を(2/3)以下に抑制することができる。さらに、この対話プロトコルをN回実行すると、偽証が成功する確率は(2/3)となり、Nを十分に大きい数(例えば、N=140)にすれば、偽証が成功する確率は無視できる程度に小さくなる。
【0090】
対話プロトコルを複数回実行する方法としては、例えば、メッセージ、要求、返答のやり取りを逐次的に複数回繰り返す直列的な方法と、1回分のやり取りで複数回分のメッセージ、要求、返答のやり取りを行う並列的な方法とが考えられる。さらに、直列的な方法と並列的な方法とを組み合わせたハイブリッド型の方法も考えられる。ここでは、図5を参照しながら、3パス方式に係る上記の対話プロトコルを並列的に実行するアルゴリズム(以下、並列化アルゴリズム)について説明する。
【0091】
工程#1:
図5に示すように、まず、証明者アルゴリズムPは、i=1〜Nについて以下の処理(1)〜処理(6)を実行する。
処理(1):証明者アルゴリズムPは、ランダムにベクトルr0i,t0i∈K及びe0i∈Kを生成する。
処理(2):証明者アルゴリズムPは、r1i←s−r0iを計算する。この計算は、秘密鍵sをベクトルr0iによりマスクする操作に相当する。さらに、証明者アルゴリズムPは、t1i←r0i+t0iを計算する。
処理(3):証明者アルゴリズムPは、e1i←F(r0i)−e0iを計算する。
処理(4):証明者アルゴリズムPは、c0i←H(r1i,G(r1i,t0i)+e0i)を計算する。
処理(5):証明者アルゴリズムPは、c1i←H(t0i,e0i)を計算する。
処理(6):証明者アルゴリズムPは、c2i←H(t1i,e1i)を計算する。
【0092】
工程#1(続き)
i=1〜Nについて上記の処理(1)〜処理(6)を実行した後、証明者アルゴリズムPは、Cmt←H(c01,c11,c21,…,c0N,c1N,c2N)を計算する。工程#1で生成されたハッシュ値Cmtは、検証者アルゴリズムVに送られる。このように、メッセージ(c01,c11,c21,…,c0N,c1N,c2N)をハッシュ値に変換してから検証者アルゴリズムVに送ることで、通信量を削減することが可能になる。
【0093】
工程#2:
ハッシュ値Cmtを受け取った検証者アルゴリズムVは、i=1〜Nのそれぞれについて、3つの検証パターンのうち、どの検証パターンを利用するかを選択する。例えば、検証者アルゴリズムVは、i=1〜Nのそれぞれについて、検証パターンの種類を表す3つの数値{0,1,2}の中から1つの数値を選択し、選択した数値を要求Chに設定する。要求Ch,…,Chは、証明者アルゴリズムPに送られる。
【0094】
工程#3:
要求Ch,…,Chを受け取った証明者アルゴリズムPは、受け取った要求Ch,…,Chのそれぞれ応じて検証者アルゴリズムVに送る返答Rsp,…,Rspを生成する。Ch=0の場合、証明者アルゴリズムPは、Rsp=(r0i,t1i,e1i,c0i)を生成する。Ch=1の場合、証明者アルゴリズムPは、Rsp=(r1i,t0i,e0i,c2i)を生成する。Ch=2の場合、証明者アルゴリズムPは、Rsp=(r1i,t1i,e1i,c1i)を生成する。
【0095】
工程#3で生成された返答Rsp,…,Rspは、検証者アルゴリズムVに送られる。
【0096】
工程#4:
返答Rsp,…,Rspを受け取った検証者アルゴリズムVは、受け取った返答Rsp,…,Rspを利用して以下の処理(1)〜処理(3)をi=1〜Nについて実行する。但し、検証者アルゴリズムVは、Ch=0の場合に処理(1)を実行し、Ch=1の場合に処理(2)を実行し、Ch=2の場合に処理(3)を実行する。
【0097】
処理(1):Ch=0の場合、検証者アルゴリズムVは、Rspから(r0i,t1i,e1i,c0i)を取り出す。次いで、検証者アルゴリズムVは、c1i=H(r0i−t1i,F(r0i)−e1i)を計算する。さらに、検証者アルゴリズムVは、c2i=H(t1i,e1i)を計算する。そして、検証者アルゴリズムVは、(c0i,c1i,c2i)を保持する。
【0098】
処理(2):Ch=1の場合、検証者アルゴリズムVは、Rspから(r1i,t0i,e0i,c2i)を取り出す。次いで、検証者アルゴリズムVは、c0i=H(r1i,G(t0i,r1i)+e0i)を計算する。さらに、検証者アルゴリズムVは、c1i=H(t0i,e0i)を計算する。そして、検証者アルゴリズムVは、(c0i,c1i,c2i)を保持する。
【0099】
処理(3):Ch=2の場合、検証者アルゴリズムVは、Rspから(r1i,t1i,e1i,c1i)を取り出す。次いで、検証者アルゴリズムVは、c0i=H(r1i,y−F(r1i)−G(t1i,r1i)−e1i)を計算する。さらに、検証者アルゴリズムVは、c2i=H(t1i,e1i)を計算する。そして、検証者アルゴリズムVは、(c0i,c1i,c2i)を保持する。
【0100】
処理(1)〜処理(3)をi=1〜Nについて実行した後、検証者アルゴリズムVは、Cmt=H(c01,c11,c21,…,c0N,c1N,c2N)の等号が成り立つか否かを検証する。検証者アルゴリズムVは、この検証が成功した場合に認証成功を示す値1を出力し、検証に失敗した場合に認証失敗を示す値0を出力する。
【0101】
以上、3パス方式に係る効率的な並列化アルゴリズムの構成例について説明した。
【0102】
<3:5パスの公開鍵認証方式に係るアルゴリズムの構成>
次に、5パスの公開鍵認証方式に係るアルゴリズムについて説明する。なお、以下の説明において、5パスの公開鍵認証方式のことを「5パス方式」と呼ぶ場合がある。
【0103】
3パス方式の場合には対話プロトコル1回当たりの偽証確率が2/3であったが、5パス方式の場合には対話プロトコル1回当たりの偽証確率が1/2+1/qとなる。但し、qは、利用する環の位数である。従って、環の位数が十分に大きい場合、5パス方式の方が1回当たりの偽証確率を低減することが可能になり、少ない対話プロトコルの実行回数で、偽証確率を十分に小さくすることができる。
【0104】
例えば、偽証確率を1/2以下にしたい場合、3パス方式においては、n/(log3−1)=1.701n回以上、対話プロトコルを実行する必要がある。一方、偽証確率を1/2以下にしたい場合、5パス方式においては、n/(1−log(1+1/q))回以上、対話プロトコルを実行する必要がある。従って、q=24にすれば、同じセキュリティレベルを実現するのに必要な通信量は、3パス方式に比べ、5パス方式の方が少なくなるのである。
【0105】
[3−1:具体的なアルゴリズムの構成例(図6)]
まず、図6を参照しながら、5パス方式に係る具体的なアルゴリズムの構成例について紹介する。図6は、5パス方式に係る具体的なアルゴリズムの構成について説明するための説明図である。ここでは、公開鍵pkの一部として2次多項式の組(f(x),…,f(x))を利用する場合について考える。但し、2次多項式f(x)は、上記の式(6)のように表現されるものとする。また、ベクトル(x,…,x)をxと表記し、2次多項式の組(f(x),…,f(x))を多変数多項式F(x)と表記することにする。
【0106】
3パス方式に係るアルゴリズムと同様、2つのベクトルt∈K、e∈Kを用いて、多変数多項式F(x+r)をマスクするために用いた多変数多項式F(x)をF(x)=G(x、t)+eのように表現する。この表現を用いると、多変数多項式F(x+r)について、下記の式(12)で表現される関係が得られる。
【0107】
【数10】

【0108】
そのため、t=Ch・r+t、e=Ch・F(r)+eとすれば、マスク後の多変数多項式F(x)=Ch・F(x+r)+F(x)も、2つのベクトルt∈K、e∈Kにより表現することができる。これらの理由から、F(x)=G(x,t)+eと設定すれば、K上のベクトル及びK上のベクトルを用いてF及びFを表現できるようになり、通信に必要なデータサイズが少ない効率的なアルゴリズムを実現することが可能になる。
【0109】
なお、F(或いはF)からrに関する情報が一切漏れることはない。例えば、e及びt(或いはe及びt)を与えられても、e及びt(或いはe及びt)を知らない限り、rの情報を一切知ることはできない。従って、零知識性は担保される。以下、上記の論理に基づいて構築された5パス方式のアルゴリズムについて説明する。ここで説明する5パス方式のアルゴリズムは、以下のような鍵生成アルゴリズムGen、証明者アルゴリズムP、検証者アルゴリズムVにより構成される。
【0110】
(鍵生成アルゴリズムGen)
鍵生成アルゴリズムGenは、環K上で定義される多変数多項式f(x,…,x),…,f(x,…,x)、及びベクトルs=(s,…,s)∈Kを生成する。次に、鍵生成アルゴリズムGenは、y=(y,…,y)←(f(s),…,f(s))を計算する。そして、鍵生成アルゴリズムGenは、(f,…,f,y)を公開鍵pkに設定し、sを秘密鍵に設定する。なお、以下では、ベクトル(x,…,x)をxと表記し、多変数多項式の組(f(x),…,f(x))をF(x)と表記する。
【0111】
(証明者アルゴリズムP、検証者アルゴリズムV)
以下、図6を参照しながら、対話プロトコルの中で証明者アルゴリズムP及び検証者アルゴリズムVにより実行される処理について説明する。この対話プロトコルの中で、証明者は、秘密鍵sの情報を検証者に一切漏らさずに、「自身がy=F(s)を満たすsを知っていること」を検証者に示す。一方、検証者は、証明者がy=F(s)を満たすsを知っているか否かを検証する。なお、公開鍵pkは、検証者に公開されているものとする。また、秘密鍵sは、証明者により秘密に管理されているものとする。以下、図6に示したフローチャートに沿って説明を進める。
【0112】
工程#1:
図6に示すように、まず、証明者アルゴリズムPは、ランダムにベクトルr∈K、t∈K、e∈Kを生成する。次いで、証明者アルゴリズムPは、r←s−rを計算する。この計算は、秘密鍵sをベクトルrによりマスクする操作に相当する。次いで、証明者アルゴリズムPは、ベクトルr,t,eのハッシュ値cを生成する。つまり、証明者アルゴリズムPは、c←H(r,t,e)を計算する。次いで、証明者アルゴリズムPは、G(t,r)+e及びrのハッシュ値cを生成する。つまり、証明者アルゴリズムPは、c←H(r,G(t,r)+e)を計算する。工程#1で生成されたメッセージ(c,c)は、検証者アルゴリズムVに送られる。
【0113】
工程#2:
メッセージ(c,c)を受け取った検証者アルゴリズムVは、q通り存在する環Kの元からランダムに1つの数Chを選択し、選択した数Chを証明者アルゴリズムPに送る。
【0114】
工程#3:
数Chを受け取った証明者アルゴリズムPは、t←Ch・r−tを計算する。さらに、証明者アルゴリズムPは、e←Ch・F(r)−eを計算する。そして、証明者アルゴリズムPは、t及びeを検証者アルゴリズムVに送る。
【0115】
工程#4:
及びeを受け取った検証者アルゴリズムVは、2つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。例えば、検証者アルゴリズムVは、検証パターンの種類を表す2つの数値{0,1}の中から1つの数値を選択し、選択した数値を要求Chに設定する。この要求Chは証明者アルゴリズムPに送られる。
【0116】
工程#5:
要求Chを受け取った証明者アルゴリズムPは、受け取った要求Chに応じて検証者アルゴリズムVに送り返す返答Rspを生成する。Ch=0の場合、証明者アルゴリズムPは、返答Rsp=rを生成する。Ch=1の場合、証明者アルゴリズムPは、返答Rsp=rを生成する。工程#5で生成された返答Rspは、検証者アルゴリズムVに送られる。
【0117】
工程#6:
返答Rspを受け取った検証者アルゴリズムVは、受け取った返答Rspを利用して以下の検証処理を実行する。
【0118】
Ch=0の場合、検証者アルゴリズムVは、r←Rspを実行する。そして、検証者アルゴリズムVは、c=H(r,Ch・r−t,Ch・F(r)−e)の等号が成り立つか否かを検証する。検証者アルゴリズムVは、この検証が成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。
【0119】
Ch=1の場合、検証者アルゴリズムVは、r←Rspを実行する。そして、検証者アルゴリズムVは、c=H(r,Ch・(y−F(r))−G(t,r)−e)の等号が成り立つか否かを検証する。検証者アルゴリズムVは、この検証が成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。
【0120】
以上、5パス方式に係る効率的なアルゴリズムの構成例について説明した。
【0121】
[3−2:並列化アルゴリズムの構成例(図7)]
次に、図7を参照しながら、図6に示した5パス方式のアルゴリズムを並列化する方法について説明する。なお、鍵生成アルゴリズムGenの構成については説明を省略する。
【0122】
先に述べた通り、5パス方式に係る対話プロトコルを適用すれば、偽証が成功する確率を(1/2+1/q)以下に抑制することができる。従って、この対話プロトコルを2回実行すれば、偽証が成功する確率を(1/2+1/q)以下に抑制することができる。さらに、この対話プロトコルをN回実行すると、偽証が成功する確率は(1/2+1/q)となり、Nを十分に大きい数(例えば、N=80)にすれば、偽証が成功する確率は無視できる程度に小さくなる。
【0123】
対話プロトコルを複数回実行する方法としては、例えば、メッセージ、要求、返答のやり取りを逐次的に複数回繰り返す直列的な方法と、1回分のやり取りで複数回分のメッセージ、要求、返答のやり取りを行う並列的な方法とが考えられる。さらに、直列的な方法と並列的な方法とを組み合わせたハイブリッド型の方法も考えられる。ここでは、5パス方式に係る上記の対話プロトコルを並列的に実行するアルゴリズム(以下、並列化アルゴリズム)について説明する。
【0124】
工程#1:
図7に示すように、まず、証明者アルゴリズムPは、i=1〜Nについて処理(1)〜処理(4)を実行する。
処理(1):証明者アルゴリズムPは、ランダムにベクトルr0i,t0i∈K及びe0i∈Kを生成する。
処理(2):証明者アルゴリズムPは、r1i←s−r0iを計算する。この計算は、秘密鍵sをベクトルr0iによりマスクする操作に相当する。
処理(3):証明者アルゴリズムPは、c0i←H(r0i,t0i,e0i)を計算する。
処理(4):証明者アルゴリズムPは、c1i←H(r1i,G(t0i,r1i)+e0i)を計算する。
i=1〜Nについて処理(1)〜処理(4)を実行した後、証明者アルゴリズムPは、ハッシュ値Cmt←H(c01,c11,…,c0N,c1N)を実行する。そして、工程#1で生成されたハッシュ値Cmtは、検証者アルゴリズムVに送られる。
【0125】
工程#2:
ハッシュ値Cmtを受け取った検証者アルゴリズムVは、i=1〜Nのそれぞれについて、q通り存在する環Kの元からランダムに1つの数ChAiを選択し、選択した数ChAi(i=1〜N)を証明者アルゴリズムPに送る。
【0126】
工程#3:
数ChAi(i=1〜N)を受け取った証明者アルゴリズムPは、i=1〜Nのそれぞれについて、t1i←ChAi・r0i−t0iを計算する。さらに、証明者アルゴリズムPは、i=1〜Nのそれぞれについて、e1i←ChAi・F(r0i)−e0iを計算する。そして、証明者アルゴリズムPは、t11,…,t1N及びe11,…,e1Nを検証者アルゴリズムVに送る。
【0127】
工程#4:
11,…,t1N及びe11,…,e1Nを受け取った検証者アルゴリズムVは、i=1〜Nのそれぞれについて、2つの検証パターンのうち、どちらの検証パターンを利用するかを選択する。例えば、検証者アルゴリズムVは、検証パターンの種類を表す2つの数値{0,1}の中から1つの数値を選択し、選択した数値を要求ChBiに設定する。要求ChBi(i=1〜N)は証明者アルゴリズムPに送られる。
【0128】
工程#5:
要求ChBi(i=1〜N)を受け取った証明者アルゴリズムPは、i=1〜Nについて、受け取った要求ChBiに応じて検証者アルゴリズムVに送り返す返答Rspを生成する。ChBi=0の場合、証明者アルゴリズムPは、返答Rsp=(r0i,c1i)を生成する。ChBi=1の場合、証明者アルゴリズムPは、返答Rsp=(r1i,c0i)を生成する。工程#5で生成された返答Rsp(i=1〜N)は、検証者アルゴリズムVに送られる。
【0129】
工程#6:
返答Rsp(i=1〜N)を受け取った検証者アルゴリズムVは、受け取った返答Rsp(i=1〜N)を利用して以下の処理(1)及び処理(2)を実行する。
【0130】
処理(1):ChBi=0の場合、検証者アルゴリズムVは、(r0i,c1i)←Rspを実行する。そして、検証者アルゴリズムVは、c0i=H(r0i,ChAi・r0i−t1i,ChAi・F(r0i)−e1i)を計算する。そして、検証者アルゴリズムVは、(c0i,c1i)を保持する。
【0131】
処理(2):ChBi=1の場合、検証者アルゴリズムVは、(r1i,c0i)←Rspを実行する。そして、検証者アルゴリズムVは、c1i=H(r1i,ChAi・(y−F(r1i))−G(t1i,r1i)−e1i)を計算する。そして、検証者アルゴリズムVは、(c0i,c1i)を保持する。
【0132】
i=1〜Nについて処理(1)及び処理(2)を実行した後、検証者アルゴリズムVは、Cmt=H(c01,c11,…,c0N,c1N)の等号が成り立つか否かを検証する。検証者アルゴリズムVは、この検証が成功した場合に認証成功を示す値1を出力し、検証に失敗があった場合に認証失敗を示す値0を出力する。
【0133】
以上、5パス方式に係る効率的な並列化アルゴリズムの構成例について説明した。
【0134】
<4:電子署名方式への変形>
次に、上記の公開鍵認証方式を電子署名方式へと変形する方法を紹介する。
【0135】
公開鍵認証方式のモデルにおける証明者を電子署名方式における署名者に対応させると、証明者のみが検証者を納得させられるという点において、電子署名方式のモデルと近似していることが容易に理解されよう。こうした考えに基づき、上述した公開鍵認証方式を電子署名方式へと変形する方法について説明する。
【0136】
[4−1:3パスの公開鍵認証方式から電子署名方式への変形(図8)]
まず、3パスの公開鍵認証方式から電子署名方式への変形について説明する。
【0137】
図8に示すように、3パス方式に係る効率的なアルゴリズム(例えば、図5を参照)は、3回の対話及び4つの工程#1〜工程#4で表現される。
【0138】
工程#1は、i=1〜Nについて、a=(r0i,t0i,e0i,r1i,t1i,e1i,c0i,c1i,c2i)を生成する処理(1)と、Cmt←H(c01,c11,c21,…,c0N,c1N,c2N)を計算する処理(2)とで構成される。工程#1で証明者アルゴリズムPにより生成されたCmtは、検証者アルゴリズムVへと送られる。
【0139】
工程#2は、Ch,…,Chを選択する処理で構成される。工程#2で検証者アルゴリズムVにより選択されたCh,…,Chは、証明者アルゴリズムPへと送られる。
【0140】
工程#3は、Ch,…,Ch及びa,…,aを用いてRsp,…,Rspを生成する処理で構成される。この処理をRsp←Select(Ch,a)と表現する。工程#3で証明者アルゴリズムPにより生成されたRsp,…,Rspは、検証者アルゴリズムVへと送られる。
【0141】
工程#4は、Ch,…,Ch及びRsp,…,Rspを用いてc01,c11,c21,…,c0N,c1N,c2Nを再生する処理(1)と、再生したc01,c11,c21,…,c0N,c1N,c2Nを用いてCmt=H(c01,c11,c21,…,c0N,c1N,c2N)を検証する処理(2)とで構成される。
【0142】
上記の工程#1〜工程#4で表現される公開鍵認証方式のアルゴリズムは、図8に示すような署名生成アルゴリズムSig及び署名検証アルゴリズムVerに変形される。
【0143】
(署名生成アルゴリズムSig)
まず、署名生成アルゴリズムSigの構成について述べる。署名生成アルゴリズムSigは、以下の処理(1)〜処理(5)で構成される。
【0144】
処理(1):署名生成アルゴリズムSigは、a=(r0i,t0i,e0i,r1i,t1i,e1i,c0i,c1i,c2i)を生成する。
処理(2):署名生成アルゴリズムSigは、Cmt←H(c01,c11,c21,…,c0N,c1N,c2N)を計算する。
処理(3):署名生成アルゴリズムSigは、(Ch,…,Ch)←H(M,Cmt)を計算する。このMは、署名を付与する文書である。
処理(4):署名生成アルゴリズムSigは、Rsp←Select(Chi,)を計算する。
処理(5):署名生成アルゴリズムSigは、(Cmt,Rsp,…,Rsp)を署名に設定する。
【0145】
(署名検証アルゴリズムVer)
次に、署名検証アルゴリズムVerの構成について述べる。署名検証アルゴリズムVerは、以下の処理(1)〜処理(3)で構成される。
【0146】
処理(1):署名検証アルゴリズムVerは、(Ch,…,Ch)←H(M,Cmt)を計算する。
処理(2):署名検証アルゴリズムVerは、Ch,…,Ch及びRsp,…,Rspを用いてc01,c11,c21,…,c0N,c1N,c2Nを生成する。
処理(3):署名検証アルゴリズムVerは、再生したc01,c11,c21,…,c0N,c1N,c2Nを用いてCmt=H(c01,c11,c21,…,c0N,c1N,c2N)を検証する。
【0147】
以上説明したように、公開鍵認証方式のモデルにおける証明者を電子署名方式における署名者に対応させることで、公開鍵認証方式のアルゴリズムを電子署名方式のアルゴリズムへと変形することが可能になる。
【0148】
[4−2:5パスの公開鍵認証方式から電子署名方式への変形(図9)]
次に、5パスの公開鍵認証方式から電子署名方式への変形について説明する。
【0149】
図9に示すように、5パス方式に係る効率的なアルゴリズム(例えば、図7を参照)は、5回の対話及び6つの工程#1〜工程#6で表現される。
【0150】
工程#1は、i=1〜Nについて、a=(r0i,t0i,e0i,r1i,t1i,e1i,c0i,c1i)を生成する処理(1)と、Cmt←H(c01,c11,…,c0N,c1N)を計算する処理(2)とで構成される。工程#1で証明者アルゴリズムPにより生成されたCmtは、検証者アルゴリズムVへと送られる。
【0151】
工程#2は、ChA1,…,ChANを選択する処理で構成される。工程#2で検証者アルゴリズムVにより選択されたChA1,…,ChANは、証明者アルゴリズムPへと送られる。
【0152】
工程#3は、i=1〜Nについて、b=(t1i,e1i)を生成する処理で構成される。工程#3で証明者アルゴリズムPにより生成されたb,…,bは、検証者アルゴリズムVへと送られる。
【0153】
工程#4は、ChB1,…,ChBNを選択する処理で構成される。工程#4で検証者アルゴリズムVにより選択されたChB1,…,ChBNは、証明者アルゴリズムPへと送られる。
【0154】
工程#5は、ChB1,…,ChBN,a,…,a,b,…,bを用いてRsp,…,Rspを生成する処理で構成される。この処理をRsp←Select(ChBi,a,b)と表現する。工程#5で証明者アルゴリズムPにより生成されたRsp,…,Rspは、検証者アルゴリズムVへと送られる。
【0155】
工程#6は、ChA1,…,ChAN,ChB1,…,ChBN,Rsp,…,Rspを用いてc01,c11,…,c0N,c1Nを再生する処理(1)と、再生したc01,c11,…,c0N,c1Nを用いてCmt=H(c01,c11,…,c0N,c1N)を検証する処理(2)とで構成される。
【0156】
上記の工程#1〜工程#6で表現される公開鍵認証方式のアルゴリズムは、図9に示すような署名生成アルゴリズムSig及び署名検証アルゴリズムVerに変形される。
【0157】
(署名生成アルゴリズムSig)
まず、署名生成アルゴリズムSigの構成について述べる。署名生成アルゴリズムSigは、以下の処理(1)〜処理(7)で構成される。
【0158】
処理(1):署名生成アルゴリズムSigは、a=(r0i,t0i,e0i,r1i,t1i,e1i,c0i,c1i)を生成する。
処理(2):署名生成アルゴリズムSigは、Cmt←H(c01,c11,…,c0N,c1N)を計算する。
処理(3):署名生成アルゴリズムSigは、(ChA1,…,ChAN)←H(M,Cmt)を計算する。このMは、署名を付与する文書である。
処理(4):署名生成アルゴリズムSigは、i=1〜Nについて、b=(t1i,e1i)を生成する。
処理(5):署名生成アルゴリズムSigは、(ChB1,…,ChBN)←H(M,Cmt,ChA1,…,ChAN,b,…,b)を計算する。なお、(ChB1,…,ChBN)←H(ChA1,…,ChAN,b,…,b)と変形してもよい。
処理(6):署名生成アルゴリズムSigは、Rsp←Select(ChBi,a,b)を計算する。
処理(7):署名生成アルゴリズムSigは、(Cmt,b,…,b,Rsp,…,Rsp)を電子署名に設定する。
【0159】
(署名検証アルゴリズムVer)
次に、署名検証アルゴリズムVerの構成について述べる。署名検証アルゴリズムVerは、以下の処理(1)〜処理(4)で構成される。
【0160】
処理(1):署名検証アルゴリズムVerは、(ChA1,…,ChAN)←H(M,Cmt)を計算する。
処理(2):署名検証アルゴリズムVerは、(ChB1,…,ChBN)←H(M,Cmt,ChA1,…,ChAN,b,…,b)を計算する。なお、署名検証アルゴリズムVerが実行する処理(5)において、(ChB1,…,ChBN)←H(ChA1,…,ChAN,b,…,b)と変形した場合、署名検証アルゴリズムVerは、(ChB1,…,ChBN)←H(ChA1,…,ChAN,b,…,b)を計算する。
処理(3):署名検証アルゴリズムVerは、ChA1,…,ChAN,ChB1,…,ChBN,Rsp,…,Rspを用いてc01,c11,…,c0N,c1Nを生成する。
処理(4):署名検証アルゴリズムVerは、再生したc01,c11,…,c0N,c1Nを用いてCmt=H(c01,c11,…,c0N,c1N)を検証する。
【0161】
以上説明したように、公開鍵認証方式のモデルにおける証明者を電子署名方式における署名者に対応させることで、公開鍵認証方式のアルゴリズムを電子署名方式のアルゴリズムへと変形することが可能になる。
【0162】
<5:双線形項Gの効率的な計算方法>
ところで、上記の公開鍵認証方式及び電子署名方式に係るアルゴリズムには、下記の式(13)で定義される双線形項Gの演算が含まれる。例えば、3パス方式のアルゴリズム(図4及び図5を参照)においては、工程#1及び工程#4の中に双線形項Gの演算が含まれる。また、5パス方式のアルゴリズム(図6及び図7を参照)においては、工程#1及び工程#6の中に双線形項Gの演算が含まれる。さらに、これらの公開鍵認証方式のアルゴリズムを変形して得られる電子署名方式のアルゴリズムにも、同様に双線形項Gの演算が含まれる。
【0163】
【数11】

【0164】
上記の式(13)から分かるように、双線形項Gの値を得るには、多変数多項式Fの演算を3回実行することが必要になる。また、多変数多項式Fはm本の2次多項式f(l=1,…,m)で構成されているため、多変数多項式Fの値を得るには、2次多項式fを実行するのに要する演算量のm倍の演算量(以下、演算量Z)が必要になる。つまり、双線形項Gの値を得るのに要する演算量は3×Z以上となる。ここでは、双線形項Gの値を得るのに要する演算量を3×Zよりも少なくする方法について説明する。
【0165】
[5−1:原理説明]
2次多項式f(x+y)は、下記の式(14)に示すように展開することができる。従って、双線形項G=(g,…,g)の要素g(x,y)は、下記の式(15)のようになる。下記の式(15)から分かるように、要素g(x,y)は、2つの2次多項式で構成されている。そのため、下記の式(15)に示した展開式に基づいて双線形項Gを演算することにより、双線形項Gの演算量を2×Z程度に抑制することが可能になる。
【0166】
【数12】

【0167】
また、上記の式(6)の右辺第2項(xに関する1次の項)を省略した形(下記の式(16)を参照)で2次多項式fを定義すると、f及びgは、下記の式(17)の表現を用いて、下記の式(18)及び式(19)のように表現することができる。この表現を用いると、関数w(x,y)を計算する演算モジュールを用意し、その演算モジュールを繰り返し利用して双線形項Gや多変数多項式Fを計算することが可能になる。例えば、この演算モジュールをハードウェア又はソフトウェアで実装し、実装した演算モジュールを利用してアルゴリズムを実行することが可能になる。
【0168】
【数13】

【0169】
以上、双線形項Gの効率的な計算方法の原理を説明した。なお、ここでは2次多項式fを上記の式(16)のように定義する方法について説明したが、本実施形態に係る技術の適用範囲はこれに限定されず、上記の式(6)に示した定義をそのまま用いてもよい。この場合、上記の式(19)にxに関する1次の項が現れる。但し、以下の説明においては、2次多項式fを上記の式(16)のように定義することを前提に説明を進める。
【0170】
[5−2:適用例#1(3パス方式への適用)]
まず、3パス方式のアルゴリズムに対する具体的な適用方法について説明する。
【0171】
(単純な適用例)
図4を参照すると、工程#1において、メッセージcを算出する際に、双線形項G(t,r)の演算が登場する。そこで、証明者アルゴリズムPは、g(t,r)=w(t,r)+w(r,t)を用いて双線形項G(t,r)を計算する。また、工程#4において、Ch=1の場合に双線形項G(t,r)の演算が登場し、Ch=2の場合に双線形項G(t,r)の演算が登場する。そこで、検証者アルゴリズムVは、Ch=1の場合にg(t,r)=w(t,r)+w(r,t)を用いて双線形項G(t,r)を計算し、Ch=2の場合にg(t,r)=w(t,r)+w(r,t)を用いて双線形項G(t,r)を計算する。この方法を適用すると、双線形項Gの計算に要する演算量は2×Z程度に抑制される。
【0172】
(効率的な適用例)
上記の方法を用いることにより、双線形項Gの演算を効率的に実行することが可能になる。但し、工程#4において、Ch=2の場合に計算すべき項(y−F(r)−G(t,r)−e)に注目すると、より効率的に演算を実行する方法に気づくであろう。上記の式(13)の定義に従うと、F(r)+G(t,r)=F(t+r)−F(t)となる。従って、左辺を単純に計算すると、1×Z+3×Z=4×Z程度の演算量となるが、右辺を参照すると分かるように、この変形により2×Z程度の演算量に削減される。
【0173】
なお、演算モジュールw(x,y)の具体的な適用方法については、下記の式(20)に示すように何通りかの方法が考えられる。いずれの方法を用いても、F(r)+G(t,r)の計算に要する演算量は2×Z程度となる。
【0174】
【数14】

【0175】
以上、3パス方式のアルゴリズムに対する具体的な適用方法について説明した。なお、ここでは、図4に示したアルゴリズムを参考に説明を行ったが、図5に示した並列化アルゴリズム又はこれらのアルゴリズムを変形したアルゴリズムに対しても同様に適用することが可能である。
【0176】
[5−3:適用例#2(5パス方式への適用)]
次に、5パス方式のアルゴリズムに対する具体的な適用方法について説明する。
【0177】
図6を参照すると、工程#1において、メッセージcを算出する際に、双線形項G(t,r)の演算が登場する。そこで、証明者アルゴリズムPは、g(t,r)=w(t,r)+w(r,t)を用いて双線形項G(t,r)を計算する。また、工程#6において、Ch=1の場合に双線形項G(t,r)の演算が登場する。そこで、検証者アルゴリズムVは、Ch=1の場合にg(t,r)=w(t,r)+w(r,t)を用いて双線形項G(t,r)を計算する。この方法を適用すると、双線形項Gの計算に要する演算量は2×Z程度に抑制される。
【0178】
以上、5パス方式のアルゴリズムに対する具体的な適用方法について説明した。なお、ここでは、図6に示したアルゴリズムを参考に説明を行ったが、図7に示した並列化アルゴリズム又はこれらのアルゴリズムを変形したアルゴリズムに対しても同様に適用することが可能である。
【0179】
[5−4:適用例#3(電子署名方式への適用)]
次に、電子署名方式のアルゴリズムに対する具体的な適用方法について説明する。
【0180】
(3パス方式に基づく電子署名方式への適用)
図8に示した電子署名方式のアルゴリズムは、図5に示した3パス方式の並列化アルゴリズムに基づくアルゴリズムである。従って、署名生成アルゴリズムSigがメッセージc0iを算出する際に、双線形項G(t0i,r1i)の演算が登場する。そこで、署名生成アルゴリズムSigは、g(t0i,r1i)=w(t0i,r1i)+w(r1i,t0i)を用いて双線形項G(t0i,r1i)を計算する。
【0181】
また、署名検証アルゴリズムVerがメッセージc0iを算出する際に、双線形項G(t0i,r1i)や双線形項G(t1i,r1i)の演算が登場する。そこで、署名検証アルゴリズムVerは、g(t0i,r1i)=w(t0i,r1i)+w(r1i,t0i)を用いて双線形項G(t0i,r1i)を計算し、g(t1i,r1i)=w(t1i,r1i)+w(r1i,t1i)を用いて双線形項G(t1i,r1i)を計算する。この方法を適用すると、双線形項Gの計算に要する演算量は2×Z程度に抑制される。
【0182】
また、署名検証アルゴリズムVerがメッセージc0iを算出する際に実行するF(r1i)+G(t1i,r1i)の演算に注目し、上記の式(20)に基づいて演算を実行することにより、演算量をさらに削減することが可能になる。
【0183】
(5パス方式に基づく電子署名方式への適用)
図9に示した電子署名方式のアルゴリズムは、図7に示した5パス方式の並列化アルゴリズムに基づくアルゴリズムである。従って、署名生成アルゴリズムSigがメッセージc1iを算出する際に、双線形項G(t0i,r1i)の演算が登場する。そこで、署名生成アルゴリズムSigは、g(t0i,r1i)=w(t0i,r1i)+w(r1i,t0i)を用いて双線形項G(t0i,r1i)を計算する。また、署名検証アルゴリズムVerがメッセージc1iを再生する際に、双線形項G(t1i,r1i)の演算が登場する。そこで、署名検証アルゴリズムVerは、g(t,r)=w(t,r)+w(r,t)を用いて双線形項G(t,r)を計算する。この方法を適用すると、双線形項Gの計算に要する演算量は2×Z程度に抑制される。
【0184】
以上、電子署名方式のアルゴリズムに対する具体的な適用方法について説明した。なお、ここでは、図8及び図9に示したアルゴリズムを参考に説明を行ったが、これらのアルゴリズムを変形したアルゴリズムに対しても同様に適用することが可能である。
【0185】
以上、双線形項Gの効率的な計算方法について説明した。
【0186】
<6:ハードウェア構成例>
上記の各アルゴリズムは、例えば、図10に示す情報処理装置のハードウェア構成を用いて実行することが可能である。つまり、当該各アルゴリズムの処理は、コンピュータプログラムを用いて図10に示すハードウェアを制御することにより実現される。なお、このハードウェアの形態は任意であり、例えば、パーソナルコンピュータ、携帯電話、PHS、PDA等の携帯情報端末、ゲーム機、接触式又は非接触式のICチップ、接触式又は非接触式のICカード、又は種々の情報家電がこれに含まれる。但し、上記のPHSは、Personal Handy−phone Systemの略である。また、上記のPDAは、Personal Digital Assistantの略である。
【0187】
図10に示すように、このハードウェアは、主に、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の略である。
【0188】
CPU902は、例えば、演算処理装置又は制御装置として機能し、ROM904、RAM906、記憶部920、又はリムーバブル記録媒体928に記録された各種プログラムに基づいて各構成要素の動作全般又はその一部を制御する。ROM904は、CPU902に読み込まれるプログラムや演算に用いるデータ等を格納する手段である。RAM906には、例えば、CPU902に読み込まれるプログラムや、そのプログラムを実行する際に適宜変化する各種パラメータ等が一時的又は永続的に格納される。
【0189】
これらの構成要素は、例えば、高速なデータ伝送が可能なホストバス908を介して相互に接続される。一方、ホストバス908は、例えば、ブリッジ910を介して比較的データ伝送速度が低速な外部バス912に接続される。また、入力部916としては、例えば、マウス、キーボード、タッチパネル、ボタン、スイッチ、及びレバー等が用いられる。さらに、入力部916としては、赤外線やその他の電波を利用して制御信号を送信することが可能なリモートコントローラ(以下、リモコン)が用いられることもある。
【0190】
出力部918としては、例えば、CRT、LCD、PDP、又はELD等のディスプレイ装置、スピーカ、ヘッドホン等のオーディオ出力装置、プリンタ、携帯電話、又はファクシミリ等、取得した情報を利用者に対して視覚的又は聴覚的に通知することが可能な装置である。但し、上記のCRTは、Cathode Ray Tubeの略である。また、上記のLCDは、Liquid Crystal Displayの略である。そして、上記のPDPは、Plasma DisplayPanelの略である。さらに、上記のELDは、Electro−Luminescence Displayの略である。
【0191】
記憶部920は、各種のデータを格納するための装置である。記憶部920としては、例えば、ハードディスクドライブ(HDD)等の磁気記憶デバイス、半導体記憶デバイス、光記憶デバイス、又は光磁気記憶デバイス等が用いられる。但し、上記のHDDは、Hard Disk Driveの略である。
【0192】
ドライブ922は、例えば、磁気ディスク、光ディスク、光磁気ディスク、又は半導体メモリ等のリムーバブル記録媒体928に記録された情報を読み出し、又はリムーバブル記録媒体928に情報を書き込む装置である。リムーバブル記録媒体928は、例えば、DVDメディア、Blu−rayメディア、HD DVDメディア、各種の半導体記憶メディア等である。もちろん、リムーバブル記録媒体928は、例えば、非接触型ICチップを搭載したICカード、又は電子機器等であってもよい。但し、上記のICは、Integrated Circuitの略である。
【0193】
接続ポート924は、例えば、USBポート、IEEE1394ポート、SCSI、RS−232Cポート、又は光オーディオ端子等のような外部接続機器930を接続するためのポートである。外部接続機器930は、例えば、プリンタ、携帯音楽プレーヤ、デジタルカメラ、デジタルビデオカメラ、又はICレコーダ等である。但し、上記のUSBは、Universal Serial Busの略である。また、上記のSCSIは、Small Computer System Interfaceの略である。
【0194】
通信部926は、ネットワーク932に接続するための通信デバイスであり、例えば、有線又は無線LAN、Bluetooth(登録商標)、又はWUSB用の通信カード、光通信用のルータ、ADSL用のルータ、又は接触又は非接触通信用のデバイス等である。また、通信部926に接続されるネットワーク932は、有線又は無線により接続されたネットワークにより構成され、例えば、インターネット、家庭内LAN、赤外線通信、可視光通信、放送、又は衛星通信等である。但し、上記のLANは、Local Area Networkの略である。また、上記のWUSBは、Wireless USBの略である。そして、上記のADSLは、Asymmetric Digital Subscriber Lineの略である。
【0195】
<7:まとめ>
最後に、本技術の実施形態に係る技術内容について簡単に纏める。ここで述べる技術内容は、例えば、PC、携帯電話、ゲーム機、情報端末、情報家電、カーナビゲーションシステム等、種々の情報処理装置に対して適用することができる。なお、以下で述べる情報処理装置の機能は、1台の情報処理装置を利用して実現することも可能であるし、複数台の情報処理装置を利用して実現することも可能である。また、以下で述べる情報処理装置が処理を実行する際に用いるデータ記憶手段及び演算処理手段は、当該情報処理装置に設けられたものであってもよいし、ネットワークを介して接続された機器に設けられたものであってもよい。
【0196】
上記の情報処理装置の機能構成は以下のように表現される。例えば、下記(1)に記載の情報処理装置は、多次多変数連立方程式の求解困難性に安全性の根拠を置く効率的な公開鍵認証方式又は電子署名方式のアルゴリズムを実行する機能を有する。
【0197】
(1)
環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及びベクトルs∈Kに基づいてメッセージを生成するメッセージ生成部と、
前記2次多変数多項式の組F及びベクトルy=(y,…,y)=(f(s),…,f(s))を保持する検証者に前記メッセージを提供するメッセージ提供部と、
k通り(k≧3)の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供部と、
を備え、
前記ベクトルsは秘密鍵であり、
前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記メッセージ生成部は、前記メッセージを生成する際、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算を式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行する、
情報処理装置。
【0198】
(2)
前記メッセージ生成部は、N回分(N≧2)のメッセージを生成し、
前記メッセージ提供部は、N回分の前記メッセージを1回の対話で前記検証者に提供し、
前記回答提供部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した検証パターンに対応するN回分の前記回答情報を1回の対話で前記検証者に提供する、
上記(1)に記載の情報処理装置。
【0199】
(3)
環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及びベクトルy=(y,…,y)=(f(s),…,f(s))を保持する情報保持部と、
前記2次多変数多項式の組F及びベクトルs∈Kに基づいて生成されたメッセージを取得するメッセージ取得部と、
前記メッセージを提供した証明者に対し、k通り(k≧3)の検証パターンの中からランダムに選択した1つの検証パターンの情報を提供するパターン情報提供部と、
前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得部と、
前記メッセージ、前記2次多変数多項式の組F、前記ベクトルy、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証する検証部と、
を備え、
前記ベクトルsは秘密鍵であり、
前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記検証部は、前記検証に用いるメッセージを再生する際、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算を式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行する、
情報処理装置。
【0200】
(4)
前記メッセージ取得部は、N回分(N≧2)の前記メッセージを1回の対話で取得し、
前記パターン情報提供部は、N回分の前記メッセージのそれぞれについて検証パターンを選択し、選択したN回分の検証パターンの情報を1回の対話で前記証明者に提供し、
前記回答取得部は、前記選択したN回分の検証パターンに対応するN回分の前記回答情報を1回の対話で前記証明者から取得し、
前記検証部は、N回分の前記メッセージの全てについて検証が成功した場合に、前記証明者が前記ベクトルsを保持していると判定する、
上記(3)に記載の情報処理装置。
【0201】
(5)
環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及びベクトルs∈Kに基づいてメッセージを生成するメッセージ生成部と、
前記2次多変数多項式の組F及びベクトルy=(y,…,y)=(f(s),…,f(s))を保持する検証者に前記メッセージを提供するメッセージ提供部と、
前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成する中間情報生成部と、
前記検証者に前記第3の情報を提供する中間情報提供部と、
k通り(k≧2)の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供部と、
を備え、
前記ベクトルsは秘密鍵であり、
前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記メッセージ生成部は、前記メッセージを生成する際、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算を式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行する、
情報処理装置。
【0202】
(6)
前記メッセージ生成部は、N回分(N≧2)のメッセージを生成し、
前記メッセージ提供部は、N回分の前記メッセージを1回の対話で前記検証者に提供し、
前記中間情報生成部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した前記第1の情報及び前記メッセージを生成する際に得られるN回分の前記第2の情報を用いてN回分の前記第3の情報を生成し、
前記中間情報提供部は、N回分の前記第3の情報を1回の対話で検証者に提供し、
前記回答提供部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した検証パターンに対応するN回分の前記回答情報を1回の対話で前記検証者に提供する、
上記(5)に記載の情報処理装置。
【0203】
(7)
環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及びベクトルy=(y,…,y)=(f(s),…,f(s))を保持する情報保持部と、
前記2次多変数多項式の組F及びベクトルs∈Kに基づいて生成されたメッセージを取得するメッセージ取得部と、
前記メッセージを提供した証明者に対し、ランダムに選択した第1の情報を提供する情報提供部と、
前記第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて前記証明者が生成した第3の情報を取得する中間情報取得部と、
k通り(k≧3)の検証パターンの中からランダムに選択した1つの検証パターンの情報を前記証明者に提供するパターン情報提供部と、
前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得部と、
前記メッセージ、前記第1の情報、前記第3の情報、前記2次多変数多項式の組F、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証する検証部と、
を備え、
前記ベクトルsは秘密鍵であり、
前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記検証部は、前記検証に用いるメッセージを再生する際、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算を式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行する、
情報処理装置。
【0204】
(8)
前記メッセージ取得部は、N回分(N≧2)の前記メッセージを1回の対話で取得し、
前記情報提供部は、N回分の前記メッセージのそれぞれについて前記第1の情報をランダムに選択し、選択したN回分の前記第1の情報を1回の対話で前記証明者に提供し、
前記中間情報取得部は、N回分の前記第1の情報及びN回分の前記メッセージを生成する際に得られるN回分の前記第2の情報を用いて前記証明者が生成したN回分の前記第3の情報を取得し、
前記パターン情報提供部は、N回分の前記メッセージのそれぞれについて検証パターンを選択し、選択したN回分の検証パターンの情報を1回の対話で前記証明者に提供し、
前記回答取得部は、前記選択したN回分の検証パターンに対応するN回分の前記回答情報を1回の対話で前記証明者から取得し、
前記検証部は、N回分の前記メッセージの全てについて検証が成功した場合に、前記証明者が前記ベクトルsを保持していると判定する、
上記(7)に記載の情報処理装置。
【0205】
(9)
環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及び署名鍵s∈Kを用いて文書Mに対する電子署名を生成する署名生成部と、
前記2次多変数多項式の組F及びベクトルy=(f(s),…,f(s))を保持する検証者へと前記電子署名を提供する署名提供部と、
を備え、
前記署名生成部は、前記電子署名を生成する過程で実行する、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算を式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行する、
署名生成装置。
【0206】
(10)
環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及びベクトルy=(f(s),…,f(s))を保持する情報保持部と、
文書Mについて、前記2次多変数多項式の組F及び署名鍵s∈Kを用いて生成された電子署名に基づいて前記文書Mの正当性を検証する署名検証部と、
を備え、
前記署名検証部は、前記電子署名を検証する過程で実行する、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算を式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行する、
署名検証装置。
【0207】
(11)
環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及びベクトルs∈Kに基づいてメッセージを生成するステップと、
前記2次多変数多項式の組F及びベクトルy=(y,…,y)=(f(s),…,f(s))を保持する検証者に前記メッセージを提供するステップと、
k通り(k≧3)の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供するステップと、
を含み、
前記ベクトルsは秘密鍵であり、
前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記生成するステップでは、前記メッセージを生成する際、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算が式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行される、
情報処理方法。
【0208】
(12)
環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及びベクトルy=(y,…,y)=(f(s),…,f(s))を保持する情報処理装置が、
前記2次多変数多項式の組F及びベクトルs∈Kに基づいて生成されたメッセージを取得するステップと、
前記メッセージを提供した証明者に対し、k通り(k≧3)の検証パターンの中からランダムに選択した1つの検証パターンの情報を提供するステップと、
前記選択した検証パターンに対応する回答情報を前記証明者から取得するステップと、
前記メッセージ、前記2次多変数多項式の組F、前記ベクトルy、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証するステップと、
を含み、
前記ベクトルsは秘密鍵であり、
前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記検証するステップでは、前記検証に用いるメッセージを再生する際、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算が式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行される、
情報処理方法。
【0209】
(13)
環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及びベクトルs∈Kに基づいてメッセージを生成するステップと、
前記2次多変数多項式の組F及びベクトルy=(y,…,y)=(f(s),…,f(s))を保持する検証者に前記メッセージを提供するステップと、
前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成するステップと、
前記検証者に前記第3の情報を提供するステップと、
k通り(k≧2)の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供するステップと、
を含み、
前記ベクトルsは秘密鍵であり、
前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記メッセージを生成するステップでは、前記メッセージを生成する際、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算が式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行される、
情報処理方法。
【0210】
(14)
環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及びベクトルy=(y,…,y)=(f(s),…,f(s))を保持する情報処理装置が、
前記2次多変数多項式の組F及びベクトルs∈Kに基づいて生成されたメッセージを取得するステップと、
前記メッセージを提供した証明者に対し、ランダムに選択した第1の情報を提供するステップと、
前記第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて前記証明者が生成した第3の情報を取得するステップと、
k通り(k≧3)の検証パターンの中からランダムに選択した1つの検証パターンの情報を前記証明者に提供するステップと、
前記選択した検証パターンに対応する回答情報を前記証明者から取得するステップと、
前記メッセージ、前記第1の情報、前記第3の情報、前記2次多変数多項式の組F、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証するステップと、
を含み、
前記ベクトルsは秘密鍵であり、
前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記検証するステップでは、前記検証に用いるメッセージを再生する際、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算が式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行される、
情報処理方法。
【0211】
(15)
環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及び署名鍵s∈Kを用いて文書Mに対する電子署名を生成するステップと、
前記2次多変数多項式の組F及びベクトルy=(f(s),…,f(s))を保持する検証者へと前記電子署名を提供するステップと、
を含み、
前記生成するステップでは、前記電子署名を生成する過程で実行される、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算が式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行される、
署名生成方法。
【0212】
(16)
環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及びベクトルy=(f(s),…,f(s))を保持する情報処理装置が、
文書Mについて、前記2次多変数多項式の組F及び署名鍵s∈Kを用いて生成された電子署名に基づいて前記文書Mの正当性を検証するステップを含み、
前記検証するステップでは、前記電子署名を検証する過程で実行される、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算が式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行される、
署名検証方法。
【0213】
(17)
上記の(1)〜(8)のいずれか1項に記載の情報処理装置が備える各部の機能をコンピュータに実現させるためのプログラム。
【0214】
(18)
上記の(9)に記載の署名生成装置が備える各部の機能をコンピュータに実現させるためのプログラム。
【0215】
(19)
上記の(10)に記載の署名検証装置が備える各部の機能をコンピュータに実現させるためのプログラム。
【0216】
(20)
上記の(17)〜(19)のいずれか1項に記載のプログラムが記録された、コンピュータにより読み取り可能な記録媒体。
【0217】
(備考)
上記の証明者アルゴリズムPは、メッセージ生成部、メッセージ提供部、回答提供部、中間情報生成部、中間情報提供部の一例である。また、上記の検証者アルゴリズムVは、情報保持部、メッセージ取得部、パターン情報提供部、回答取得部、検証部、中間情報取得部の一例である。また、上記の署名生成アルゴリズムSigは、署名生成部、署名提供部の一例である。また、上記の署名検証アルゴリズムVerは、情報保持部、署名検証部の一例である。
【0218】
以上、添付図面を参照しながら本技術の好適な実施形態について説明したが、本技術は係る例に限定されないことは言うまでもない。当業者であれば、特許請求の範囲に記載された範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、それらについても当然に本技術の技術的範囲に属するものと了解される。
【0219】
上記の説明において、ハッシュ関数Hを用いるアルゴリズムを紹介したが、ハッシュ関数Hの代わりにコミットメント関数COMを用いてもよい。コミットメント関数COMは、文字列S及び乱数ρを引数にとる関数である。コミットメント関数の例としては、Shai HaleviとSilvio Micaliによって国際会議CRYPTO1996で発表された方式などがある。
【符号の説明】
【0220】
Gen 鍵生成アルゴリズム
P 証明者アルゴリズム
V 検証者アルゴリズム
Sig 署名生成アルゴリズム
Ver 署名検証アルゴリズム


【特許請求の範囲】
【請求項1】
環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及びベクトルs∈Kに基づいてメッセージを生成するメッセージ生成部と、
前記2次多変数多項式の組F及びベクトルy=(y,…,y)=(f(s),…,f(s))を保持する検証者に前記メッセージを提供するメッセージ提供部と、
k通り(k≧3)の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供部と、
を備え、
前記ベクトルsは秘密鍵であり、
前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記メッセージ生成部は、前記メッセージを生成する際、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算を式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行する、
情報処理装置。
【請求項2】
前記メッセージ生成部は、N回分(N≧2)のメッセージを生成し、
前記メッセージ提供部は、N回分の前記メッセージを1回の対話で前記検証者に提供し、
前記回答提供部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した検証パターンに対応するN回分の前記回答情報を1回の対話で前記検証者に提供する、
請求項1に記載の情報処理装置。
【請求項3】
環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及びベクトルy=(y,…,y)=(f(s),…,f(s))を保持する情報保持部と、
前記2次多変数多項式の組F及びベクトルs∈Kに基づいて生成されたメッセージを取得するメッセージ取得部と、
前記メッセージを提供した証明者に対し、k通り(k≧3)の検証パターンの中からランダムに選択した1つの検証パターンの情報を提供するパターン情報提供部と、
前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得部と、
前記メッセージ、前記2次多変数多項式の組F、前記ベクトルy、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証する検証部と、
を備え、
前記ベクトルsは秘密鍵であり、
前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記検証部は、前記検証に用いるメッセージを再生する際、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算を式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行する、
情報処理装置。
【請求項4】
前記メッセージ取得部は、N回分(N≧2)の前記メッセージを1回の対話で取得し、
前記パターン情報提供部は、N回分の前記メッセージのそれぞれについて検証パターンを選択し、選択したN回分の検証パターンの情報を1回の対話で前記証明者に提供し、
前記回答取得部は、前記選択したN回分の検証パターンに対応するN回分の前記回答情報を1回の対話で前記証明者から取得し、
前記検証部は、N回分の前記メッセージの全てについて検証が成功した場合に、前記証明者が前記ベクトルsを保持していると判定する、
請求項3に記載の情報処理装置。
【請求項5】
環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及びベクトルs∈Kに基づいてメッセージを生成するメッセージ生成部と、
前記2次多変数多項式の組F及びベクトルy=(y,…,y)=(f(s),…,f(s))を保持する検証者に前記メッセージを提供するメッセージ提供部と、
前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成する中間情報生成部と、
前記検証者に前記第3の情報を提供する中間情報提供部と、
k通り(k≧2)の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供する回答提供部と、
を備え、
前記ベクトルsは秘密鍵であり、
前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記メッセージ生成部は、前記メッセージを生成する際、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算を式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行する、
情報処理装置。
【請求項6】
前記メッセージ生成部は、N回分(N≧2)のメッセージを生成し、
前記メッセージ提供部は、N回分の前記メッセージを1回の対話で前記検証者に提供し、
前記中間情報生成部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した前記第1の情報及び前記メッセージを生成する際に得られるN回分の前記第2の情報を用いてN回分の前記第3の情報を生成し、
前記中間情報提供部は、N回分の前記第3の情報を1回の対話で検証者に提供し、
前記回答提供部は、N回分の前記メッセージのそれぞれについて前記検証者が選択した検証パターンに対応するN回分の前記回答情報を1回の対話で前記検証者に提供する、
請求項5に記載の情報処理装置。
【請求項7】
環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及びベクトルy=(y,…,y)=(f(s),…,f(s))を保持する情報保持部と、
前記2次多変数多項式の組F及びベクトルs∈Kに基づいて生成されたメッセージを取得するメッセージ取得部と、
前記メッセージを提供した証明者に対し、ランダムに選択した第1の情報を提供する情報提供部と、
前記第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて前記証明者が生成した第3の情報を取得する中間情報取得部と、
k通り(k≧3)の検証パターンの中からランダムに選択した1つの検証パターンの情報を前記証明者に提供するパターン情報提供部と、
前記選択した検証パターンに対応する回答情報を前記証明者から取得する回答取得部と、
前記メッセージ、前記第1の情報、前記第3の情報、前記2次多変数多項式の組F、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証する検証部と、
を備え、
前記ベクトルsは秘密鍵であり、
前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記検証部は、前記検証に用いるメッセージを再生する際、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算を式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行する、
情報処理装置。
【請求項8】
前記メッセージ取得部は、N回分(N≧2)の前記メッセージを1回の対話で取得し、
前記情報提供部は、N回分の前記メッセージのそれぞれについて前記第1の情報をランダムに選択し、選択したN回分の前記第1の情報を1回の対話で前記証明者に提供し、
前記中間情報取得部は、N回分の前記第1の情報及びN回分の前記メッセージを生成する際に得られるN回分の前記第2の情報を用いて前記証明者が生成したN回分の前記第3の情報を取得し、
前記パターン情報提供部は、N回分の前記メッセージのそれぞれについて検証パターンを選択し、選択したN回分の検証パターンの情報を1回の対話で前記証明者に提供し、
前記回答取得部は、前記選択したN回分の検証パターンに対応するN回分の前記回答情報を1回の対話で前記証明者から取得し、
前記検証部は、N回分の前記メッセージの全てについて検証が成功した場合に、前記証明者が前記ベクトルsを保持していると判定する、
請求項7に記載の情報処理装置。
【請求項9】
環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及び署名鍵s∈Kを用いて文書Mに対する電子署名を生成する署名生成部と、
前記2次多変数多項式の組F及びベクトルy=(f(s),…,f(s))を保持する検証者へと前記電子署名を提供する署名提供部と、
を備え、
前記署名生成部は、前記電子署名を生成する過程で実行する、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算を式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行する、
署名生成装置。
【請求項10】
環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及びベクトルy=(f(s),…,f(s))を保持する情報保持部と、
文書Mについて、前記2次多変数多項式の組F及び署名鍵s∈Kを用いて生成された電子署名に基づいて前記文書Mの正当性を検証する署名検証部と、
を備え、
前記署名検証部は、前記電子署名を検証する過程で実行する、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算を式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行する、
署名検証装置。
【請求項11】
環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及びベクトルs∈Kに基づいてメッセージを生成するステップと、
前記2次多変数多項式の組F及びベクトルy=(y,…,y)=(f(s),…,f(s))を保持する検証者に前記メッセージを提供するステップと、
k通り(k≧3)の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供するステップと、
を含み、
前記ベクトルsは秘密鍵であり、
前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記生成するステップでは、前記メッセージを生成する際、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算が式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行される、
情報処理方法。
【請求項12】
環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及びベクトルy=(y,…,y)=(f(s),…,f(s))を保持する情報処理装置が、
前記2次多変数多項式の組F及びベクトルs∈Kに基づいて生成されたメッセージを取得するステップと、
前記メッセージを提供した証明者に対し、k通り(k≧3)の検証パターンの中からランダムに選択した1つの検証パターンの情報を提供するステップと、
前記選択した検証パターンに対応する回答情報を前記証明者から取得するステップと、
前記メッセージ、前記2次多変数多項式の組F、前記ベクトルy、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証するステップと、
を含み、
前記ベクトルsは秘密鍵であり、
前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記検証するステップでは、前記検証に用いるメッセージを再生する際、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算が式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行される、
情報処理方法。
【請求項13】
環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及びベクトルs∈Kに基づいてメッセージを生成するステップと、
前記2次多変数多項式の組F及びベクトルy=(y,…,y)=(f(s),…,f(s))を保持する検証者に前記メッセージを提供するステップと、
前記検証者がランダムに選択した第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて第3の情報を生成するステップと、
前記検証者に前記第3の情報を提供するステップと、
k通り(k≧2)の検証パターンの中から前記検証者が選択した検証パターンに対応する回答情報を前記検証者に提供するステップと、
を含み、
前記ベクトルsは秘密鍵であり、
前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記メッセージを生成するステップでは、前記メッセージを生成する際、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算が式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行される、
情報処理方法。
【請求項14】
環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及びベクトルy=(y,…,y)=(f(s),…,f(s))を保持する情報処理装置が、
前記2次多変数多項式の組F及びベクトルs∈Kに基づいて生成されたメッセージを取得するステップと、
前記メッセージを提供した証明者に対し、ランダムに選択した第1の情報を提供するステップと、
前記第1の情報及び前記メッセージを生成する際に得られる第2の情報を用いて前記証明者が生成した第3の情報を取得するステップと、
k通り(k≧3)の検証パターンの中からランダムに選択した1つの検証パターンの情報を前記証明者に提供するステップと、
前記選択した検証パターンに対応する回答情報を前記証明者から取得するステップと、
前記メッセージ、前記第1の情報、前記第3の情報、前記2次多変数多項式の組F、及び前記回答情報に基づいて前記証明者が前記ベクトルsを保持しているか否かを検証するステップと、
を含み、
前記ベクトルsは秘密鍵であり、
前記2次多変数多項式の組F及び前記ベクトルyは公開鍵であり、
前記メッセージは、前記公開鍵、前記第1の情報、前記第3の情報、前記回答情報を利用して当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記メッセージは、前記公開鍵及び前記回答情報を利用して、当該回答情報に対応する検証パターン用に予め用意された演算を実行することで得られる情報であり、
前記検証するステップでは、前記検証に用いるメッセージを再生する際、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算が式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行される、
情報処理方法。
【請求項15】
環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及び署名鍵s∈Kを用いて文書Mに対する電子署名を生成するステップと、
前記2次多変数多項式の組F及びベクトルy=(f(s),…,f(s))を保持する検証者へと前記電子署名を提供するステップと、
を含み、
前記生成するステップでは、前記電子署名を生成する過程で実行される、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算が式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行される、
署名生成方法。
【請求項16】
環K上で定義され、2次形式で表現される2次多変数多項式の組F=(f,…,f)及びベクトルy=(f(s),…,f(s))を保持する情報処理装置が、
文書Mについて、前記2次多変数多項式の組F及び署名鍵s∈Kを用いて生成された電子署名に基づいて前記文書Mの正当性を検証するステップを含み、
前記検証するステップでは、前記電子署名を検証する過程で実行される、G(x,x)=F(x+x)−F(x)−F(x)で定義される関数G=(g,…,g)の計算が式g(x,x)=x+x(l=1〜m;Aは、n×nの係数行列)に基づいて実行される、
署名検証方法。


【図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