鍵生成装置、鍵生成方法及び鍵生成プログラム
【課題】安全性・信頼性の高いデジタル署名を生成することができ、しかも少ない計算量で実現可能な公開鍵暗号に基づくデジタル署名システムを提供する。
【解決手段】有限体Fｑ上定義された３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）（公開鍵）と該Ａ内の曲面のうちｘとｙ座標がパラメータｓとｔの関数で表されたセクション（秘密鍵）の生成のため、２変数多項式λｘ（ｓ，ｔ）を生成し、λｘで割り切れる２変数多項式λｙ（ｓ，ｔ）を生成し、ｕｘ（ｓ，ｔ）−ｖｘ（ｓ，ｔ）をλｘとする２変数多項式ｕｘとｖｘを生成し、ｕｙ（ｓ，ｔ）−ｖｙ（ｓ，ｔ）をλｙとする２変数多項式ｕｙとｖｙを生成し、ｕｘをｘ座標、ｕｙをｙ座標とするセクションＤ１：（ｕｘ（ｓ，ｔ），ｕｙ（ｓ，ｔ），ｓ，ｔ）と、ｖｘをｘ座標、ｖｙをｙ座標とするセクションＤ２：（ｖｘ（ｓ，ｔ），ｖｙ（ｓ，ｔ），ｓ，ｔ）を生成し、セクションＤ１とＤ２を含む上記Ａの多項式を生成する。
【解決手段】有限体Fｑ上定義された３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）（公開鍵）と該Ａ内の曲面のうちｘとｙ座標がパラメータｓとｔの関数で表されたセクション（秘密鍵）の生成のため、２変数多項式λｘ（ｓ，ｔ）を生成し、λｘで割り切れる２変数多項式λｙ（ｓ，ｔ）を生成し、ｕｘ（ｓ，ｔ）−ｖｘ（ｓ，ｔ）をλｘとする２変数多項式ｕｘとｖｘを生成し、ｕｙ（ｓ，ｔ）−ｖｙ（ｓ，ｔ）をλｙとする２変数多項式ｕｙとｖｙを生成し、ｕｘをｘ座標、ｕｙをｙ座標とするセクションＤ１：（ｕｘ（ｓ，ｔ），ｕｙ（ｓ，ｔ），ｓ，ｔ）と、ｖｘをｘ座標、ｖｙをｙ座標とするセクションＤ２：（ｖｘ（ｓ，ｔ），ｖｙ（ｓ，ｔ），ｓ，ｔ）を生成し、セクションＤ１とＤ２を含む上記Ａの多項式を生成する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、公開鍵暗号方式を利用したデジタル署名生成装置、デジタル署名検証装置、鍵生成装置に関する。
【背景技術】
【０００２】
電子メールを始めとする多くの情報がネットワークを行き交うことにより、人々がコミュニケーションを行なうネットワーク社会において、暗号技術は情報の機密性や真正性を守る手段として広く活用されている。
【０００３】
暗号技術は大きく共通鍵暗号技術と公開鍵暗号技術に分けることができ、共通鍵暗号はデータの攪拌アルゴリズムに基づいた暗号方式で、高速に暗号化／復号ができる一方で、予め共通の鍵を持った２者間でしか秘密通信や認証通信ができない。公開鍵暗号は数学的なアルゴリズムに基づいた暗号方式で、共通鍵暗号ほど暗号化／復号が高速でないが、事前の鍵共有を必要とせず、通信の際は送信相手が公開している公開鍵を利用して秘密通信を実現し、送信者の秘密鍵を利用してデジタル署名を施すことで（成りすましを防ぐ）認証通信が可能となるという特徴がある。
【０００４】
このため、共通鍵暗号に基づくデジタル署名は秘密鍵を共有できる環境にある相手間や機器間で、高速性が求められている場合か、署名生成装置か署名検証装置のどちらか一方の能力が低い場合の認証手段として用いられている。また、公開鍵暗号に基づくデジタル署名は、インターネットに開設されているネットショッピング、銀行や証券会社のオンラインサイトなど秘密鍵が共有できない環境にある場合や、秘密鍵が共有できる環境にある場合でも、署名生成装置か署名検証装置のどちらの計算能力も高い場合に用いられている。
【０００５】
代表的な公開鍵暗号には、ＲＳＡ暗号と楕円曲線暗号があり、それぞれに基づくデジタル署名方式が提案されている。ＲＳＡ暗号は素因数分解問題の困難性が安全性の根拠となっており、署名生成演算及び署名検証演算として冪乗剰余演算が用いられている。楕円曲線暗号は楕円曲線上の離散対数問題の困難性が安全性の根拠となっており、署名生成演算並びに署名検証演算として楕円曲線上の点演算が用いられている。これらの公開鍵暗号は特定の鍵（公開鍵）に関する解読法（署名偽造法）は提案されているものの、一般的な解読法（署名偽造法）は知られていないため、安全性に関する重大な問題は、後に述べる量子計算機による解読法を除き、現在までのところ見つかっていない。
【０００６】
この他の公開鍵暗号に基づくデジタル署名には、体の拡大理論を利用して構成され連立方程式の求解問題に安全性の根拠をおいた多次多変数暗号に基づくＳＦＬＡＳＨと呼ばれる方式がある。しかし、多次多変数暗号には有力な攻撃方法が知られており、その解読法を避けるために必要な鍵サイズを大きくしなくてはならず、実用性が問題視されはじめている。
【０００７】
一方で、現在デジタル署名に広く利用されているＲＳＡ暗号と楕円曲線暗号であっても、量子計算機が出現すれば解読される危険に晒されている。量子計算機とは量子力学で知られているエンタングルメントという物理現象を利用して、（現在の計算機とは違った原理に基づいて）超並列計算を行わせることができる計算機であり、現在までのところ実験レベルでしか動作が確認されていない仮想の計算機であるが、実現に向けた研究開発が進められている。この量子計算機を用いて１９９４年にＳｈｏｒは素因数分解や離散対数問題を効率的に解くアルゴリズムが構成できることを示した（非特許文献１参照）。
【０００８】
即ち、量子計算機が実現すれば素因数分解に基づくＲＳＡ暗号や、（楕円曲線上の）離散対数問題に基づく楕円曲線暗号は解読できることになる。
【０００９】
このような状況の下、量子計算機が実現されてもなお安全な公開鍵暗号に基づくデジタル署名の研究が近年行われるようになってきた。現時点で実現可能で公開鍵暗号で量子計算機でも解読が難しいとされている方式には多次多変数暗号に基づくＳＦＬＡＳＨと呼ばれる方式があるが、多次多変数暗号は前記の通り、現状の計算機に対して安全とするために必要となる鍵サイズが膨大となっており、実用化が危ぶまれている。
【００１０】
更に、公開鍵暗号は共通鍵暗号と比較して、回路規模が大きく、処理時間も掛かるため、モバイル端末などの小電力環境では実現できないか実現しても処理時間がかかるという問題があった。このため、小電力環境でも実現できる公開鍵暗号が求められている。
【００１１】
一般に公開鍵暗号に基づくデジタル署名は（素因数分解問題や離散対数問題などの）計算困難な問題を見出し、（秘密鍵を知らずに）平文と呼ばれるメッセージにデジタル署名を生成しようとすることが当該計算困難な問題を解くことと計算量的に同等になるように構成する。しかし、逆に計算困難な問題が見つかったとしても必ずしもその問題を安全性の根拠とするようにデジタル署名を構成できる訳ではない。なぜなら、計算が困難すぎる問題に安全性の根拠をおくと鍵を生成する問題も困難になり、構成が難しくなる。一方で問題を鍵生成が可能となる程度に容易とすると、デジタル署名の偽造も容易になってしまう。
【００１２】
従って、公開鍵暗号を構成するには計算困難な問題を見つけるとともに、鍵を生成できる程には容易だが、（生成した秘密鍵を知らずに）解読できる程には容易でないという絶妙なバランスを持つ問題に作り変えるという創造性が必要であり、そこが難しいために現在まで数えるほどの公開鍵暗号に基づくデジタル署名しか提案されてこなかった。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】P.W.Shor:“Algorithms for Quantum Computation : Discrete Log and Factoring”,Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science,1994.
【発明の概要】
【発明が解決しようとする課題】
【００１４】
このように、従来は、量子計算機が出現しても安全性が確保でき、現在の計算機でも安全に実現可能であるとともに、小電力環境での実現可能性がある公開鍵暗号に基づくデジタル署名システム（鍵を生成し、デジタル署名を生成し、検証を行うためのシステム）が存在しなかった。
【００１５】
そこで、本発明は、安全性・信頼性の高いデジタル署名を生成することができ、しかも少ない計算量で実現可能な公開鍵暗号に基づくデジタル署名システムを提供する。
【課題を解決するための手段】
【００１６】
本発明に係るデジタル署名生成装置は、有限体Fｑならびに署名生成用の秘密鍵として、ｘ座標、ｙ座標、パラメータｓ、及びパラメータｔで表される前記有限体Fｑ上定義された３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）内の曲面のうち、ｘ座標及びｙ座標がパラメータｓ及びｔの関数で表されたセクションＤ（ｕｘ（ｓ，ｔ），ｕｙ（ｓ，ｔ），ｓ，ｔ）を記憶する記憶手段を備え、メッセージｍのハッシュ値を計算し、前記ハッシュ値を前記有限体Fｑ上定義された１変数多項式ｈ（ｔ）に埋め込み、ハッシュ値多項式を生成し、前記記憶手段に記憶されたセクションのパラメータｓに前記ハッシュ値多項式を代入することで、ｘ座標及びｙ座標がパラメータｔの関数で表された前記セクション上の曲線であるデジタル署名Ｄｓ（Ｕｘ（ｔ），Ｕｙ（ｔ），ｔ）を生成する。
【００１７】
本発明に係るデジタル署名検証装置は、有限体Fｑならびに公開鍵として、ｘ座標、ｙ座標、パラメータｓ、及びパラメータｔで表される前記有限体Fｑ上定義された３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）の多項式を記憶する記憶手段を備え、メッセージｍを入力するとともに、前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）内の曲面のうち、ｘ座標及びｙ座標がパラメータｓ及びｔの関数で表されたセクションＤ（ｕｘ（ｓ，ｔ），ｕｙ（ｓ，ｔ），ｓ，ｔ）を署名生成用の秘密鍵として用いて生成された、ｘ座標及びｙ座標がパラメータｔの関数で表された前記セクション上の曲線である、前記メッセージｍに対応したデジタル署名Ｄｓ：（Ｕｘ（ｔ），Ｕｙ（ｔ），ｔ）を入力する。前記メッセージｍのハッシュ値を計算し、前記ハッシュ値を、パラメータｔを有する前記有限体Fｑ上定義された１変数多項式ｈ（ｔ）に埋め込み、ハッシュ値多項式を生成し、前記記憶手段に記憶された前記多項式のパラメータｓに前記ハッシュ値多項式を代入して、前記ハッシュ値に対応した代数曲面Ｘ（ｘ，ｙ，ｔ）を計算し、前記代数曲面Ｘ（ｘ，ｙ，ｔ）の座標ｘ及び座標ｙに、前記デジタル署名のｘ座標を表す関数Ｕｘ（ｔ）と、ｙ座標を表す関数Ｕy（ｔ）をそれぞれ代入することにより、前記メッセージ及び前記デジタル署名の正当性を検証する。
【００１８】
本発明の鍵生成装置は、有限体Fｑならびに署名検証用の公開鍵として用いられる、ｘ座標、ｙ座標、パラメータｓ、及びパラメータｔで表される前記有限体Fｑ上定義された３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）と、署名生成用の秘密鍵として用いられる前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）内の曲面のうち、ｘ座標及びｙ座標がパラメータｓ及びｔの関数で表されたセクションを生成する鍵生成装置であって、前記有限体Fｑ上定義された、パラメータｓ、ｔに関する第１の２変数多項式λｘ（ｓ，ｔ）を生成し、前記第１の２変数多項式λｘ（ｓ，ｔ）で割り切れる、前記有限体Fｑ上定義された第２の２変数多項式λｙ（ｓ，ｔ）を生成し、前記有限体Fｑ上定義された、パラメータｓ，ｔに関する２つの２変数多項式ｕｘ（ｓ，ｔ）、ｖｘ（ｓ，ｔ）を、当該２つの２変数多項式の差分｛ｕｘ（ｓ，ｔ）−ｖｘ（ｓ，ｔ）｝が前記第１の２変数多項式λｘ（ｓ，ｔ）となるように生成し、前記有限体Fｑ上定義された、パラメータｓ，ｔに関する２つの２変数多項式ｕｙ（ｓ，ｔ）、ｖｙ（ｓ，ｔ）を、当該２つの２変数多項式の差分｛ｕｙ（ｓ，ｔ）−ｖｙ（ｓ，ｔ）｝が前記第２の２変数多項式λｙ（ｓ，ｔ）となるように生成し、２変数多項式ｕｘ（ｓ，ｔ）をｘ座標、２変数関数ｕｙ（ｓ，ｔ）をｙ座標とするセクションＤ１：（ｘ，ｙ，ｓ，ｔ）＝（ｕｘ（ｓ，ｔ），ｕｙ（ｓ，ｔ），ｓ，ｔ）と、２変数多項式ｖｘ（ｓ，ｔ）をｘ座標、２変数関数ｖｙ（ｓ，ｔ）をｙ座標とするセクションＤ２：（ｘ，ｙ，ｓ，ｔ）＝（ｖｘ（ｓ，ｔ），ｖｙ（ｓ，ｔ），ｓ，ｔ）を生成する。また、前記セクションＤ１及び前記セクションＤ２を含む前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）の多項式を生成する。
【００１９】
本発明の鍵生成装置は、有限体Fｑならびに、ｘ座標、ｙ座標、パラメータｓ、及びパラメータｔで表された、署名検証用の公開鍵として用いられる前記有限体Fｑ上定義された３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）と、前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）内の曲面のうち、ｘ座標及びｙ座標がパラメータｓ及びｔの関数で表された、署名生成用の秘密鍵として用いられるセクションを生成する鍵生成装置であって、パラメータｓ、ｔに関する第１番目から第ｎ（ｎは正の整数）番目までのｎ（ｎは正の整数）個の前記有限体Fｑ上定義された２変数多項式ｕｘ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）と、パラメータｓ、ｔに関する第１番目から第ｎ番目までのｎ個の前記有限体Fｑ上定義された２変数多項式ｕｙ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）を生成し、第ｉ（１≦ｉ≦ｎ）番目の２変数多項式ｕｘ，ｉ（ｓ，ｔ）及びｕｙ，ｉ（ｓ，ｔ）をそれぞれｘ座標、ｙ座標とする第ｉ番目のセクションＤｉ：（ｘ，ｙ，ｓ，ｔ）＝（ｕｘ，ｉ（ｓ，ｔ）、ｕｙ，ｉ（ｓ，ｔ），ｓ，ｔ）（１≦ｉ≦ｎ）を生成することにより、第１番目から第ｎ番目までのｎ個のセクションＤｉ（１≦ｉ≦ｎ）を求め、第ｉ（１≦ｉ≦ｎ）番目の２変数多項式ｕｘ，ｉ（ｓ，ｔ）及びｕｙ，ｉ（ｓ，ｔ）を用いて、第ｉ番目のｘ因子（ｘ−ｕｘ，ｉ（ｓ，ｔ））及びｙ因子（ｙ−ｕｙ，ｉ（ｓ，ｔ））を生成することにより、第１番目から第ｎ番目までのｘ因子及びｙ因子を求める、第ｉ（１≦ｉ≦ｎ）番目のｘ因子及びｙ因子を左辺と右辺に振り分けて、左辺に振り分けられたｎ個のｘ因子及びｙ因子の積と、右辺に振り分けられたｎ個のｘ因子及びｙ因子の積とを等号で結ぶことにより得られる等式を生成し、生成された等式を展開することにより、前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）の多項式を生成する。
【発明の効果】
【００２０】
安全性・信頼性の高い公開鍵暗号に基づくデジタル署名を生成することができ、しかも少ない計算量で実現可能となる。
【図面の簡単な説明】
【００２１】
【図１】３次元多様体のファイブレーションと、代数曲面について説明するための図。
【図２】鍵生成装置の構成例を示した図。
【図３】図２の鍵生成装置の処理動作を説明するためのフローチャート。
【図４】デジタル署名生成装置の構成例を示した図。
【図５】図４のデジタル署名生成装置の処理動作を説明するためのフローチャート。
【図６】デジタル署名検証装置の構成例を示した図。
【図７】図６のデジタル署名検証装置の処理動作を説明するためのフローチャート。
【図８】鍵生成装置の他の構成例を示した図。
【図９】図８の鍵生成装置の処理動作を説明するためのフローチャート。
【図１０】図２の鍵生成装置の他の構成例を示した図。
【図１１】図４のデジタル署名生成装置の他の構成例を示した図。
【図１２】図６のデジタル署名検証装置の他の構成例を示した図。
【図１３】８の鍵生成装置の他の構成例を示した図。
【発明を実施するための最良の形態】
【００２２】
以下、本発明の実施形態について図面を参照して説明する。
【００２３】
まず、本実施形態の概要を説明する。
【００２４】
（概要）
本実施形態では、３次元多様体は、体Ｋ上定義された連立（代数）方程式の解の集合のうち３次元の自由度を持ったものと定義される。例えば、体Ｋ上の連立方程式
【数１】
【００２５】
は変数６つに対し、それらを束縛する３つの方程式があるので３次元の自由度を持っており、３次元多様体となる。特に４変数のＫ上代数方程式
【数２】
【００２６】
の解の集合として定義される空間もＫ上の３次元多様体となる。尚、式（１）、式（２）に示した３次元多様体の定義式は、アフィン空間におけるものであって、射影空間におけるそれは（式（２）の場合）
【数３】
【００２７】
である。本実施形態では、３次元多様体を射影空間で扱うことはないので３次元多様体の定義式を式（１）若しくは式（２）としたが、射影空間で表現しても、本実施形態はそのまま成立する。一方、代数曲面は体Ｋ上定義された連立（代数）方程式の解の集合のうち２次元の自由度を持ったものである。よって、例えば
【数４】
【００２８】
と定義される。本実施形態においては式（２）のように１つの式で書ける３次元多様体のみを扱うので、以下では式（２）を３次元多様体の定義方程式のごとく扱う。
【００２９】
体とは加減乗除が自由にできる集合であって、実数、有理数、複素数がこれにあたる。たとえば、整数や行列など０以外に除算ができない元を含む集合は該当しない。体の中には有限体と呼ばれる有限個の元から構成される体がある。例えば素数ｐに対し、ｐを法とする剰余類Ｚ／ｐＺは体をなす。このような体は素体と呼ばれ、Ｆｐと表す。有限体にはこの他に素数の冪乗個の元を持つ体Ｆｑ（ｑ＝ｐｒ）があるが、本実施形態では簡単のため、主に素体Ｆｐのみを扱う。一般に素体Ｆｐのｐは素体Ｆｐの標数と呼ばれる。一方、一般の有限体でも、本実施形態は自明な変形を施すことによって同様に成立する。
【００３０】
公開鍵暗号ではメッセージをデジタルデータとして埋め込む必要から有限体上で構成することが多く、本実施形態においても同様に有限体（本実施形態では特に素体）Ｆｐ上定義された３次元多様体を扱う。
【００３１】
３次元多様体Ａ：ｆ（ｘ，ｙ，ｚ，ｕ）＝０内には、図１に示すように、通常、代数曲面が複数存在する。このような代数曲面は３次元多様体上の因子と呼ばれる。一般に３次元多様体の定義式が与えられた時に（非自明な）因子を求める問題は現代の数学においても未解決の難問であり、後述する多次多変数方程式によって解く方法を除けば一般的な解法は知られていない。
【００３２】
特に本実施形態で扱うような有限体で定義された３次元多様体においては有理数体などの無限体（無限個の元からなる体）で定義された３次元多様体と比較しても手掛かりが少なく、より難しい問題であることが知られている。更に、前記因子を求めるために出現する多次多変数方程式は、多次多変数暗号を解く場合に出現する多次多変数方程式と比べるとそのバラエティーが広く、多次多変数暗号に対して提案されている解法は一般には成立しない。
【００３３】
本実施形態では、この問題を３次元多様体上の求因子問題もしくは単に求因子問題と呼び、前記３次元多様体上の求因子問題に安全性の根拠をおく公開鍵暗号を構成する。
【００３４】
ｘ座標、ｙ座標、ｚ座標及びパラメータｕで表された３次元多様体Ａの定義式ｆ（ｘ，ｙ，ｚ，ｕ）＝０ において、変数ｚ、ｕをそれぞれパラメータｓ、ｔに変えて、
ｇｓ，ｔ（ｘ，ｙ）：＝ｆ（ｘ，ｙ，ｓ，ｔ）
とおく。これを体Ｋ上の２変数代数関数体Ｋ（ｓ，ｔ）の元を係数とする多項式とみなし、ｇｓ，ｔ（ｘ，ｙ）＝０ が、Ｋ（ｓ，ｔ）上の代数曲線を定義するとき、３次元多様体Ａはｓ，ｔをパラメータとするアフィン平面Ｐ２上のファイブレーションを持つといい、（ｘ，ｙ，ｓ，ｔ）を（ｓ，ｔ）に対応させることによって得られる写像Ａ→Ｐ２を、３次元多様体Ａのアフィン平面Ｐ２上のファイブレーションと呼ぶ。
【００３５】
そして、アフィン平面Ｐ２上の点（ｓ，ｔ）を１点（ｓ０，ｔ０）（ｓ０，ｔ０ は体Ｋの元）に固定したときに得られる曲線ｇｓ０，ｔ０（ｘ，ｙ）＝０ を点（ｓ０，ｔ０）上のファイバーと呼び、Ａｓ０，ｔ０ と表す。
【００３６】
アフィン平面Ｐ２上のファイブレーションを持つ３次元多様体にはセクションと呼ばれ、
（ｘ，ｙ，ｓ，ｔ）＝（ｕｘ（ｓ，ｔ），ｕｙ（ｓ，ｔ），ｓ，ｔ）
と表すことのできる、ｓ，ｔ でパラメタライズされた３次元多様体Ａ上の代数曲面が存在することが多い。セクションを持たないファイブレーションも存在するが、セクションを持つようなｆ（ｘ，ｙ，ｚ，ｕ）は容易に構成できる。
【００３７】
一方、上述のように、３次元多様体Ａの定義式ｆ（ｘ，ｙ，ｚ，ｕ）＝０ を２変数代数関数体Ｋ（ｓ，ｔ）の上で考えるのではなく、例えば１変数代数関数体Ｋ（ｔ）の上で考えることもできる。その場合は、
ｈｔ（ｘ，ｙ，ｓ）：＝ｆ（ｘ，ｙ，ｓ，ｔ）
とおくと、ｔの各値に対してｈｔ（ｘ，ｙ，ｓ）＝０ は、１変数代数関数体Ｋ（ｔ）上の代数曲面を定義する。このとき、Ａはｔをパラメータとするアフィン直線Ｐ１ 上のファイブレーションを持つといい、（ｘ，ｙ，ｓ，ｔ）を（ｔ）に対応させることによって得られる写像Ａ→Ｐ１ を３次元多様体Ａのアフィン直線Ｐ１上のファイブレーションと呼ぶ。
【００３８】
そして、アフィン直線Ｐ１ 上の点ｔを１点ｔ０に固定したときに得られる曲面
ｈｔ０（ｘ，ｙ，ｓ）＝０
を点ｔ０ 上のファイバーと呼び、Ａｔ０ と表す。
【００３９】
アフィン直線Ｐ１ 上のファイブレーションを持つ３次元多様体におけるセクションとは、
（ｘ，ｙ，ｓ，ｔ）＝（ｕｘ（ｔ），ｕｙ（ｔ），ｕｓ（ｔ），ｔ）
と表すことができ、ｔでパラメタライズされた、３次元多様体Ａ上の代数曲線のことである。
【００４０】
セクションは、３次元多様体の因子である。一般に３次元多様体のファイブレーションが与えられたとき、それに対応するファイバーは（ｓやｔに体の元を代入することにより）直ちに求まるが、対応するセクションを求めることは極めて難しい。
【００４１】
本実施形態で述べるデジタル署名は、３次元多様体上の求因子問題のうち、特に３次元多様体Ａのファイブレーションが与えられたとき、セクションを求める問題に安全性の根拠をおいたデジタル署名である。
【００４２】
尚、本実施形態においては、主としてアフィン平面Ｐ２ 上のファイブレーションを扱うので、簡単のためアフィン平面Ｐ２ 上のファイブレーションであることが明らかな場合は、単にファイブレーションと呼ぶ。またこの場合、ファイブレーションを持つ３次元多様体の定義式ｆ（ｘ，ｙ，ｓ，ｔ）＝０を単にファイブレーションと呼ぶことがある。
【００４３】
ファイブレーションからセクションを求めるには、現代の数学においても、セクション（ｕｘ（ｓ，ｔ），ｕｙ（ｓ，ｔ），ｓ，ｔ）を
【数５】
【００４４】
（ここでｄｅｇｓｕｘ（ｓ，ｔ）はｕｘ（ｓ，ｔ）において、ｓのみを変数としたときの次数である。）と仮定した上で、
【数６】
【００４５】
とおき、これをＡ（ｘ，ｙ，ｓ，ｔ）＝０に代入して、
【数７】
【００４６】
とし、この左辺を展開してｓｉｔｊの係数を
α０，…，αｒｓｘｒｔｘ−１，β０，…，βｒｓｙｒｔｙ−１の関数
ｃｉ，ｊ（α０，…，αｒｓｘｒｔｘ−１，β０，…，βｒｓｙｒｔｙ−１）
で表現し、連立方程式系
【数８】
【００４７】
を立てて、これを解くことによって求める方法しか知られていない。
【００４８】
即ち、本発明の公開鍵暗号も従来技術で述べた多次多変数暗号と同様に連立方程式の求解問題に帰着すると言える。しかし、多次多変数暗号が（現代の数学ではかなり解明されている）有限体の拡大理論に依存した非常に限られた範囲の多次多変数方程式の求解問題に帰着しているのに対し、３次元多様体暗号は数学上の未解決問題である求因子問題に依存しているため、問題の困難さのレベルは大きく異なる。
【００４９】
以下では３次元多様体上の求因子問題に基づいたデジタル署名の具体的な構成を説明する。尚、以下では全てＦｐ上定義された３次元多様体を考える。このため、全ての演算はＦｐ上で行う。
【００５０】
（第１の実施形態）
本実施形態に係るデジタル署名で用いられる公開鍵は、
Ｆｐ上の３次元多様体Ｘのファイブレーション：Ａ（ｘ，ｙ，ｓ，ｔ）＝０である。
【００５１】
秘密鍵は、Ｆｐ上の３次元多様体Ａのｎ個のセクション
Ｄｉ：（ｘ，ｙ，ｓ，ｔ）＝（ｕｘ，ｉ（ｓ，ｔ），ｕｙ，ｉ（ｓ，ｔ），ｓ，ｔ）である。
【００５２】
これらは後述する鍵生成方法で容易に求めることができる。
【００５３】
（１）署名生成処理
次に、署名生成処理の概要を述べる。署名生成処理ではまず署名生成したいメッセージ（以下では平文と呼ぶ）を整数ｍに変換する。変換の方法はメッセージをＪＩＳコードなどのコード体系を利用してコード化し、それを整数に読み換える方法が一般的である。
【００５４】
次に、変換された整数ｍをハッシュ関数ｈ（ｘ）にかけてハッシュ値ｈ（ｍ）を計算する。ここでハッシュ値ｈ（ｍ）は一般に１２０ビットないし１６０ビットあるので、例えば、ｈ（ｍ）＝ｈ０‖ｈ１‖…‖ｈｒ−１
と、複数のブロックｈ０、ｈ１、…ｈｒ−１に分割し、これらを変数ｔに関する１変数多項式
ｈ（ｔ）＝ｈｒ−１ｔｒ−１＋…＋ｈ１ｔ＋ｈ０
の係数に埋め込む（ハッシュ値埋め込み処理）。ハッシュ値の埋め込まれた１変数多項式をハッシュ値多項式ｈ（ｔ）と呼ぶ。ここでｈ（ｔ）をＦｐ上の多項式とするために、
各ｈｉ（０≦ｉ≦ｒ−１）はＦｐの元となるように取る必要がある。即ち、上記ハッシュ値は、ｐのビット長に基づいて、
０≦ｈｉ≦ｐ−１
となるようにハッシュ値を分割する。
【００５５】
次に、秘密鍵であるｎ個のセクションＤｉのなかからランダムに１つ選択する。選択されたセクション
Ｄｉ：（ｗｘ（ｓ，ｔ），ｗｙ（ｓ，ｔ），ｓ，ｔ）
に対して、その変数ｓに上記ハッシュ値多項式ｈ（ｔ）を代入する。即ち、
（ｗｘ（ｈ（ｔ），ｔ），ｗｙ（ｈ（ｔ），ｔ），ｈ（ｔ），ｔ）
これを整理して、
Ｄｓ：（ｘ，ｙ，ｔ）＝（Ｗｘ（ｔ），Ｗｙ（ｔ），ｔ） …（３）
とし、これをメッセージｍに対するデジタル署名Ｄｓとしてメッセージｍと共に受信者に送信する。
【００５６】
以上の説明からもわかるように、式（３）に示すデジタル署名Ｄｓは、秘密鍵として用いたセクションＤｉ上の曲線である。
【００５７】
ここで、安全性の観点からＷｘ（ｔ）、Ｗｙ（ｔ）の次数が選択したセクションによらず一定であることが望ましい。これはセクションに現れる多項式ｕｘ，ｉ（ｓ，ｔ）に対して、
【数９】
【００５８】
とするとき、全てのｉに対してｕｘ，ｉ（ｓ，ｔ）がｓｈｘｔｋｘ の項を含むようにすることで解決できる。なぜならば、このようにすることによって、ハッシュ値多項式ｈ（ｔ）をどのセクションのｓに代入しても、得られる多項式Ｗｘ（ｔ）の最大次数の項はｈ（ｔ）をｓｈｘｔｋｘ の項に代入した多項式から生じるためである。
【００５９】
ｕｙ，ｉ（ｓ，ｔ）に関しても同様の手段でＷｙ（ｔ）の次数をｉによらず一定に保つことができる。このような鍵（セクションとそれに対応する３次元多様体）を生成する方法は後に示す。
【００６０】
（２）署名検証処理
デジタル署名Ｄｓ（ｘ，ｙ，ｔ）を受け取った受信者は所有する有限体Fｐ上定義された公開鍵Ａ（ｘ，ｙ，ｓ，ｔ）を利用して次のように署名検証処理を行う。
【００６１】
まず、前述の署名生成処理と同様に、メッセージ（以下では平文と呼ぶ）を整数ｍに変換する。変換の方法は署名生成処理と同じである。次に変換された整数ｍを上述の署名生成処理と同じハッシュ関数ｈ（ｘ）にかけてハッシュ値ｈ（ｍ）を計算する。更に前述の署名生成処理と同様に、ハッシュ値を、ｈ（ｍ）＝ｈ０‖ｈ１‖…‖ｈｒ−１
と、複数のブロックｈ０、ｈ１、…ｈｒ−１に分割し、これらを変数ｔに関する有限体Fｐ上定義された１変数多項式
ｈ（ｔ）＝ｈｒ−１ｔｒ−１＋…＋ｈ１ｔ＋ｈ０
の係数に埋め込み、ハッシュ値の埋め込まれたハッシュ値多項式ｈ（ｔ）を生成する。
【００６２】
次に、公開鍵である３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）の変数ｓに、生成したハッシュ値多項式ｈ（ｔ）を代入して、代数曲面
Ｘ（ｘ，ｙ，ｔ）＝Ａ（ｘ，ｙ，ｈ（ｔ），ｔ）
を生成する。このＸ（ｘ，ｙ，ｔ）もファイブレーションを持つ代数曲面である。
【００６３】
次に、得られた代数曲面Ｘに、（受信側が受け取った）式（３）で表現されたデジタル署名を代入する。このとき値が「０」になればデジタル署名が正しく、「０」でなければデジタル署名が正しくないことを意味する。
【００６４】
なぜならば、前述のデジタル署名生成処理においては、秘密鍵として与えられたセクションのうちランダムに選択されたセクションＤｉに対して、ｓ＝ｈ（ｔ）を代入していた。一方、これは前述のデジタル署名検証処理で行った３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）にｓ＝ｈ（ｔ）を代入して得られた代数曲面Ｘ（ｘ，ｙ，ｔ）のセクションに対応している。従って、前述のデジタル署名検証処理のような代入操作を行うと、値が「０」となる。
【００６５】
更に、ｓ＝ｈ（ｔ）を代入して得られる代数曲面もそのセクションを求めることは３次元多様体と同様に難しく多次多変数方程式の求解問題に帰着することが知られている。このため、後述する安全性署名の項目でも詳しく述べるように、３次元多様体のセクションを知らない第三者がメッセージに対応した代数曲面のセクションを提示することは当該代数曲面のセクションを求める問題に帰着する。このため（計算量の観点で）不可能であるといえる。このことが本発明のデジタル署名が安全であることの根拠である。
【００６６】
（３）鍵生成方法
鍵生成方法を説明する。本実施形態の鍵生成は、セクションＤ１、Ｄ２をランダムに選び、それに対応したファイブレーションを計算することによって行う。但し、生成された３次元多様体が２つのセクションを同時に持つようにするために以下のような工夫が必要となる。
【００６７】
ここでは簡単のため３次元多様体のうち、次のファイブレーションを持つ３次元多様体を例にとって鍵生成方法を示す。
【数１０】
【００６８】
ここで、ａ（ｓ，ｔ），ｂ（ｓ，ｔ）は２変数多項式である。まず、素体の標数ｐを決める。このときｐは小さくても安全性に問題は生じない。さて、セクションＤ１，Ｄ２を
【数１１】
【００６９】
とおいて、３次元多様体Ａに代入し、
【数１２】
【００７０】
を得る。これらを辺々引くとｂ（ｓ，ｔ）が消え、
【数１３】
【００７１】
となる。ａ（ｓ，ｔ）を２変数多項式とするには、たとえば
【数１４】
【００７２】
であれば十分である。このことを利用して以下に示すアルゴリズムで鍵生成を行うことができる。
【００７３】
ここで、ｋ１（ｓ，ｔ）｜ｋ２（ｓ，ｔ）は、多項式ｋ１（ｓ，ｔ）が、
多項式ｋ２（ｓ，ｔ）を割り切ることを意味している。
【００７４】
まず、λｘ（ｓ，ｔ）｜λｙ（ｓ，ｔ）となる２つの多項式をランダムに選択する。具体的にこのような多項式の組を求めるには、例えばλｘ（ｓ，ｔ）をランダムに与えて、同じくランダムな多項式ｃ（ｓ，ｔ）によってλｙ（ｓ，ｔ）＝ｃ（ｓ，ｔ）λｘ（ｓ，ｔ）を計算することによって、λｙ（ｓ，ｔ）を求めることで実現できる。
【００７５】
次に、多項式ｖｘ（ｓ，ｔ）をランダムに選択し、
【数１５】
【００７６】
によって、ｕｘ（ｓ，ｔ）を計算する。同様に多項式ｖｙ（ｓ，ｔ）をランダムに選択し、
【数１６】
【００７７】
によって、ｕｙ（ｓ，ｔ）を計算する。このようにして計算されたｕｘ（ｓ，ｔ）、ｖｘ（ｓ，ｔ）、ｕｙ（ｓ，ｔ）、ｖｙ（ｓ，ｔ）を利用して、
【数１７】
【００７８】
を計算することにより、多項式ａ（ｓ，ｔ）が計算できる。更にｂ（ｓ，ｔ）は、上述のａ（ｓ，ｔ）を利用して、
【数１８】
【００７９】
によって得られる。
【００８０】
前述の鍵生成方法は、上記以外の３次元多様体であっても、例えば
【数１９】
【００８１】
という形の定義式を仮定すれば同様に可能であり、上述の例のみに限定されない。
【００８２】
一方で、上述の鍵生成方式では３つ以上のセクションを持つ代数曲面を生成することができない。また、上述の安全性上望ましい条件として挙げたデジタル署名
Ｄｓ：（ｘ，ｙ，ｔ）＝（Ｗｘ（ｔ），Ｗｙ（ｔ），ｔ）
に表われるＷｘ（ｔ）、Ｗｙ（ｔ）の次数を、選択したセクションによらず一定にするような公開鍵を生成することが困難である。これら両方を解決する鍵生成方法として、以下のような第２の鍵生成方法が考えられる。
【００８３】
まず、ｕｘ，ｉ（ｓ，ｔ）の最大次数の項ｓｈｘｔｋｘを決め、ｓの最大次数がｈｘ、ｔの最大次数がｋｘとなるように、ｎ個の２変数多項式ｕｘ，ｉ（ｓ，ｔ）を定める。また同様にしてｕｙ，ｉ（ｓ，ｔ）の最大次数の項ｓｈｙｔｋｙを決め、ｓの最大次数がｈｙ、ｔの最大次数がｋｙとなるように、ｎ個の２変数多項式ｕｙ，ｉ（ｓ，ｔ）を定める。
【００８４】
次に、これらの多項式から因子（ｘ−ｕｘ，ｉ（ｓ，ｔ））、（ｙ−ｕｙ，ｉ（ｓ，ｔ））を生成し、各ｉ（１≦ｉ≦ｎ）について、ｉが同じ値の２つの因子（ｘ−ｕｘ，ｉ（ｓ，ｔ））及び（ｙ−ｕｙ，ｉ（ｓ，ｔ））を、左辺と右辺のそれぞれに振り分ける。そして、左辺に振り分けられたｎ個の因子の積と、右辺に振り分けられたｎ個の因子の積とを等号で結ぶことにより、次式（６）に示すような方程式を得る。
【数２０】
【００８５】
式（６）は、前記条件を満たす方程式となる。ここで、例えば、
Ｄｉ：（ｕｘ，ｉ（ｓ，ｔ），ｕｙ，ｉ（ｓ，ｔ），ｓ，ｔ）がセクションとなる。
【００８６】
更に、これらのセクションは、その作り方からｈ（ｔ）を代入しても、同じ次数のデジタル署名Ｄｓ：（Ｗｘ（ｔ），Ｗｙ（ｔ），ｔ）が生成される。実際には式（６）のままであるとセクションがすぐ分かってしまうので、展開することによって公開鍵である３次元多様体を得る。
【００８７】
一方で、式（６）ではｘの因子が右辺に、ｙの因子が左辺に分かれているため因数分解によってセクションを求めることが容易となる場合がある。そこで、例えば
【数２１】
【００８８】
などのように、ｘの因子とｙの因子をランダムに両辺に分けて公開鍵暗号である３次元多様体を生成することが望ましい。このように公開鍵と秘密鍵を生成することによって一般にｎ個以上のセクションを持つ安全性の高い３次元多様体を生成することができる。尚、前記安全性の観点を除けば、ｕｘ，ｉ（ｓ，ｔ），ｕｙ，ｉ（ｓ，ｔ）の作り方に自由度を持たせることができる。
【００８９】
（４）安全性の証明
上述のデジタル署名の安全性証明に関して説明する。デジタル署名の安全性は、メッセージ（平文）とデジタル署名のペアを作成する問題が多項式時間で解ければ３次元多様体のセクションを求める問題を多項式時間で求めることができ、逆に３次元多様体のセクションを求める問題を多項式時間で求めることができれば、メッセージ（平文）とデジタル署名のペアを作成することが多項式時間で可能なことを証明することによって証明することができる。即ち、上記の事実を理論的に証明することによって、メッセージ（平文）とデジタル署名のペアを作成可能なこと（存在的偽造可能であること）と、３次元多様体のセクションを求める問題が解けることが同値であることが示せるので、安全性の根拠としている３次元多様体のセクションを求める問題が困難であれば、デジタル署名が存在的偽造不可能であることが示されるからである。以上の方針に従った安全性証明を次に示す。
【００９０】
ここで、２次元セクションＤをＤ＝（ｄｘ（ｓ，ｔ），ｄｙ（ｓ，ｔ），ｓ，ｔ）と書いたとき、２次元セクションの次数を、ｄｘ（ｓ，ｔ），ｄｙ（ｓ，ｔ）の次数の最大値、
ｍａｘ｛ｄｅｇ（ｄｘ（ｓ，ｔ）），ｄｅｇ（ｄｙ（ｓ，ｔ））｝とする。
【００９１】
［定理１］ｎ次のセクションを持つ有限体Fｐ上定義された３次元多様体の求セクション問題が計算困難であることと、本発明のデジタル署名は存在的偽造不可能の意味で安全であることは同値である。
【００９２】
［証明１］本実施形態のデジタル署名による平文と署名の具体的なペアを多項式時間内に計算できるアルゴリズムαが存在したとする。このとき、このアルゴリズムαを利用して３次元多様体の２次元セクションを求める多項式時間アルゴリズムが存在することを示す。
【００９３】
まず、２次元セクションを求めたい３次元多様体をＡ（ｘ，ｙ，ｓ，ｔ）とする。次にＡ（ｘ，ｙ，ｓ，ｔ）を公開鍵とするデジタル署名方式を考え、アルゴリズムαを利用して多項式個の平文と署名のペアを生成する。ここで、平文ｍｉに対するハッシュ値多項式をｈｉ（ｔ）とし、その署名を
【数２２】
【００９４】
とする。ここで、ｆｉ（ｓ，ｔ），ｇｉ（ｓ，ｔ）は３次元多様体Ａのセクションのｘ，ｙ座標に対応するもので、高々有限個しか存在しない。従って、一定数以上の署名を集めれば、ｆｉ（ｓ，ｔ），ｇｉ（ｓ，ｔ）は全て異なるものではなく、その幾つかは同一となる。これらのうちどれが同じものであるかは以下の方法で判定できる。
【００９５】
３次元多様体Ｂ（ｘ，ｙ，ｓ，ｔ）（＝Ａ（ｘ，ｙ，ｔ，ｓ））を考える。このＢ（ｘ，ｙ，ｓ，ｔ）は３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）のｓとｔを交換したものであり、セクションの次数の定義からｎ次のセクションを持っている。そこで、アルゴリズムαを利用して、１つの平文と署名のペアを生成する。その際、特にハッシュ値多項式ｈｉ（ｓ）が定数ｈｉ（ｓ）＝ｈ０となるものを選び、生成された署名を
【数２３】
【００９６】
とすると、
【数２４】
【００９７】
は、ｓでパラメタライズされたＡ（ｘ，ｙ，ｓ，ｔ）の１つの１次元サイクルを与える。ここでサイクルとは部分多様体のことを意味し、特に１次元サイクルとは１次元の部分多様体である。このサイクルＤを利用して、１次元サイクル
【数２５】
【００９８】
のうち、Ｄと同じＸのセクションの上に存在するものを以下の多項式アルゴリズムで見出す。
【００９９】
まず、（ｓ，ｔ）＝（ｈｉ（ｈ０），ｈ０）とおくと、Ｄ上の点（ζ（ｈｉ（ｈ０），ｈ０），η（ｈｉ（ｈ０），ｈ０），ｈｉ（ｈ０），ｈ０）とＤｓ（ｉ）上の点（ｆｉ（ｈｉ（ｈ０），ｈ０），ｇｉ（ｈｉ（ｈ０），ｈ０），ｈｉ（ｈ０），ｈ０）が定まる。そして、Ｘのセクションが（ｓ，ｔ）を座標とする平面に同型であることに注意すると、
【数２６】
【０１００】
であればＤｓ（ｉ）とＤは同一のセクションの上に存在する。等しくなければＤｓ（ｉ）とＤとは同一のセクションの上にはない。ここで同じセクションに含まれる１次元サイクル群を、
【数２７】
【０１０１】
とする。さて、ここで３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）のセクション（ｗｘ（ｓ，ｔ），ｗｙ（ｓ，ｔ），ｓ，ｔ）を
【数２８】
【０１０２】
と書くと、式（８）の１次元セクションを代入することによって、
【数２９】
【０１０３】
を得る。この両辺をｔの冪毎にその係数を比較することによって、ａｉｊの連立１次方程式が得られる。連立１次方程式は多項式時間の解法が存在するので、多項式時間で全ての
ａｉｊが求まる。同様にｂｉｊも多項式時間で求まるので、３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）のセクションが多項式時間で求まることが示せた。
【０１０４】
逆に、３次元多様体の２次元セクションを求める多項式時間アルゴリズムβが存在したとする。このとき、このアルゴリズムβを利用して、本実施形態のデジタル署名による平文と署名の具体的なペアを多項式時間内に計算できることを示す。
【０１０５】
本実施形態のデジタル署名の公開鍵である３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）が与えられたとき、アルゴリズムβを利用して、その２次元セクション
Ｄ：（ｗｘ（ｓ，ｔ），ｗｙ（ｓ，ｔ），ｓ，ｔ）
を求める。ここで平文ｍを適当に決め、そのハッシュ値多項式をｈ（ｔ）とした時、
ｓ＝ｈ（ｔ）と置くことにより、署名
Ｄｓ：（ｗｘ（ｈ（ｔ），ｔ），ｗｙ（ｈ（ｔ），ｔ），ｔ）
を得る。これにより平文と署名の具体的なペアを多項式時間内に計算可能である。
【０１０６】
以上により、定理が証明された。
【０１０７】
（５）バリエーション
本実施形態におけるバリエーションを述べる。第１のバリエーションはハッシュ値多項式をハッシュ値自体に置き換えるバリエーションである。本実施形態におけるデジタル署名生成処理においては、平文ｍからハッシュ値ｈ（ｍ）を計算し、ハッシュ値ｈ（ｍ）をハッシュ値多項式ｈ（ｔ）に展開して、ランダムに選択したセクションＤｉにｓ＝ｈ（ｔ）と代入していた。
【０１０８】
しかし、ハッシュ値をハッシュ値多項式に埋め込まないような実施形態も成立する。即ち、セクションＤｉに、ハッシュ値ｈ（ｍ）そのものを、ｓ＝ｈ（ｍ）として代入することにより、デジタル署名
Ｄｓ：（ｗｘ（ｈ（ｍ），ｔ），ｗｙ（ｈ（ｍ），ｔ），ｔ）
が生成できる。この場合は、デジタル署名検証処理においても同様に公開鍵である３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）への代入をｓ＝ｈ（ｍ）によって行うことにより、同様の手段で署名検証が可能となる。
【０１０９】
実際に、このバリエーションが成り立つことは、本実施形態におけるハッシュ値多項式ｈ（ｔ）を定数項だけからなる多項式と考えれば理解することができる。即ち、本バリエーションは本実施形態の特別な場合と言うことができる。本バリエーションを利用することによってデジタル署名生成処理、デジタル署名検証処理における多項式演算を軽減でき、計算メモリ量や計算処理時間を削減することが可能となる。しかし、その反面でハッシュ値は最小でも１２０ビットであるため定義体であるＦｐのｐのサイズを１２０ビット程度に大きくしなければならず、多倍長演算が必要となるという弱点も持ち合わせており、
適用有効範囲は限定される。
【０１１０】
第２のバリエーションは、本実施形態のデジタル署名生成装置、デジタル署名検証装置においてハッシュ値多項式を代入する変数の変更に関するバリエーションである。本実施形態のデジタル署名生成装置、デジタル署名検証装置においては、ハッシュ値多項式としてｈ（ｔ）という変数ｔによる１変数多項式を取り、秘密鍵であるセクション若しくは公開鍵である３次元多様体の変数ｓに代入していたが、これを以下のように変更しても本発明は安全性も含めて同様に成立する。
【０１１１】
即ちハッシュ値多項式として、ｈ（ｓ）という変数ｓによる１変数多項式を取り、秘密鍵であるセクション若しくは公開鍵である３次元多様体の変数ｔに代入する。変数ｓ，ｔは共にパラメータなので本バリエーションによってその効果は変わらない。
【０１１２】
（６）構成
次に、本実施形態のデジタル署名方式に係る鍵生成装置、デジタル署名生成装置、デジタル署名検証装置の構成例と、これらの処理動作について説明する。
【０１１３】
図２は、鍵生成装置の構成例を示したもので、図３は、図２の鍵生成装置の処理動作を説明するためのフローチャートである。以下、図３に示すフローチャートを参照して、図２の鍵生成装置の構成及び処理動作について説明する。尚、理解の助けとして具体的な数値や式を示すが、これはあくまでも理解を助けるための例であって、実際に使われる十分な安全性を持つデジタル署名とは（特に多項式の次数などの点で）必ずしも一致していない。
【０１１４】
なお、ここでは、前述した、ｙ２＝ｘ３＋ａ（ｓ，ｔ）ｘ＋ｂ（ｓ，ｔ）というファイブレーションをもつ３次元多様体を例にとり説明する。
【０１１５】
鍵生成処理開始の指令が外部装置等から制御部１に伝えら、鍵生成装置は鍵生成処理を開始する（ステップＳ１）。当該指令が制御部１に伝わると、制御部１は、素数生成部２に素数の生成を要請する。素数生成はランダムに素数を発生させても良いが、ここでは大きな素数を使う必要はないので、高々６ビット程度の素数からランダム若しくは（出力順を予め決めておくなどの手段で）恣意的に選択するか、当該鍵生成装置で予め定まっている素数を利用してもよい。ここでは素数ｐ＝１７が生成されたとする（ステップＳ２）。
【０１１６】
制御部１は、セクション生成部５に、素数ｐを出力し、セクション生成部５では、セクションの生成を開始する。セクション生成部５は、まず、素数ｐを２変数多項式生成部３に出力し、２変数多項式生成部３は、２変数多項式λｘ（ｓ，ｔ）（＝−ｓ（ｔ−１））を生成する（ステップＳ３）。２変数多項式生成部３では、予め定められた一定範囲内で次数をランダムに選択し、その次数を持つ２変数多項式の係数を有限体Ｆｐの元として０からｐ−１までの範囲でそれぞれ生成する。
【０１１７】
２変数多項式生成部３は、λｘ（ｓ，ｔ）を生成すると、これを制御部１へ出力する。制御部１は、λｘ（ｓ，ｔ）を得ると、上記同様に、ランダムな２変数多項式ｃ（ｓ，ｔ）の生成処理を行い、ｃ（ｓ，ｔ）（＝ｓ＋ｔ）を得る（ステップＳ４）。
【０１１８】
制御部１は、ｃ（ｓ，ｔ）とλｘ（ｓ，ｔ）を２変数多項式演算部４に出力する。
【０１１９】
２変数多項式演算部４では、λｙ（ｓ，ｔ）＝ｃ（ｓ，ｔ）λｘ（ｓ，ｔ）を計算し（ステップＳ５）、制御部１へλｙ（ｓ，ｔ）（＝−（ｓ＋ｔ）ｓ（ｔ−１））を出力する。
【０１２０】
λｙ（ｓ，ｔ）を受け取った制御部１では、次にλｘ（ｓ，ｔ）の生成と同様の方法で２変数多項式ｖｘ（ｓ，ｔ）（＝２ｓｔ）をランダムに生成し（ステップＳ６）、λｘ（ｓ，ｔ）（＝−ｓ（ｔ−１））とｖｘ（ｓ，ｔ）（＝２ｓｔ）を２変数多項式演算部４へ出力する。
【０１２１】
２変数多項式演算部４は、ｕｘ（ｓ，ｔ）（＝λｘ（ｓ，ｔ）＋ｖｘ（ｓ，ｔ）＝ｓ（ｔ＋１））を計算し、これを制御部１へ出力する（ステップＳ７）。
【０１２２】
制御部１は、ステップＳ６と同様に、ｖｙ（ｓ，ｔ）（＝２ｓｔ２＋ｓ＋ｓ２ｔ−ｓ２−ｓｔ）を生成し（ステップＳ８）、さらに、
ｕｙ（＝λｙ（ｓ，ｔ）＋ｖｙ（ｓ，ｔ）＝ｓ（ｔ２＋１））を計算する（ステップＳ９）。
【０１２３】
制御部１は、ｕｘ（ｓ，ｔ）、ｕｙ（ｓ、ｔ）、ｖｘ（ｓ，ｔ）、ｖｙ（ｓ，ｔ）を３次元多様体生成部６に出力する。
【０１２４】
３次元多様体生成部６は、２変数多項式演算部４を繰り返し使うことにより、式（４）に用いて、３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）：ｙ２＝ｘ３＋ａ（ｓ，ｔ）ｘ＋ｂ（ｓ，ｔ）のパラメータｓ、ｔに関する２変数多項式ａ（ｓ，ｔ）を計算する（ステップＳ１０）。
【０１２５】
この例では
【数３０】
【０１２６】
と求まる。さらに、式（５）を用いて、ａ（ｓ、ｔ）とｕｘ（ｓ，ｔ）、ｕｙ（ｓ，ｔ）、ｖｘ（ｓ，ｔ）、ｖｙ（ｓ，ｔ）から、２変数多項式演算部４を繰り返し使うことにより、パラメータｓ、ｔに関する２変数多項式ｂ（ｓ，ｔ）を計算する（ステップＳ１１）。
【０１２７】
この例では、
【数３１】
【０１２８】
を得る。
【０１２９】
３次元多様体生成部６は、得られたａ（ｓ，ｔ）、ｂ（ｓ，ｔ）を制御部１に出力する。
【０１３０】
制御部１は、３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）を表す多項式：ｙ２＝ｘ３＋ａ（ｓ，ｔ）ｘ＋ｂ（ｓ，ｔ）に、ステップＳ１０及びステップＳ１１で得られたａ（ｓ，ｔ）とｂ（ｓ，ｔ）を代入することで、次式（９）に示すような、公開鍵である３次元多様体ＡのファイブレーションＡ（ｘ，ｙ，ｓ，ｔ）の多項式を生成する。
【０１３１】
また、次式（１０）に示すように、２変数多項式ｕｘ（ｓ，ｔ）をｘ座標、２変数多項式ｕｙ（ｓ，ｔ）をｙ座標とするセクションＤ１：（ｘ，ｙ，ｓ，ｔ）と、２変数多項式ｖｘ（ｓ，ｔ）をｘ座標、２変数多項式ｖｙ（ｓ，ｔ）をｙ座標とするセクションＤ２：（ｘ，ｙ，ｓ，ｔ）を生成する（ステップＳ１２）。
【数３２】
【０１３２】
制御部１は、生成された公開鍵と秘密鍵を鍵出力部７に出力し、鍵出力部７は、公開鍵と秘密鍵を出力する。
【０１３３】
なお、図２に示す各機能（制御部１、素数生成部２、２変数多項式３、２変数多項式演算部４、セクション生成部５、３次元多様体生成部６、鍵出力部７など）は、図１０に示すように、各種プログラムなどを記憶する記憶部１０１、ＣＰＵなどの演算部１００、出力部１０２、入力部１０３、通信部１０４などをバスに接続してなるコンピュータに、記憶部１０１に記憶されている各プログラムを実行させることにより、実現することができる。
【０１３４】
図１０では、記憶部１０１には、制御部１、素数生成部２、２変数多項式生成部３、２変数多項式演算部４、セクション生成部５、３次元多様体生成部６、鍵出力部７のそれぞれの機能を実現すための鍵生成制御プログラム、素数生成プログラム、２変数多項式生成プログラム、２変数多項式演算プログラム、セクション生成プログラム、３次元多様体生成プログラム、鍵出力プログラムが記憶されている。
【０１３５】
図２の鍵出力部７から出力された秘密鍵や公開鍵は、例えば、通信部１０４を介して要求元へ送信されたり、後述するデジタル署名生成装置やデジタル署名検証装置へ渡される。
【０１３６】
図４は、デジタル署名生成装置の構成例を示したもので、図５は、図４のデジタル署名生成装置の処理動作を説明するためのフローチャートである。以下、図５に示すフローチャートを参照して、図４のデジタル署名生成装置の構成及び処理動作について説明する。
【０１３７】
図４のデジタル署名生成装置は、平文入力部１１から平文ｍを取得し、秘密鍵入力部１４から秘密鍵であるセクション群Ｄｉ（ｕｘ（ｓ，ｔ），ｕｙ（ｓ，ｙ），ｓ，ｔ）（０≦ｉ≦ｎ）を取得する。
【０１３８】
ここで、秘密鍵を前述の鍵生成処理で生成された
１．素体の標数ｐ＝１７
２．式（１０）に示した有限体Fｐ上定義された３次元多様体Ａの２つのセクションを利用する。尚、全ての演算は鍵生成処理で決定した有限体Ｆ１７で行う。
【０１３９】
まず、平文入力部１１から平文ｍが入力されることによって、デジタル署名生成処理が開始される（ステップＳ１０１）。入力された平文ｍは、ハッシュ値計算部１２に出力され、ＳＨＡ１やＭＤ５などのハッシュ関数を利用してハッシュ値ｈ（ｍ）が計算される。ここでは、簡単のため、ハッシュ値を「０ｘ１５１」とするが、本来は１２０ビット以上である必要がある。計算されたハッシュ値は、ハッシュ値多項式生成部１３に送られ、予め定められた複数のブロックに分割される。ここでは、ｐ＝１７であることから４ビット毎に分割し、各ブロックをハッシュ値多項式ｈ（ｔ）の係数に埋め込む（ステップＳ１０３）。その結果得られるハッシュ値多項式ｈ（ｔ）は ｈ（ｔ）＝ｔ２＋５ｔ＋１ となる。
【０１４０】
秘密鍵記憶部１８には、図２や後述の図８に示した構成の鍵生成装置で生成された秘密鍵である少なくとも１つのセクションを記憶する。
【０１４１】
秘密鍵入力部１４は、秘密鍵記憶部１８から秘密鍵であるセクション群を読み出して、署名生成部１５へ出力する（ステップＳ１０４）。秘密鍵記憶部１８には、複数のセクションが記憶されていることが望ましい。ここでは、式（１０）に示した２つのセクションＤ１、Ｄ２が秘密鍵記憶部１８に記憶されており、秘密鍵入力部１４は、この２つのセクションＤ１、Ｄ２を秘密鍵記憶部１８から読み出し、署名生成部１５へ出力する。これらセクション群は、署名生成部１５から、セクション選択部１６に出力される。セクション選択部１６は、入力されたセクション群のうちから１つのセクションをランダムに選択する（ステップＳ１０５）。ここではＤ１が選択されたとする。選択されたセクションＤ１は、署名生成部１５に出力される。なお、秘密鍵記憶部１８に秘密鍵が１つのみ記憶されている場合には、セクション選択部１６の上記処理は省略される。
【０１４２】
選択されたセクションＤ１を受信した署名生成部１５は、ハッシュ値多項式生成部１３から、ステップＳ１０３で生成されたハッシュ値多項式ｈ（ｔ）を取得して、選択されたセクションＤ１のｓ座標にｈ（ｔ）を代入して（ｓ＝ｈ（ｔ））、セクションＤｓを生成する（ステップＳ１０６）。
【０１４３】
ここでは、次式（１１）に示すようなセクションＤｓが生成される。
【数３３】
【０１４４】
このセクションＤｓは、デジタル署名として署名出力部１７から出力される（ステップＳ１０７）。
【０１４５】
前述の第１、第２のバリエーションは本実施形態において同様の処理で成立する。尚、第１のバリエーションを利用する場合は現状では（ハッシュ値の大きさを考慮して）ｐを１２０ビット以上とする必要がある。
【０１４６】
なお、図４に示す各機能（平文入力部１１、ハッシュ値計算部１２、ハッシュ値多項式生成部１３，秘密鍵入力部１４、署名生成部１５、セクション選択部１６，署名出力部１７など）は、図１１に示すように、各種プログラムなどを記憶する記憶部１０１、ＣＰＵなどの演算部１００、出力部１０２、入力部１０３、通信部１０４などをバスに接続してなるコンピュータに、記憶部１０１に記憶されている各プログラムを実行させることにより、実現することができる。
【０１４７】
図１１では、記憶部１０１には、平文入力部１１、ハッシュ値計算部１２、ハッシュ値多項式生成部１３，秘密鍵入力部１４、署名生成部１５、セクション選択部１６，署名出力部１７のそれぞれの機能を実現すための平文入力プログラム、ハッシュ値計算プログラム、ハッシュ値多項式生成プログラム、秘密鍵入力プログラム、署名生成プログラム、セクション選択プログラム，署名出力プログラムが記憶されている。また、記憶部１０１は、秘密鍵を記憶する秘密鍵記憶部１８としても機能する。
【０１４８】
平文入力部１１で入力されたメッセージｍと、署名出力部１７で出力されたデジタル署名は、例えば、通信部１０４を介して相手端末へ送信される。
【０１４９】
図６は、デジタル署名検証装置の構成例を示したもので、図７は、図６のデジタル署名検証装置の処理動作を説明するためのフローチャートである。以下、図７に示すフローチャートを参照して、図６のデジタル署名検証装置の構成及び処理動作について説明する。
【０１５０】
図６のデジタル署名生成装置は、平文入力部２１から平文ｍを取得し、公開鍵入力部２４から公開鍵である有限体Fｐ上定義された３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）を取得する。
【０１５１】
まず、平文入力部２１から平文ｍが入力されることよって、デジタル署名検証処理が開始される（ステップＳ２０１）。
【０１５２】
入力された平文ｍは、ハッシュ値計算部２２に出力され、署名生成装置で用いられたものと同じハッシュ関数を利用してハッシュ値が計算される（ステップＳ２０２）。ここでは、ハッシュ値は署名生成装置で出力したハッシュ値と同じ「０ｘ１５１」となる。このハッシュ値は、ハッシュ値多項式生成部２３に出力される。
【０１５３】
ハッシュ値多項式生成部２３では、デジタル署名検証装置と同じアルゴリズムで、ハッシュ値多項式ｈ（ｔ）を計算する（ステップＳ２０３）。従って、ここで得られる、ハッシュ値多項式ｈ（ｔ）は、ｈ（ｔ）＝ｔ２＋５ｔ＋１ となる。
【０１５４】
得られたハッシュ値多項式ｈ（ｔ）は、署名検証部２６へ出力される。
【０１５５】
公開鍵記憶部２９は、図２や後述の図８に示した構成の鍵生成装置で生成された公開鍵である有限体Fｐ上定義された３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）の多項式を記憶する。
【０１５６】
公開鍵入力部２４は、公開鍵記憶部２９から公開鍵である３次元多様体の多項式を読み出して、署名生成部１５へ出力する（ステップＳ２０４）。ここでは、式（９）に示した３次元多様体、すなわち、公開鍵が署名検証部２６へ入力される。署名検証部２６は、入力された公開鍵を代数曲面生成部２７に出力する。
【０１５７】
署名検証部２６は、ステップＳ２０３で生成されたハッシュ値多項式ｈ（ｔ）を代数曲面生成部２７へ出力する。
【０１５８】
代数曲面生成部２７は、３次元多様体の変数ｓに、署名検証部２６から出力されたハッシュ値多項式ｈ（ｔ）を代入して、代数曲面Ｘ（ｘ，ｙ，ｔ）を生成する（ステップＳ２０５）。ここでは、次式（１２）に示すような代数曲面Ｘ（ｘ，ｙ，ｔ）が得られる。
【数３４】
【０１５９】
次に、署名入力部２５に入力された式（１１）に示した署名Ｄｓ：（Ｕｘ（ｔ），Ｕｙ（ｔ），ｔ）を署名検証部２６が読み込む（ステップＳ２０６）。この署名Ｄｓのｘ座標Ｕｘ（ｔ）＝ｔ３＋６ｔ２＋６ｔ＋１、ｙ座標Ｕｙ（ｔ）＝ｔ４＋５ｔ３＋２ｔ２＋５ｔ＋１を、それぞれ、式（１２）に示した代数曲面Ｘのｘ，ｙ座標に代入して、展開・整理する（ステップＳ２０７）。前述の通り、デジタル署名Ｄｓは代数曲面Ｘの因子となっているため、代入して整理すれば「０」となるはずである。従って、「０」となれば（ステップＳ２０８）、判定結果出力部２８に、「署名検証成功」を出力する（ステップＳ２０９）。「０」とならなければ、デジタル署名が間違っていたことを意味するので（ステップＳ２０８）、判定結果出力部２８に、「署名検証失敗」を出力する（ステップＳ２１０）。
【０１６０】
判定結果出力部２８は、判定結果を外部へ出力して、全ての処理を終了する。
【０１６１】
ここで示した例では、正当なデジタル署名なので、ステップＳ２０７で、代数曲面Ｘにデジタル署名Ｄｓ代入して整理した結果は、確かに「０」となり、署名検証部２６は、判定結果出力部２８に「署名検証成功」を出力し、判定結果出力部２８はそれを外部に出力して終了する。
【０１６２】
第１、第２のバリエーションは本実施形態において同様の処理で成立する。
【０１６３】
なお、図６に示す各機能（平文入力部２１、ハッシュ値計算部２２、ハッシュ値多項式生成部２３，公開鍵入力部２４、署名入力部２５、署名検証部２６、代数曲面生成部２７、判定結果出力部２８など）は、図１２に示すように、各種プログラムなどを記憶する記憶部１０１、ＣＰＵなどの演算部１００、出力部１０２、入力部１０３、通信部１０４などをバスに接続してなるコンピュータに、記憶部１０１に記憶されている各プログラムを実行させることにより、実現することができる。
【０１６４】
図１２では、記憶部１０１には、平文入力部２１、ハッシュ値計算部２２、ハッシュ値多項式生成部２３，公開鍵入力部２４、署名入力部２５、署名検証部２６、代数曲面生成部２７、判定結果出力部２８のそれぞれの機能を実現すための平文入力プログラム、ハッシュ値計算プログラム、ハッシュ値多項式生成プログラム、公開鍵入力プログラム、署名入力プログラム、署名検証プログラム、代数曲面生成プログラム、判定結果出力プログラムが記憶されている。また、記憶部１０１は、公開鍵を記憶する公開鍵記憶部２９として機能する。
【０１６５】
署名入力部２５には、デジタル署名生成装置で生成されたメッセージｍに対応するデジタル署名が入力される。
【０１６６】
次に、第２の鍵生成方法について説明する。図８は第２の鍵生成方法を用いた鍵生成装置の構成例を示したもので、図９は、図８の鍵生成装置の処理動作を説明するためのフローチャートである。以下、図９に示すフローチャートを参照して、図８の鍵生成装置の構成及び処理動作について説明する。
【０１６７】
鍵生成処理開始の指令が外部装置等から制御部１に伝えられ、鍵生成装置は鍵生成処理を開始する（ステップＳ３０１）。当該指令が制御部１に伝わると、制御部１は、素数生成部２に素数の生成を要請する。素数生成はランダムに素数を発生させても良いが、ここでは大きな素数を使う必要はないので、高々６ビット程度の素数からランダム若しくは（出力順を予め決めておくなどの手段で）恣意的に選択するか、当該鍵生成装置で予め定まっている素数を利用してもよい。ここでは素数ｐ＝１７が生成されたとする（ステップＳ３０２）。
【０１６８】
制御部１は、セクション生成部５に、素数ｐを送信し、セクション生成部５では、セクションの生成を開始する。セクション生成部５では、ｎ個のセクション
Ｄｉ：（ｘ，ｙ，ｓ，ｔ）＝（ｕｘ，ｉ（ｓ，ｔ），ｕｙ，ｉ（ｓ，ｔ），ｓ，ｔ）
（１≦ｉ≦ｎ）
のｘ座標ｕｘ，ｉ（ｓ，ｔ）、ｙ座標ｕｙ，ｉ（ｓ，ｔ）を以下に示す方法で決定する。
【０１６９】
まず、ｘ座標のｓに関する次元の最大値ｈｘ、ｔに関する次元の最大値ｋｘを定める（ステップＳ３０３）。即ち、
【数３５】
【０１７０】
ここでは、簡単のため、ｈｘ＝ｋｘ＝２とする。
【０１７１】
次に、ｓｈｘｔｋｘの項を含み、この次数の範囲内のセクションＤｉのｘ座標ｕｘ，ｉ（ｓ，ｔ）の生成を２変数多項式生成部３に要求する。ここでは、ｎ＝３であるので、２変数多項式生成部３は、ｕｘ，１（ｓ、ｔ）、ｕｘ，２（ｓ、ｔ）、ｕｘ，３（ｓ、ｔ）を、ランダムに順次決定する（ステップＳ３０４）。すなわち、
【数３６】
【０１７２】
が得られる。
【０１７３】
次に、ステップＳ３０３と同様に、ｙ座標のｓに関する次元の最大値ｈｙ、ｔに関する次元の最大値ｋｙを定める（ステップＳ３０５）。即ち、
【数３７】
【０１７４】
ここでは、簡単のためｈｙ＝ｋｙ＝２とする。
【０１７５】
次に、ｓｈｙｔｋｙの項を含み、この次数の範囲内のセクションＤｉのｙ座標ｕｙ，ｉ（ｓ，ｔ）の生成を２変数多項式生成部３に要求する。ここでは、ｎ＝３であるので、２変数多項式生成部３は、ｕｙ，１（ｓ、ｔ）、ｕｙ，２（ｓ、ｔ）、ｕｙ，３（ｓ、ｔ）を、ランダムに順次決定する（ステップＳ３０６）。すなわち、
【数３８】
【０１７６】
が得られる。
【０１７７】
以上で、セクションＤｉが生成された。
【０１７８】
これらセクションは制御部１に出力される。制御部１では、３次元多様体生成部６に、これらセクションを出力して、３次元多様体を生成させる。
【０１７９】
３次元多様体生成部６では、入力されたｕｘ，ｉ（ｓ，ｔ）、ｕｙ，ｉ（ｓ，ｔ）をそれぞれ、
ｘ因子（ｘ−ｕｘ，ｉ（ｓ，ｔ））、ｙ因子（ｙ−ｕｙ，ｉ（ｓ，ｔ））と因子化する（ステップＳ３０７）。
【０１８０】
そして、ｉが同じ値の因子ｘ（ｘ−ｕｘ，ｉ（ｓ，ｔ））及びｙ因子（ｙ−ｕｙ，ｉ（ｓ，ｔ））を、左辺と右辺にランダムに振り分ける。そして、左辺に振り分けられたｎ個の因子の積と、右辺に振り分けられたｎ個の因子の積とを等号で結ぶことにより、次式（１３）に示すような４変数（ｘ、ｙ、ｓ、ｔ）多項式を生成する。
【数３９】
【０１８１】
３次元多様体生成部６は、制御部１を介して、（もしくは直接）４変数多項式演算部８へ、上式（１３）の展開を依頼する。
【０１８２】
４変数多項式演算部８は、上式（１３）を展開して、当該４変数多項式に含まれる各項を、左辺と右辺のいずれか一方にまとめて、次式（１４）に示すような、３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）を得る（ステップＳ３０８）。
【数４０】
【０１８３】
４変数多項式演算部８は、得られた３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）を制御部１へ出力する。制御部１では３つのセクションと３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）を鍵として鍵出力部７へ出力し、鍵出力部７では、これらの鍵を出力する。
【０１８４】
なお、図８に示す各機能（制御部１、素数生成部２、２変数多項式生成部３、４変数多項式演算部８、セクション生成部５、３次元多様体生成部６、鍵出力部７など）は、図１３に示すように、各種プログラムなどを記憶する記憶部１０１、ＣＰＵなどの演算部１００、出力部１０２、入力部１０３、通信部１０４などをバスに接続してなるコンピュータに、記憶部１０１に記憶されている各プログラムを実行させることにより、実現することができる。
【０１８５】
図１３では、記憶部１０１には、制御部１、素数生成部２、２変数多項式生成部３、４変数多項式演算部８、セクション生成部５、３次元多様体生成部６、鍵出力部７のそれぞれの機能を実現すための鍵生成制御プログラム、素数生成プログラム、２変数多項式生成プログラム、４変数多項式演算プログラム、セクション生成プログラム、３次元多様体生成プログラム、鍵出力プログラムが記憶されている。
【０１８６】
図８の鍵出力部７から出力された秘密鍵や公開鍵は、例えば、通信部１０４を介して要求元へ送信されたり、後述するデジタル署名生成装置やデジタル署名検証装置へ渡される。
【０１８７】
図８の示す鍵生成装置の２変数多項式生成部３は、安全性を高めるため、セクションのｘ座標やｙ座標に対応する２変数多項式を生成する際、変数ｓ、ｔについての字数の最大値（ｘ座標の変数ｓの最大次数ｈｘ、ｘ座標の変数ｔの最大次数ｋｘ、ｙ座標の変数ｓの最大次数ｈｙ、ｙ座標の変数ｔの最大多項数ｋｙ）をそれぞれ定め、ｘ座標については、ｓｈｘｔｋｘの項を必ず含む２変数多項式を生成、ｙ座標については、ｓｈｙｔｋｙの項を必ず含む２変数多項式を生成している。
【０１８８】
しかし、この場合に限らず、次数が最大値ｈｘ以下の変数ｓと、次数が最大値ｋｘ以下の変数ｔとのうちの少なくとも１つを因子として有する複数の単項式とを含む２変数多項式ｕｘ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）や、次数が最大値ｈｙ以下の変数ｓと、次数が最大値ｋｙ以下の変数ｔとのうちの少なくとも１つを因子として有する複数の単項式とを含む２変数多項式ｕｙ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）を生成すれば、ｎ個のセクションを持つ３次元多様体を生成することができる。
【０１８９】
以上説明したように、上記実施形態によれば、メッセージ送信側のデジタル署名生成装置は有限体Fｐならびに、ｘ座標、ｙ座標、パラメータｓ、及びパラメータｔで表される前記有限体Fｐ上定義された３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）内の曲面のうち、ｘ座標及びｙ座標がパラメータｓ及びｔの関数で表されたセクションＤ（ｕｘ（ｓ，ｔ），ｕｙ（ｓ，ｙ），ｓ，ｔ）を、署名生成用の秘密鍵として記憶手段に記憶する。ＣＰＵ等の演算手段は、メッセージｍのハッシュ値を計算し、このハッシュ値を前記有限体Fｐ上定義された１変数多項式ｈ（ｔ）の係数に埋め込み、ハッシュ値多項式を生成する。そして、演算手段は、記憶手段からセクションを１つ読み出して、それを署名生成用の秘密鍵として用いて、デジタル署名を生成する。すなわち、セクションのｓ座標に上記ハッシュ値多項式を代入することで、ｘ座標及びｙ座標がパラメータｔの関数で表された前記セクション上の曲線であるデジタル署名Ｄｓ（Ｕｘ（ｔ），Ｕｙ（ｔ），ｔ）を生成する。このようにして生成されたデジタル署名は、上記メッセージｍとともに、メッセージ送信側の送信手段により、メッセージ受信側へ送信される。
【０１９０】
記憶手段は、異なる複数のセクションＤｉ（ｕｘ，ｉ（ｓ，ｔ），ｕｙ，ｉ（ｓ，ｔ），ｓ，ｔ）（ｉは、０≦ｉ≦ｎの任意の正の整数）を記憶し、デジタル署名を生成する度に、この記憶手段に記憶された複数のセクションＤｉのうちの任意の１つのセクションを選択して、デジタル署名を生成することにより、より安全性が高まる。
【０１９１】
また、メッセージ受信側のデジタル署名検証装置は、記憶手段に、有限体Fｐならびに公開鍵として、ｘ座標、ｙ座標、パラメータｓ、及びパラメータｔで表される前記有限体Fｐ上定義された３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）の多項式を記憶する。メッセージｍと当該メッセージｍに対応するデジタル署名Ｄｓ：（Ｕｘ（ｔ），Ｕｙ（ｔ），ｔ）とが入力されると、ＣＰＵ等の演算手段が、メッセージｍのハッシュ値を計算し、このハッシュ値を前記有限体Fｐ上定義された１変数多項式ｈ（ｔ）に埋め込み、ハッシュ値多項式を生成する。そして、演算手段は、記憶手段から上記メッセージ送信側に対応する公開鍵である３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）の多項式のｓ座標に、当該ハッシュ値多項式を代入して、ハッシュ値に対応した代数曲面Ｘ（ｘ，ｙ，ｔ）を計算する。さらに、演算手段は、代数曲面Ｘ（ｘ，ｙ，ｔ）に、上記デジタル署名を代入して、メッセージ及びデジタル署名の正当性を検証する。すなわち、代数曲面Ｘ（ｘ，ｙ，ｔ）のｘ座標に、デジタル署名のｘ座標（変数ｔの多項式で表された）Ｕｘ（ｔ）を代入し、代数曲面Ｘ（ｘ，ｙ，ｔ）のｙ座標に、デジタル署名のｙ座標（変数ｔの多項式で表された）Ｕｙ（ｔ）を代入した後、式を展開し（多項式の積を単項式の和の形で表す）、整理する。この結果（代数曲面Ｘ（ｘ，ｙ，ｔ）にデジタル署名のｘ座標およびｙ座標を代入した結果）が「０」であるとき、メッセージｍが改竄されていないこと、及び、メッセージｍが、上記公開鍵に対応する正当なメッセージ送信者から送信されたことが検証されたことになる（署名検証成功）。
【０１９２】
鍵生成装置では、ＣＰＵ等の演算手段が、前記有限体Fｐ上定義された、パラメータｓ、ｔに関する第１の２変数多項式λｘ（ｓ，ｔ）と、この第１の２変数多項式λｘ（ｓ，ｔ）で割り切れる、前記有限体Fｐ上定義された第２の２変数多項式λｙ（ｓ，ｔ）を生成し、次に、前記有限体Fｐ上定義された、変数ｘがパラメータｓ，ｔで表される２つの２変数多項式ｕｘ（ｓ，ｔ）、ｖｘ（ｓ，ｔ）を、当該２つの２変数多項式の差分｛ｕｘ（ｓ，ｔ）−ｖｘ（ｓ，ｔ）｝がλｘ（ｓ，ｔ）となるように生成し、さらに、前記有限体Fｐ上定義された、変数ｙがパラメータｓ，ｔで表される２つの２変数多項式ｕｙ（ｓ，ｔ）、ｖｙ（ｓ，ｔ）を、当該２つの２変数多項式の差分｛ｕｙ（ｓ，ｔ）−ｖｙ（ｓ，ｔ）｝がλｙ（ｓ，ｔ）となるように生成する。そして、演算手段は、２変数多項式ｕｘ（ｓ，ｔ）をｘ座標、２変数関数ｕｙ（ｓ，ｔ）をｙ座標とするセクションＤ１：（ｘ，ｙ，ｓ，ｔ）＝（ｕｘ（ｓ，ｔ），ｕｙ（ｓ，ｔ），ｓ，ｔ）と、２変数多項式ｖｘ（ｓ，ｔ）をｘ座標、２変数関数ｖｙ（ｓ，ｔ）をｙ座標とするセクションＤ２：（ｘ，ｙ，ｓ，ｔ）＝（ｖｘ（ｓ，ｔ），ｖｙ（ｓ，ｔ），ｓ，ｔ）を生成する。これら２つのセクションＤ１、Ｄ２が秘密鍵である。また、この２つのセクションＤ１，Ｄ２を持つ３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）を生成する。この３次元多様体Ａが、公開鍵である。
【０１９３】
他の鍵生成装置では、ＣＰＵ等の演算手段が、パラメータｓ、ｔに関する第１番目から第ｎ（ｎは正の整数）番目までのｎ（ｎは正の整数）個の前記有限体Fｐ上定義された２変数多項式ｕｘ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）と、パラメータｓ、ｔに関する第１番目から第ｎ番目までのｎ個の前記有限体Fｐ上定義された２変数多項式ｕｙ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）を生成する。演算手段は、生成された第ｉ（１≦ｉ≦ｎ）番目の２変数多項式ｕｘ，ｉ（ｓ，ｔ）及びｕｙ，ｉ（ｓ，ｔ）をそれぞれｘ座標、ｙ座標とする第ｉ番目のセクションＤｉ：（ｘ，ｙ，ｓ，ｔ）＝（ｕｘ，ｉ（ｓ，ｔ）、ｕｙ，ｉ（ｓ，ｔ），ｓ，ｔ）（１≦ｉ≦ｎ）を生成することにより、第１番目から第ｎ番目までのｎ個のセクションＤｉ（１≦ｉ≦ｎ）を求める。このｎ個のセクションが秘密鍵である。さらに、演算手段は、生成された第ｉ（１≦ｉ≦ｎ）番目の２変数多項式ｕｘ，ｉ（ｓ，ｔ）及びｕｙ，ｉ（ｓ，ｔ）を用いて、第ｉ番目のｘ因子（ｘ−ｕｘ，ｉ（ｓ，ｔ））及びｙ因子（ｙ−ｕｙ，ｉ（ｓ，ｔ））を生成することにより、第１番目から第ｎ番目までのｘ因子及びｙ因子を求める。演算手段は、生成された第ｉ（１≦ｉ≦ｎ）番目のｘ因子及びｙ因子を左辺と右辺に振り分けて、左辺に振り分けられたｎ個のｘ因子及びｙ因子の積と、右辺に振り分けられたｎ個のｘ因子及びｙ因子の積とを等号で結ぶことにより得られる等式を生成すると、この生成された等式を展開することにより、公開鍵である、３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）の多項式を生成する。
【０１９４】
このように、上記実施形態にかかる公開鍵暗号に基づくデジタル署名システムは、頑健（robust）で、安全性・信頼性の高いデジタル署名を生成することができ、しかも少ない計算量で実現可能である。
【符号の説明】
【０１９５】
１…制御部、２…素数生成部、３…２変数多項式生成部、４…２変数多項式演算部、５…セクション生成部、６…３次元多様体生成部、７…鍵出力部、１１…平文入力部、１２…ハッシュ値計算部、１３…ハッシュ値多項式生成部、１４…秘密鍵入力部、１５…署名生成部、１６…セクション選択部、１７…署名出力部、２１…平文入力部、２２…ハッシュ値計算部、２３…ハッシュ値多項式生成部、２４…公開鍵入力部、２５…署名入力部、２６…署名検証部、２７…代数曲面生成部、２８…判定結果出力部、８…４変数多項式演算部。
【技術分野】
【０００１】
本発明は、公開鍵暗号方式を利用したデジタル署名生成装置、デジタル署名検証装置、鍵生成装置に関する。
【背景技術】
【０００２】
電子メールを始めとする多くの情報がネットワークを行き交うことにより、人々がコミュニケーションを行なうネットワーク社会において、暗号技術は情報の機密性や真正性を守る手段として広く活用されている。
【０００３】
暗号技術は大きく共通鍵暗号技術と公開鍵暗号技術に分けることができ、共通鍵暗号はデータの攪拌アルゴリズムに基づいた暗号方式で、高速に暗号化／復号ができる一方で、予め共通の鍵を持った２者間でしか秘密通信や認証通信ができない。公開鍵暗号は数学的なアルゴリズムに基づいた暗号方式で、共通鍵暗号ほど暗号化／復号が高速でないが、事前の鍵共有を必要とせず、通信の際は送信相手が公開している公開鍵を利用して秘密通信を実現し、送信者の秘密鍵を利用してデジタル署名を施すことで（成りすましを防ぐ）認証通信が可能となるという特徴がある。
【０００４】
このため、共通鍵暗号に基づくデジタル署名は秘密鍵を共有できる環境にある相手間や機器間で、高速性が求められている場合か、署名生成装置か署名検証装置のどちらか一方の能力が低い場合の認証手段として用いられている。また、公開鍵暗号に基づくデジタル署名は、インターネットに開設されているネットショッピング、銀行や証券会社のオンラインサイトなど秘密鍵が共有できない環境にある場合や、秘密鍵が共有できる環境にある場合でも、署名生成装置か署名検証装置のどちらの計算能力も高い場合に用いられている。
【０００５】
代表的な公開鍵暗号には、ＲＳＡ暗号と楕円曲線暗号があり、それぞれに基づくデジタル署名方式が提案されている。ＲＳＡ暗号は素因数分解問題の困難性が安全性の根拠となっており、署名生成演算及び署名検証演算として冪乗剰余演算が用いられている。楕円曲線暗号は楕円曲線上の離散対数問題の困難性が安全性の根拠となっており、署名生成演算並びに署名検証演算として楕円曲線上の点演算が用いられている。これらの公開鍵暗号は特定の鍵（公開鍵）に関する解読法（署名偽造法）は提案されているものの、一般的な解読法（署名偽造法）は知られていないため、安全性に関する重大な問題は、後に述べる量子計算機による解読法を除き、現在までのところ見つかっていない。
【０００６】
この他の公開鍵暗号に基づくデジタル署名には、体の拡大理論を利用して構成され連立方程式の求解問題に安全性の根拠をおいた多次多変数暗号に基づくＳＦＬＡＳＨと呼ばれる方式がある。しかし、多次多変数暗号には有力な攻撃方法が知られており、その解読法を避けるために必要な鍵サイズを大きくしなくてはならず、実用性が問題視されはじめている。
【０００７】
一方で、現在デジタル署名に広く利用されているＲＳＡ暗号と楕円曲線暗号であっても、量子計算機が出現すれば解読される危険に晒されている。量子計算機とは量子力学で知られているエンタングルメントという物理現象を利用して、（現在の計算機とは違った原理に基づいて）超並列計算を行わせることができる計算機であり、現在までのところ実験レベルでしか動作が確認されていない仮想の計算機であるが、実現に向けた研究開発が進められている。この量子計算機を用いて１９９４年にＳｈｏｒは素因数分解や離散対数問題を効率的に解くアルゴリズムが構成できることを示した（非特許文献１参照）。
【０００８】
即ち、量子計算機が実現すれば素因数分解に基づくＲＳＡ暗号や、（楕円曲線上の）離散対数問題に基づく楕円曲線暗号は解読できることになる。
【０００９】
このような状況の下、量子計算機が実現されてもなお安全な公開鍵暗号に基づくデジタル署名の研究が近年行われるようになってきた。現時点で実現可能で公開鍵暗号で量子計算機でも解読が難しいとされている方式には多次多変数暗号に基づくＳＦＬＡＳＨと呼ばれる方式があるが、多次多変数暗号は前記の通り、現状の計算機に対して安全とするために必要となる鍵サイズが膨大となっており、実用化が危ぶまれている。
【００１０】
更に、公開鍵暗号は共通鍵暗号と比較して、回路規模が大きく、処理時間も掛かるため、モバイル端末などの小電力環境では実現できないか実現しても処理時間がかかるという問題があった。このため、小電力環境でも実現できる公開鍵暗号が求められている。
【００１１】
一般に公開鍵暗号に基づくデジタル署名は（素因数分解問題や離散対数問題などの）計算困難な問題を見出し、（秘密鍵を知らずに）平文と呼ばれるメッセージにデジタル署名を生成しようとすることが当該計算困難な問題を解くことと計算量的に同等になるように構成する。しかし、逆に計算困難な問題が見つかったとしても必ずしもその問題を安全性の根拠とするようにデジタル署名を構成できる訳ではない。なぜなら、計算が困難すぎる問題に安全性の根拠をおくと鍵を生成する問題も困難になり、構成が難しくなる。一方で問題を鍵生成が可能となる程度に容易とすると、デジタル署名の偽造も容易になってしまう。
【００１２】
従って、公開鍵暗号を構成するには計算困難な問題を見つけるとともに、鍵を生成できる程には容易だが、（生成した秘密鍵を知らずに）解読できる程には容易でないという絶妙なバランスを持つ問題に作り変えるという創造性が必要であり、そこが難しいために現在まで数えるほどの公開鍵暗号に基づくデジタル署名しか提案されてこなかった。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】P.W.Shor:“Algorithms for Quantum Computation : Discrete Log and Factoring”,Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science,1994.
【発明の概要】
【発明が解決しようとする課題】
【００１４】
このように、従来は、量子計算機が出現しても安全性が確保でき、現在の計算機でも安全に実現可能であるとともに、小電力環境での実現可能性がある公開鍵暗号に基づくデジタル署名システム（鍵を生成し、デジタル署名を生成し、検証を行うためのシステム）が存在しなかった。
【００１５】
そこで、本発明は、安全性・信頼性の高いデジタル署名を生成することができ、しかも少ない計算量で実現可能な公開鍵暗号に基づくデジタル署名システムを提供する。
【課題を解決するための手段】
【００１６】
本発明に係るデジタル署名生成装置は、有限体Fｑならびに署名生成用の秘密鍵として、ｘ座標、ｙ座標、パラメータｓ、及びパラメータｔで表される前記有限体Fｑ上定義された３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）内の曲面のうち、ｘ座標及びｙ座標がパラメータｓ及びｔの関数で表されたセクションＤ（ｕｘ（ｓ，ｔ），ｕｙ（ｓ，ｔ），ｓ，ｔ）を記憶する記憶手段を備え、メッセージｍのハッシュ値を計算し、前記ハッシュ値を前記有限体Fｑ上定義された１変数多項式ｈ（ｔ）に埋め込み、ハッシュ値多項式を生成し、前記記憶手段に記憶されたセクションのパラメータｓに前記ハッシュ値多項式を代入することで、ｘ座標及びｙ座標がパラメータｔの関数で表された前記セクション上の曲線であるデジタル署名Ｄｓ（Ｕｘ（ｔ），Ｕｙ（ｔ），ｔ）を生成する。
【００１７】
本発明に係るデジタル署名検証装置は、有限体Fｑならびに公開鍵として、ｘ座標、ｙ座標、パラメータｓ、及びパラメータｔで表される前記有限体Fｑ上定義された３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）の多項式を記憶する記憶手段を備え、メッセージｍを入力するとともに、前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）内の曲面のうち、ｘ座標及びｙ座標がパラメータｓ及びｔの関数で表されたセクションＤ（ｕｘ（ｓ，ｔ），ｕｙ（ｓ，ｔ），ｓ，ｔ）を署名生成用の秘密鍵として用いて生成された、ｘ座標及びｙ座標がパラメータｔの関数で表された前記セクション上の曲線である、前記メッセージｍに対応したデジタル署名Ｄｓ：（Ｕｘ（ｔ），Ｕｙ（ｔ），ｔ）を入力する。前記メッセージｍのハッシュ値を計算し、前記ハッシュ値を、パラメータｔを有する前記有限体Fｑ上定義された１変数多項式ｈ（ｔ）に埋め込み、ハッシュ値多項式を生成し、前記記憶手段に記憶された前記多項式のパラメータｓに前記ハッシュ値多項式を代入して、前記ハッシュ値に対応した代数曲面Ｘ（ｘ，ｙ，ｔ）を計算し、前記代数曲面Ｘ（ｘ，ｙ，ｔ）の座標ｘ及び座標ｙに、前記デジタル署名のｘ座標を表す関数Ｕｘ（ｔ）と、ｙ座標を表す関数Ｕy（ｔ）をそれぞれ代入することにより、前記メッセージ及び前記デジタル署名の正当性を検証する。
【００１８】
本発明の鍵生成装置は、有限体Fｑならびに署名検証用の公開鍵として用いられる、ｘ座標、ｙ座標、パラメータｓ、及びパラメータｔで表される前記有限体Fｑ上定義された３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）と、署名生成用の秘密鍵として用いられる前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）内の曲面のうち、ｘ座標及びｙ座標がパラメータｓ及びｔの関数で表されたセクションを生成する鍵生成装置であって、前記有限体Fｑ上定義された、パラメータｓ、ｔに関する第１の２変数多項式λｘ（ｓ，ｔ）を生成し、前記第１の２変数多項式λｘ（ｓ，ｔ）で割り切れる、前記有限体Fｑ上定義された第２の２変数多項式λｙ（ｓ，ｔ）を生成し、前記有限体Fｑ上定義された、パラメータｓ，ｔに関する２つの２変数多項式ｕｘ（ｓ，ｔ）、ｖｘ（ｓ，ｔ）を、当該２つの２変数多項式の差分｛ｕｘ（ｓ，ｔ）−ｖｘ（ｓ，ｔ）｝が前記第１の２変数多項式λｘ（ｓ，ｔ）となるように生成し、前記有限体Fｑ上定義された、パラメータｓ，ｔに関する２つの２変数多項式ｕｙ（ｓ，ｔ）、ｖｙ（ｓ，ｔ）を、当該２つの２変数多項式の差分｛ｕｙ（ｓ，ｔ）−ｖｙ（ｓ，ｔ）｝が前記第２の２変数多項式λｙ（ｓ，ｔ）となるように生成し、２変数多項式ｕｘ（ｓ，ｔ）をｘ座標、２変数関数ｕｙ（ｓ，ｔ）をｙ座標とするセクションＤ１：（ｘ，ｙ，ｓ，ｔ）＝（ｕｘ（ｓ，ｔ），ｕｙ（ｓ，ｔ），ｓ，ｔ）と、２変数多項式ｖｘ（ｓ，ｔ）をｘ座標、２変数関数ｖｙ（ｓ，ｔ）をｙ座標とするセクションＤ２：（ｘ，ｙ，ｓ，ｔ）＝（ｖｘ（ｓ，ｔ），ｖｙ（ｓ，ｔ），ｓ，ｔ）を生成する。また、前記セクションＤ１及び前記セクションＤ２を含む前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）の多項式を生成する。
【００１９】
本発明の鍵生成装置は、有限体Fｑならびに、ｘ座標、ｙ座標、パラメータｓ、及びパラメータｔで表された、署名検証用の公開鍵として用いられる前記有限体Fｑ上定義された３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）と、前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）内の曲面のうち、ｘ座標及びｙ座標がパラメータｓ及びｔの関数で表された、署名生成用の秘密鍵として用いられるセクションを生成する鍵生成装置であって、パラメータｓ、ｔに関する第１番目から第ｎ（ｎは正の整数）番目までのｎ（ｎは正の整数）個の前記有限体Fｑ上定義された２変数多項式ｕｘ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）と、パラメータｓ、ｔに関する第１番目から第ｎ番目までのｎ個の前記有限体Fｑ上定義された２変数多項式ｕｙ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）を生成し、第ｉ（１≦ｉ≦ｎ）番目の２変数多項式ｕｘ，ｉ（ｓ，ｔ）及びｕｙ，ｉ（ｓ，ｔ）をそれぞれｘ座標、ｙ座標とする第ｉ番目のセクションＤｉ：（ｘ，ｙ，ｓ，ｔ）＝（ｕｘ，ｉ（ｓ，ｔ）、ｕｙ，ｉ（ｓ，ｔ），ｓ，ｔ）（１≦ｉ≦ｎ）を生成することにより、第１番目から第ｎ番目までのｎ個のセクションＤｉ（１≦ｉ≦ｎ）を求め、第ｉ（１≦ｉ≦ｎ）番目の２変数多項式ｕｘ，ｉ（ｓ，ｔ）及びｕｙ，ｉ（ｓ，ｔ）を用いて、第ｉ番目のｘ因子（ｘ−ｕｘ，ｉ（ｓ，ｔ））及びｙ因子（ｙ−ｕｙ，ｉ（ｓ，ｔ））を生成することにより、第１番目から第ｎ番目までのｘ因子及びｙ因子を求める、第ｉ（１≦ｉ≦ｎ）番目のｘ因子及びｙ因子を左辺と右辺に振り分けて、左辺に振り分けられたｎ個のｘ因子及びｙ因子の積と、右辺に振り分けられたｎ個のｘ因子及びｙ因子の積とを等号で結ぶことにより得られる等式を生成し、生成された等式を展開することにより、前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）の多項式を生成する。
【発明の効果】
【００２０】
安全性・信頼性の高い公開鍵暗号に基づくデジタル署名を生成することができ、しかも少ない計算量で実現可能となる。
【図面の簡単な説明】
【００２１】
【図１】３次元多様体のファイブレーションと、代数曲面について説明するための図。
【図２】鍵生成装置の構成例を示した図。
【図３】図２の鍵生成装置の処理動作を説明するためのフローチャート。
【図４】デジタル署名生成装置の構成例を示した図。
【図５】図４のデジタル署名生成装置の処理動作を説明するためのフローチャート。
【図６】デジタル署名検証装置の構成例を示した図。
【図７】図６のデジタル署名検証装置の処理動作を説明するためのフローチャート。
【図８】鍵生成装置の他の構成例を示した図。
【図９】図８の鍵生成装置の処理動作を説明するためのフローチャート。
【図１０】図２の鍵生成装置の他の構成例を示した図。
【図１１】図４のデジタル署名生成装置の他の構成例を示した図。
【図１２】図６のデジタル署名検証装置の他の構成例を示した図。
【図１３】８の鍵生成装置の他の構成例を示した図。
【発明を実施するための最良の形態】
【００２２】
以下、本発明の実施形態について図面を参照して説明する。
【００２３】
まず、本実施形態の概要を説明する。
【００２４】
（概要）
本実施形態では、３次元多様体は、体Ｋ上定義された連立（代数）方程式の解の集合のうち３次元の自由度を持ったものと定義される。例えば、体Ｋ上の連立方程式
【数１】
【００２５】
は変数６つに対し、それらを束縛する３つの方程式があるので３次元の自由度を持っており、３次元多様体となる。特に４変数のＫ上代数方程式
【数２】
【００２６】
の解の集合として定義される空間もＫ上の３次元多様体となる。尚、式（１）、式（２）に示した３次元多様体の定義式は、アフィン空間におけるものであって、射影空間におけるそれは（式（２）の場合）
【数３】
【００２７】
である。本実施形態では、３次元多様体を射影空間で扱うことはないので３次元多様体の定義式を式（１）若しくは式（２）としたが、射影空間で表現しても、本実施形態はそのまま成立する。一方、代数曲面は体Ｋ上定義された連立（代数）方程式の解の集合のうち２次元の自由度を持ったものである。よって、例えば
【数４】
【００２８】
と定義される。本実施形態においては式（２）のように１つの式で書ける３次元多様体のみを扱うので、以下では式（２）を３次元多様体の定義方程式のごとく扱う。
【００２９】
体とは加減乗除が自由にできる集合であって、実数、有理数、複素数がこれにあたる。たとえば、整数や行列など０以外に除算ができない元を含む集合は該当しない。体の中には有限体と呼ばれる有限個の元から構成される体がある。例えば素数ｐに対し、ｐを法とする剰余類Ｚ／ｐＺは体をなす。このような体は素体と呼ばれ、Ｆｐと表す。有限体にはこの他に素数の冪乗個の元を持つ体Ｆｑ（ｑ＝ｐｒ）があるが、本実施形態では簡単のため、主に素体Ｆｐのみを扱う。一般に素体Ｆｐのｐは素体Ｆｐの標数と呼ばれる。一方、一般の有限体でも、本実施形態は自明な変形を施すことによって同様に成立する。
【００３０】
公開鍵暗号ではメッセージをデジタルデータとして埋め込む必要から有限体上で構成することが多く、本実施形態においても同様に有限体（本実施形態では特に素体）Ｆｐ上定義された３次元多様体を扱う。
【００３１】
３次元多様体Ａ：ｆ（ｘ，ｙ，ｚ，ｕ）＝０内には、図１に示すように、通常、代数曲面が複数存在する。このような代数曲面は３次元多様体上の因子と呼ばれる。一般に３次元多様体の定義式が与えられた時に（非自明な）因子を求める問題は現代の数学においても未解決の難問であり、後述する多次多変数方程式によって解く方法を除けば一般的な解法は知られていない。
【００３２】
特に本実施形態で扱うような有限体で定義された３次元多様体においては有理数体などの無限体（無限個の元からなる体）で定義された３次元多様体と比較しても手掛かりが少なく、より難しい問題であることが知られている。更に、前記因子を求めるために出現する多次多変数方程式は、多次多変数暗号を解く場合に出現する多次多変数方程式と比べるとそのバラエティーが広く、多次多変数暗号に対して提案されている解法は一般には成立しない。
【００３３】
本実施形態では、この問題を３次元多様体上の求因子問題もしくは単に求因子問題と呼び、前記３次元多様体上の求因子問題に安全性の根拠をおく公開鍵暗号を構成する。
【００３４】
ｘ座標、ｙ座標、ｚ座標及びパラメータｕで表された３次元多様体Ａの定義式ｆ（ｘ，ｙ，ｚ，ｕ）＝０ において、変数ｚ、ｕをそれぞれパラメータｓ、ｔに変えて、
ｇｓ，ｔ（ｘ，ｙ）：＝ｆ（ｘ，ｙ，ｓ，ｔ）
とおく。これを体Ｋ上の２変数代数関数体Ｋ（ｓ，ｔ）の元を係数とする多項式とみなし、ｇｓ，ｔ（ｘ，ｙ）＝０ が、Ｋ（ｓ，ｔ）上の代数曲線を定義するとき、３次元多様体Ａはｓ，ｔをパラメータとするアフィン平面Ｐ２上のファイブレーションを持つといい、（ｘ，ｙ，ｓ，ｔ）を（ｓ，ｔ）に対応させることによって得られる写像Ａ→Ｐ２を、３次元多様体Ａのアフィン平面Ｐ２上のファイブレーションと呼ぶ。
【００３５】
そして、アフィン平面Ｐ２上の点（ｓ，ｔ）を１点（ｓ０，ｔ０）（ｓ０，ｔ０ は体Ｋの元）に固定したときに得られる曲線ｇｓ０，ｔ０（ｘ，ｙ）＝０ を点（ｓ０，ｔ０）上のファイバーと呼び、Ａｓ０，ｔ０ と表す。
【００３６】
アフィン平面Ｐ２上のファイブレーションを持つ３次元多様体にはセクションと呼ばれ、
（ｘ，ｙ，ｓ，ｔ）＝（ｕｘ（ｓ，ｔ），ｕｙ（ｓ，ｔ），ｓ，ｔ）
と表すことのできる、ｓ，ｔ でパラメタライズされた３次元多様体Ａ上の代数曲面が存在することが多い。セクションを持たないファイブレーションも存在するが、セクションを持つようなｆ（ｘ，ｙ，ｚ，ｕ）は容易に構成できる。
【００３７】
一方、上述のように、３次元多様体Ａの定義式ｆ（ｘ，ｙ，ｚ，ｕ）＝０ を２変数代数関数体Ｋ（ｓ，ｔ）の上で考えるのではなく、例えば１変数代数関数体Ｋ（ｔ）の上で考えることもできる。その場合は、
ｈｔ（ｘ，ｙ，ｓ）：＝ｆ（ｘ，ｙ，ｓ，ｔ）
とおくと、ｔの各値に対してｈｔ（ｘ，ｙ，ｓ）＝０ は、１変数代数関数体Ｋ（ｔ）上の代数曲面を定義する。このとき、Ａはｔをパラメータとするアフィン直線Ｐ１ 上のファイブレーションを持つといい、（ｘ，ｙ，ｓ，ｔ）を（ｔ）に対応させることによって得られる写像Ａ→Ｐ１ を３次元多様体Ａのアフィン直線Ｐ１上のファイブレーションと呼ぶ。
【００３８】
そして、アフィン直線Ｐ１ 上の点ｔを１点ｔ０に固定したときに得られる曲面
ｈｔ０（ｘ，ｙ，ｓ）＝０
を点ｔ０ 上のファイバーと呼び、Ａｔ０ と表す。
【００３９】
アフィン直線Ｐ１ 上のファイブレーションを持つ３次元多様体におけるセクションとは、
（ｘ，ｙ，ｓ，ｔ）＝（ｕｘ（ｔ），ｕｙ（ｔ），ｕｓ（ｔ），ｔ）
と表すことができ、ｔでパラメタライズされた、３次元多様体Ａ上の代数曲線のことである。
【００４０】
セクションは、３次元多様体の因子である。一般に３次元多様体のファイブレーションが与えられたとき、それに対応するファイバーは（ｓやｔに体の元を代入することにより）直ちに求まるが、対応するセクションを求めることは極めて難しい。
【００４１】
本実施形態で述べるデジタル署名は、３次元多様体上の求因子問題のうち、特に３次元多様体Ａのファイブレーションが与えられたとき、セクションを求める問題に安全性の根拠をおいたデジタル署名である。
【００４２】
尚、本実施形態においては、主としてアフィン平面Ｐ２ 上のファイブレーションを扱うので、簡単のためアフィン平面Ｐ２ 上のファイブレーションであることが明らかな場合は、単にファイブレーションと呼ぶ。またこの場合、ファイブレーションを持つ３次元多様体の定義式ｆ（ｘ，ｙ，ｓ，ｔ）＝０を単にファイブレーションと呼ぶことがある。
【００４３】
ファイブレーションからセクションを求めるには、現代の数学においても、セクション（ｕｘ（ｓ，ｔ），ｕｙ（ｓ，ｔ），ｓ，ｔ）を
【数５】
【００４４】
（ここでｄｅｇｓｕｘ（ｓ，ｔ）はｕｘ（ｓ，ｔ）において、ｓのみを変数としたときの次数である。）と仮定した上で、
【数６】
【００４５】
とおき、これをＡ（ｘ，ｙ，ｓ，ｔ）＝０に代入して、
【数７】
【００４６】
とし、この左辺を展開してｓｉｔｊの係数を
α０，…，αｒｓｘｒｔｘ−１，β０，…，βｒｓｙｒｔｙ−１の関数
ｃｉ，ｊ（α０，…，αｒｓｘｒｔｘ−１，β０，…，βｒｓｙｒｔｙ−１）
で表現し、連立方程式系
【数８】
【００４７】
を立てて、これを解くことによって求める方法しか知られていない。
【００４８】
即ち、本発明の公開鍵暗号も従来技術で述べた多次多変数暗号と同様に連立方程式の求解問題に帰着すると言える。しかし、多次多変数暗号が（現代の数学ではかなり解明されている）有限体の拡大理論に依存した非常に限られた範囲の多次多変数方程式の求解問題に帰着しているのに対し、３次元多様体暗号は数学上の未解決問題である求因子問題に依存しているため、問題の困難さのレベルは大きく異なる。
【００４９】
以下では３次元多様体上の求因子問題に基づいたデジタル署名の具体的な構成を説明する。尚、以下では全てＦｐ上定義された３次元多様体を考える。このため、全ての演算はＦｐ上で行う。
【００５０】
（第１の実施形態）
本実施形態に係るデジタル署名で用いられる公開鍵は、
Ｆｐ上の３次元多様体Ｘのファイブレーション：Ａ（ｘ，ｙ，ｓ，ｔ）＝０である。
【００５１】
秘密鍵は、Ｆｐ上の３次元多様体Ａのｎ個のセクション
Ｄｉ：（ｘ，ｙ，ｓ，ｔ）＝（ｕｘ，ｉ（ｓ，ｔ），ｕｙ，ｉ（ｓ，ｔ），ｓ，ｔ）である。
【００５２】
これらは後述する鍵生成方法で容易に求めることができる。
【００５３】
（１）署名生成処理
次に、署名生成処理の概要を述べる。署名生成処理ではまず署名生成したいメッセージ（以下では平文と呼ぶ）を整数ｍに変換する。変換の方法はメッセージをＪＩＳコードなどのコード体系を利用してコード化し、それを整数に読み換える方法が一般的である。
【００５４】
次に、変換された整数ｍをハッシュ関数ｈ（ｘ）にかけてハッシュ値ｈ（ｍ）を計算する。ここでハッシュ値ｈ（ｍ）は一般に１２０ビットないし１６０ビットあるので、例えば、ｈ（ｍ）＝ｈ０‖ｈ１‖…‖ｈｒ−１
と、複数のブロックｈ０、ｈ１、…ｈｒ−１に分割し、これらを変数ｔに関する１変数多項式
ｈ（ｔ）＝ｈｒ−１ｔｒ−１＋…＋ｈ１ｔ＋ｈ０
の係数に埋め込む（ハッシュ値埋め込み処理）。ハッシュ値の埋め込まれた１変数多項式をハッシュ値多項式ｈ（ｔ）と呼ぶ。ここでｈ（ｔ）をＦｐ上の多項式とするために、
各ｈｉ（０≦ｉ≦ｒ−１）はＦｐの元となるように取る必要がある。即ち、上記ハッシュ値は、ｐのビット長に基づいて、
０≦ｈｉ≦ｐ−１
となるようにハッシュ値を分割する。
【００５５】
次に、秘密鍵であるｎ個のセクションＤｉのなかからランダムに１つ選択する。選択されたセクション
Ｄｉ：（ｗｘ（ｓ，ｔ），ｗｙ（ｓ，ｔ），ｓ，ｔ）
に対して、その変数ｓに上記ハッシュ値多項式ｈ（ｔ）を代入する。即ち、
（ｗｘ（ｈ（ｔ），ｔ），ｗｙ（ｈ（ｔ），ｔ），ｈ（ｔ），ｔ）
これを整理して、
Ｄｓ：（ｘ，ｙ，ｔ）＝（Ｗｘ（ｔ），Ｗｙ（ｔ），ｔ） …（３）
とし、これをメッセージｍに対するデジタル署名Ｄｓとしてメッセージｍと共に受信者に送信する。
【００５６】
以上の説明からもわかるように、式（３）に示すデジタル署名Ｄｓは、秘密鍵として用いたセクションＤｉ上の曲線である。
【００５７】
ここで、安全性の観点からＷｘ（ｔ）、Ｗｙ（ｔ）の次数が選択したセクションによらず一定であることが望ましい。これはセクションに現れる多項式ｕｘ，ｉ（ｓ，ｔ）に対して、
【数９】
【００５８】
とするとき、全てのｉに対してｕｘ，ｉ（ｓ，ｔ）がｓｈｘｔｋｘ の項を含むようにすることで解決できる。なぜならば、このようにすることによって、ハッシュ値多項式ｈ（ｔ）をどのセクションのｓに代入しても、得られる多項式Ｗｘ（ｔ）の最大次数の項はｈ（ｔ）をｓｈｘｔｋｘ の項に代入した多項式から生じるためである。
【００５９】
ｕｙ，ｉ（ｓ，ｔ）に関しても同様の手段でＷｙ（ｔ）の次数をｉによらず一定に保つことができる。このような鍵（セクションとそれに対応する３次元多様体）を生成する方法は後に示す。
【００６０】
（２）署名検証処理
デジタル署名Ｄｓ（ｘ，ｙ，ｔ）を受け取った受信者は所有する有限体Fｐ上定義された公開鍵Ａ（ｘ，ｙ，ｓ，ｔ）を利用して次のように署名検証処理を行う。
【００６１】
まず、前述の署名生成処理と同様に、メッセージ（以下では平文と呼ぶ）を整数ｍに変換する。変換の方法は署名生成処理と同じである。次に変換された整数ｍを上述の署名生成処理と同じハッシュ関数ｈ（ｘ）にかけてハッシュ値ｈ（ｍ）を計算する。更に前述の署名生成処理と同様に、ハッシュ値を、ｈ（ｍ）＝ｈ０‖ｈ１‖…‖ｈｒ−１
と、複数のブロックｈ０、ｈ１、…ｈｒ−１に分割し、これらを変数ｔに関する有限体Fｐ上定義された１変数多項式
ｈ（ｔ）＝ｈｒ−１ｔｒ−１＋…＋ｈ１ｔ＋ｈ０
の係数に埋め込み、ハッシュ値の埋め込まれたハッシュ値多項式ｈ（ｔ）を生成する。
【００６２】
次に、公開鍵である３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）の変数ｓに、生成したハッシュ値多項式ｈ（ｔ）を代入して、代数曲面
Ｘ（ｘ，ｙ，ｔ）＝Ａ（ｘ，ｙ，ｈ（ｔ），ｔ）
を生成する。このＸ（ｘ，ｙ，ｔ）もファイブレーションを持つ代数曲面である。
【００６３】
次に、得られた代数曲面Ｘに、（受信側が受け取った）式（３）で表現されたデジタル署名を代入する。このとき値が「０」になればデジタル署名が正しく、「０」でなければデジタル署名が正しくないことを意味する。
【００６４】
なぜならば、前述のデジタル署名生成処理においては、秘密鍵として与えられたセクションのうちランダムに選択されたセクションＤｉに対して、ｓ＝ｈ（ｔ）を代入していた。一方、これは前述のデジタル署名検証処理で行った３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）にｓ＝ｈ（ｔ）を代入して得られた代数曲面Ｘ（ｘ，ｙ，ｔ）のセクションに対応している。従って、前述のデジタル署名検証処理のような代入操作を行うと、値が「０」となる。
【００６５】
更に、ｓ＝ｈ（ｔ）を代入して得られる代数曲面もそのセクションを求めることは３次元多様体と同様に難しく多次多変数方程式の求解問題に帰着することが知られている。このため、後述する安全性署名の項目でも詳しく述べるように、３次元多様体のセクションを知らない第三者がメッセージに対応した代数曲面のセクションを提示することは当該代数曲面のセクションを求める問題に帰着する。このため（計算量の観点で）不可能であるといえる。このことが本発明のデジタル署名が安全であることの根拠である。
【００６６】
（３）鍵生成方法
鍵生成方法を説明する。本実施形態の鍵生成は、セクションＤ１、Ｄ２をランダムに選び、それに対応したファイブレーションを計算することによって行う。但し、生成された３次元多様体が２つのセクションを同時に持つようにするために以下のような工夫が必要となる。
【００６７】
ここでは簡単のため３次元多様体のうち、次のファイブレーションを持つ３次元多様体を例にとって鍵生成方法を示す。
【数１０】
【００６８】
ここで、ａ（ｓ，ｔ），ｂ（ｓ，ｔ）は２変数多項式である。まず、素体の標数ｐを決める。このときｐは小さくても安全性に問題は生じない。さて、セクションＤ１，Ｄ２を
【数１１】
【００６９】
とおいて、３次元多様体Ａに代入し、
【数１２】
【００７０】
を得る。これらを辺々引くとｂ（ｓ，ｔ）が消え、
【数１３】
【００７１】
となる。ａ（ｓ，ｔ）を２変数多項式とするには、たとえば
【数１４】
【００７２】
であれば十分である。このことを利用して以下に示すアルゴリズムで鍵生成を行うことができる。
【００７３】
ここで、ｋ１（ｓ，ｔ）｜ｋ２（ｓ，ｔ）は、多項式ｋ１（ｓ，ｔ）が、
多項式ｋ２（ｓ，ｔ）を割り切ることを意味している。
【００７４】
まず、λｘ（ｓ，ｔ）｜λｙ（ｓ，ｔ）となる２つの多項式をランダムに選択する。具体的にこのような多項式の組を求めるには、例えばλｘ（ｓ，ｔ）をランダムに与えて、同じくランダムな多項式ｃ（ｓ，ｔ）によってλｙ（ｓ，ｔ）＝ｃ（ｓ，ｔ）λｘ（ｓ，ｔ）を計算することによって、λｙ（ｓ，ｔ）を求めることで実現できる。
【００７５】
次に、多項式ｖｘ（ｓ，ｔ）をランダムに選択し、
【数１５】
【００７６】
によって、ｕｘ（ｓ，ｔ）を計算する。同様に多項式ｖｙ（ｓ，ｔ）をランダムに選択し、
【数１６】
【００７７】
によって、ｕｙ（ｓ，ｔ）を計算する。このようにして計算されたｕｘ（ｓ，ｔ）、ｖｘ（ｓ，ｔ）、ｕｙ（ｓ，ｔ）、ｖｙ（ｓ，ｔ）を利用して、
【数１７】
【００７８】
を計算することにより、多項式ａ（ｓ，ｔ）が計算できる。更にｂ（ｓ，ｔ）は、上述のａ（ｓ，ｔ）を利用して、
【数１８】
【００７９】
によって得られる。
【００８０】
前述の鍵生成方法は、上記以外の３次元多様体であっても、例えば
【数１９】
【００８１】
という形の定義式を仮定すれば同様に可能であり、上述の例のみに限定されない。
【００８２】
一方で、上述の鍵生成方式では３つ以上のセクションを持つ代数曲面を生成することができない。また、上述の安全性上望ましい条件として挙げたデジタル署名
Ｄｓ：（ｘ，ｙ，ｔ）＝（Ｗｘ（ｔ），Ｗｙ（ｔ），ｔ）
に表われるＷｘ（ｔ）、Ｗｙ（ｔ）の次数を、選択したセクションによらず一定にするような公開鍵を生成することが困難である。これら両方を解決する鍵生成方法として、以下のような第２の鍵生成方法が考えられる。
【００８３】
まず、ｕｘ，ｉ（ｓ，ｔ）の最大次数の項ｓｈｘｔｋｘを決め、ｓの最大次数がｈｘ、ｔの最大次数がｋｘとなるように、ｎ個の２変数多項式ｕｘ，ｉ（ｓ，ｔ）を定める。また同様にしてｕｙ，ｉ（ｓ，ｔ）の最大次数の項ｓｈｙｔｋｙを決め、ｓの最大次数がｈｙ、ｔの最大次数がｋｙとなるように、ｎ個の２変数多項式ｕｙ，ｉ（ｓ，ｔ）を定める。
【００８４】
次に、これらの多項式から因子（ｘ−ｕｘ，ｉ（ｓ，ｔ））、（ｙ−ｕｙ，ｉ（ｓ，ｔ））を生成し、各ｉ（１≦ｉ≦ｎ）について、ｉが同じ値の２つの因子（ｘ−ｕｘ，ｉ（ｓ，ｔ））及び（ｙ−ｕｙ，ｉ（ｓ，ｔ））を、左辺と右辺のそれぞれに振り分ける。そして、左辺に振り分けられたｎ個の因子の積と、右辺に振り分けられたｎ個の因子の積とを等号で結ぶことにより、次式（６）に示すような方程式を得る。
【数２０】
【００８５】
式（６）は、前記条件を満たす方程式となる。ここで、例えば、
Ｄｉ：（ｕｘ，ｉ（ｓ，ｔ），ｕｙ，ｉ（ｓ，ｔ），ｓ，ｔ）がセクションとなる。
【００８６】
更に、これらのセクションは、その作り方からｈ（ｔ）を代入しても、同じ次数のデジタル署名Ｄｓ：（Ｗｘ（ｔ），Ｗｙ（ｔ），ｔ）が生成される。実際には式（６）のままであるとセクションがすぐ分かってしまうので、展開することによって公開鍵である３次元多様体を得る。
【００８７】
一方で、式（６）ではｘの因子が右辺に、ｙの因子が左辺に分かれているため因数分解によってセクションを求めることが容易となる場合がある。そこで、例えば
【数２１】
【００８８】
などのように、ｘの因子とｙの因子をランダムに両辺に分けて公開鍵暗号である３次元多様体を生成することが望ましい。このように公開鍵と秘密鍵を生成することによって一般にｎ個以上のセクションを持つ安全性の高い３次元多様体を生成することができる。尚、前記安全性の観点を除けば、ｕｘ，ｉ（ｓ，ｔ），ｕｙ，ｉ（ｓ，ｔ）の作り方に自由度を持たせることができる。
【００８９】
（４）安全性の証明
上述のデジタル署名の安全性証明に関して説明する。デジタル署名の安全性は、メッセージ（平文）とデジタル署名のペアを作成する問題が多項式時間で解ければ３次元多様体のセクションを求める問題を多項式時間で求めることができ、逆に３次元多様体のセクションを求める問題を多項式時間で求めることができれば、メッセージ（平文）とデジタル署名のペアを作成することが多項式時間で可能なことを証明することによって証明することができる。即ち、上記の事実を理論的に証明することによって、メッセージ（平文）とデジタル署名のペアを作成可能なこと（存在的偽造可能であること）と、３次元多様体のセクションを求める問題が解けることが同値であることが示せるので、安全性の根拠としている３次元多様体のセクションを求める問題が困難であれば、デジタル署名が存在的偽造不可能であることが示されるからである。以上の方針に従った安全性証明を次に示す。
【００９０】
ここで、２次元セクションＤをＤ＝（ｄｘ（ｓ，ｔ），ｄｙ（ｓ，ｔ），ｓ，ｔ）と書いたとき、２次元セクションの次数を、ｄｘ（ｓ，ｔ），ｄｙ（ｓ，ｔ）の次数の最大値、
ｍａｘ｛ｄｅｇ（ｄｘ（ｓ，ｔ）），ｄｅｇ（ｄｙ（ｓ，ｔ））｝とする。
【００９１】
［定理１］ｎ次のセクションを持つ有限体Fｐ上定義された３次元多様体の求セクション問題が計算困難であることと、本発明のデジタル署名は存在的偽造不可能の意味で安全であることは同値である。
【００９２】
［証明１］本実施形態のデジタル署名による平文と署名の具体的なペアを多項式時間内に計算できるアルゴリズムαが存在したとする。このとき、このアルゴリズムαを利用して３次元多様体の２次元セクションを求める多項式時間アルゴリズムが存在することを示す。
【００９３】
まず、２次元セクションを求めたい３次元多様体をＡ（ｘ，ｙ，ｓ，ｔ）とする。次にＡ（ｘ，ｙ，ｓ，ｔ）を公開鍵とするデジタル署名方式を考え、アルゴリズムαを利用して多項式個の平文と署名のペアを生成する。ここで、平文ｍｉに対するハッシュ値多項式をｈｉ（ｔ）とし、その署名を
【数２２】
【００９４】
とする。ここで、ｆｉ（ｓ，ｔ），ｇｉ（ｓ，ｔ）は３次元多様体Ａのセクションのｘ，ｙ座標に対応するもので、高々有限個しか存在しない。従って、一定数以上の署名を集めれば、ｆｉ（ｓ，ｔ），ｇｉ（ｓ，ｔ）は全て異なるものではなく、その幾つかは同一となる。これらのうちどれが同じものであるかは以下の方法で判定できる。
【００９５】
３次元多様体Ｂ（ｘ，ｙ，ｓ，ｔ）（＝Ａ（ｘ，ｙ，ｔ，ｓ））を考える。このＢ（ｘ，ｙ，ｓ，ｔ）は３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）のｓとｔを交換したものであり、セクションの次数の定義からｎ次のセクションを持っている。そこで、アルゴリズムαを利用して、１つの平文と署名のペアを生成する。その際、特にハッシュ値多項式ｈｉ（ｓ）が定数ｈｉ（ｓ）＝ｈ０となるものを選び、生成された署名を
【数２３】
【００９６】
とすると、
【数２４】
【００９７】
は、ｓでパラメタライズされたＡ（ｘ，ｙ，ｓ，ｔ）の１つの１次元サイクルを与える。ここでサイクルとは部分多様体のことを意味し、特に１次元サイクルとは１次元の部分多様体である。このサイクルＤを利用して、１次元サイクル
【数２５】
【００９８】
のうち、Ｄと同じＸのセクションの上に存在するものを以下の多項式アルゴリズムで見出す。
【００９９】
まず、（ｓ，ｔ）＝（ｈｉ（ｈ０），ｈ０）とおくと、Ｄ上の点（ζ（ｈｉ（ｈ０），ｈ０），η（ｈｉ（ｈ０），ｈ０），ｈｉ（ｈ０），ｈ０）とＤｓ（ｉ）上の点（ｆｉ（ｈｉ（ｈ０），ｈ０），ｇｉ（ｈｉ（ｈ０），ｈ０），ｈｉ（ｈ０），ｈ０）が定まる。そして、Ｘのセクションが（ｓ，ｔ）を座標とする平面に同型であることに注意すると、
【数２６】
【０１００】
であればＤｓ（ｉ）とＤは同一のセクションの上に存在する。等しくなければＤｓ（ｉ）とＤとは同一のセクションの上にはない。ここで同じセクションに含まれる１次元サイクル群を、
【数２７】
【０１０１】
とする。さて、ここで３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）のセクション（ｗｘ（ｓ，ｔ），ｗｙ（ｓ，ｔ），ｓ，ｔ）を
【数２８】
【０１０２】
と書くと、式（８）の１次元セクションを代入することによって、
【数２９】
【０１０３】
を得る。この両辺をｔの冪毎にその係数を比較することによって、ａｉｊの連立１次方程式が得られる。連立１次方程式は多項式時間の解法が存在するので、多項式時間で全ての
ａｉｊが求まる。同様にｂｉｊも多項式時間で求まるので、３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）のセクションが多項式時間で求まることが示せた。
【０１０４】
逆に、３次元多様体の２次元セクションを求める多項式時間アルゴリズムβが存在したとする。このとき、このアルゴリズムβを利用して、本実施形態のデジタル署名による平文と署名の具体的なペアを多項式時間内に計算できることを示す。
【０１０５】
本実施形態のデジタル署名の公開鍵である３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）が与えられたとき、アルゴリズムβを利用して、その２次元セクション
Ｄ：（ｗｘ（ｓ，ｔ），ｗｙ（ｓ，ｔ），ｓ，ｔ）
を求める。ここで平文ｍを適当に決め、そのハッシュ値多項式をｈ（ｔ）とした時、
ｓ＝ｈ（ｔ）と置くことにより、署名
Ｄｓ：（ｗｘ（ｈ（ｔ），ｔ），ｗｙ（ｈ（ｔ），ｔ），ｔ）
を得る。これにより平文と署名の具体的なペアを多項式時間内に計算可能である。
【０１０６】
以上により、定理が証明された。
【０１０７】
（５）バリエーション
本実施形態におけるバリエーションを述べる。第１のバリエーションはハッシュ値多項式をハッシュ値自体に置き換えるバリエーションである。本実施形態におけるデジタル署名生成処理においては、平文ｍからハッシュ値ｈ（ｍ）を計算し、ハッシュ値ｈ（ｍ）をハッシュ値多項式ｈ（ｔ）に展開して、ランダムに選択したセクションＤｉにｓ＝ｈ（ｔ）と代入していた。
【０１０８】
しかし、ハッシュ値をハッシュ値多項式に埋め込まないような実施形態も成立する。即ち、セクションＤｉに、ハッシュ値ｈ（ｍ）そのものを、ｓ＝ｈ（ｍ）として代入することにより、デジタル署名
Ｄｓ：（ｗｘ（ｈ（ｍ），ｔ），ｗｙ（ｈ（ｍ），ｔ），ｔ）
が生成できる。この場合は、デジタル署名検証処理においても同様に公開鍵である３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）への代入をｓ＝ｈ（ｍ）によって行うことにより、同様の手段で署名検証が可能となる。
【０１０９】
実際に、このバリエーションが成り立つことは、本実施形態におけるハッシュ値多項式ｈ（ｔ）を定数項だけからなる多項式と考えれば理解することができる。即ち、本バリエーションは本実施形態の特別な場合と言うことができる。本バリエーションを利用することによってデジタル署名生成処理、デジタル署名検証処理における多項式演算を軽減でき、計算メモリ量や計算処理時間を削減することが可能となる。しかし、その反面でハッシュ値は最小でも１２０ビットであるため定義体であるＦｐのｐのサイズを１２０ビット程度に大きくしなければならず、多倍長演算が必要となるという弱点も持ち合わせており、
適用有効範囲は限定される。
【０１１０】
第２のバリエーションは、本実施形態のデジタル署名生成装置、デジタル署名検証装置においてハッシュ値多項式を代入する変数の変更に関するバリエーションである。本実施形態のデジタル署名生成装置、デジタル署名検証装置においては、ハッシュ値多項式としてｈ（ｔ）という変数ｔによる１変数多項式を取り、秘密鍵であるセクション若しくは公開鍵である３次元多様体の変数ｓに代入していたが、これを以下のように変更しても本発明は安全性も含めて同様に成立する。
【０１１１】
即ちハッシュ値多項式として、ｈ（ｓ）という変数ｓによる１変数多項式を取り、秘密鍵であるセクション若しくは公開鍵である３次元多様体の変数ｔに代入する。変数ｓ，ｔは共にパラメータなので本バリエーションによってその効果は変わらない。
【０１１２】
（６）構成
次に、本実施形態のデジタル署名方式に係る鍵生成装置、デジタル署名生成装置、デジタル署名検証装置の構成例と、これらの処理動作について説明する。
【０１１３】
図２は、鍵生成装置の構成例を示したもので、図３は、図２の鍵生成装置の処理動作を説明するためのフローチャートである。以下、図３に示すフローチャートを参照して、図２の鍵生成装置の構成及び処理動作について説明する。尚、理解の助けとして具体的な数値や式を示すが、これはあくまでも理解を助けるための例であって、実際に使われる十分な安全性を持つデジタル署名とは（特に多項式の次数などの点で）必ずしも一致していない。
【０１１４】
なお、ここでは、前述した、ｙ２＝ｘ３＋ａ（ｓ，ｔ）ｘ＋ｂ（ｓ，ｔ）というファイブレーションをもつ３次元多様体を例にとり説明する。
【０１１５】
鍵生成処理開始の指令が外部装置等から制御部１に伝えら、鍵生成装置は鍵生成処理を開始する（ステップＳ１）。当該指令が制御部１に伝わると、制御部１は、素数生成部２に素数の生成を要請する。素数生成はランダムに素数を発生させても良いが、ここでは大きな素数を使う必要はないので、高々６ビット程度の素数からランダム若しくは（出力順を予め決めておくなどの手段で）恣意的に選択するか、当該鍵生成装置で予め定まっている素数を利用してもよい。ここでは素数ｐ＝１７が生成されたとする（ステップＳ２）。
【０１１６】
制御部１は、セクション生成部５に、素数ｐを出力し、セクション生成部５では、セクションの生成を開始する。セクション生成部５は、まず、素数ｐを２変数多項式生成部３に出力し、２変数多項式生成部３は、２変数多項式λｘ（ｓ，ｔ）（＝−ｓ（ｔ−１））を生成する（ステップＳ３）。２変数多項式生成部３では、予め定められた一定範囲内で次数をランダムに選択し、その次数を持つ２変数多項式の係数を有限体Ｆｐの元として０からｐ−１までの範囲でそれぞれ生成する。
【０１１７】
２変数多項式生成部３は、λｘ（ｓ，ｔ）を生成すると、これを制御部１へ出力する。制御部１は、λｘ（ｓ，ｔ）を得ると、上記同様に、ランダムな２変数多項式ｃ（ｓ，ｔ）の生成処理を行い、ｃ（ｓ，ｔ）（＝ｓ＋ｔ）を得る（ステップＳ４）。
【０１１８】
制御部１は、ｃ（ｓ，ｔ）とλｘ（ｓ，ｔ）を２変数多項式演算部４に出力する。
【０１１９】
２変数多項式演算部４では、λｙ（ｓ，ｔ）＝ｃ（ｓ，ｔ）λｘ（ｓ，ｔ）を計算し（ステップＳ５）、制御部１へλｙ（ｓ，ｔ）（＝−（ｓ＋ｔ）ｓ（ｔ−１））を出力する。
【０１２０】
λｙ（ｓ，ｔ）を受け取った制御部１では、次にλｘ（ｓ，ｔ）の生成と同様の方法で２変数多項式ｖｘ（ｓ，ｔ）（＝２ｓｔ）をランダムに生成し（ステップＳ６）、λｘ（ｓ，ｔ）（＝−ｓ（ｔ−１））とｖｘ（ｓ，ｔ）（＝２ｓｔ）を２変数多項式演算部４へ出力する。
【０１２１】
２変数多項式演算部４は、ｕｘ（ｓ，ｔ）（＝λｘ（ｓ，ｔ）＋ｖｘ（ｓ，ｔ）＝ｓ（ｔ＋１））を計算し、これを制御部１へ出力する（ステップＳ７）。
【０１２２】
制御部１は、ステップＳ６と同様に、ｖｙ（ｓ，ｔ）（＝２ｓｔ２＋ｓ＋ｓ２ｔ−ｓ２−ｓｔ）を生成し（ステップＳ８）、さらに、
ｕｙ（＝λｙ（ｓ，ｔ）＋ｖｙ（ｓ，ｔ）＝ｓ（ｔ２＋１））を計算する（ステップＳ９）。
【０１２３】
制御部１は、ｕｘ（ｓ，ｔ）、ｕｙ（ｓ、ｔ）、ｖｘ（ｓ，ｔ）、ｖｙ（ｓ，ｔ）を３次元多様体生成部６に出力する。
【０１２４】
３次元多様体生成部６は、２変数多項式演算部４を繰り返し使うことにより、式（４）に用いて、３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）：ｙ２＝ｘ３＋ａ（ｓ，ｔ）ｘ＋ｂ（ｓ，ｔ）のパラメータｓ、ｔに関する２変数多項式ａ（ｓ，ｔ）を計算する（ステップＳ１０）。
【０１２５】
この例では
【数３０】
【０１２６】
と求まる。さらに、式（５）を用いて、ａ（ｓ、ｔ）とｕｘ（ｓ，ｔ）、ｕｙ（ｓ，ｔ）、ｖｘ（ｓ，ｔ）、ｖｙ（ｓ，ｔ）から、２変数多項式演算部４を繰り返し使うことにより、パラメータｓ、ｔに関する２変数多項式ｂ（ｓ，ｔ）を計算する（ステップＳ１１）。
【０１２７】
この例では、
【数３１】
【０１２８】
を得る。
【０１２９】
３次元多様体生成部６は、得られたａ（ｓ，ｔ）、ｂ（ｓ，ｔ）を制御部１に出力する。
【０１３０】
制御部１は、３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）を表す多項式：ｙ２＝ｘ３＋ａ（ｓ，ｔ）ｘ＋ｂ（ｓ，ｔ）に、ステップＳ１０及びステップＳ１１で得られたａ（ｓ，ｔ）とｂ（ｓ，ｔ）を代入することで、次式（９）に示すような、公開鍵である３次元多様体ＡのファイブレーションＡ（ｘ，ｙ，ｓ，ｔ）の多項式を生成する。
【０１３１】
また、次式（１０）に示すように、２変数多項式ｕｘ（ｓ，ｔ）をｘ座標、２変数多項式ｕｙ（ｓ，ｔ）をｙ座標とするセクションＤ１：（ｘ，ｙ，ｓ，ｔ）と、２変数多項式ｖｘ（ｓ，ｔ）をｘ座標、２変数多項式ｖｙ（ｓ，ｔ）をｙ座標とするセクションＤ２：（ｘ，ｙ，ｓ，ｔ）を生成する（ステップＳ１２）。
【数３２】
【０１３２】
制御部１は、生成された公開鍵と秘密鍵を鍵出力部７に出力し、鍵出力部７は、公開鍵と秘密鍵を出力する。
【０１３３】
なお、図２に示す各機能（制御部１、素数生成部２、２変数多項式３、２変数多項式演算部４、セクション生成部５、３次元多様体生成部６、鍵出力部７など）は、図１０に示すように、各種プログラムなどを記憶する記憶部１０１、ＣＰＵなどの演算部１００、出力部１０２、入力部１０３、通信部１０４などをバスに接続してなるコンピュータに、記憶部１０１に記憶されている各プログラムを実行させることにより、実現することができる。
【０１３４】
図１０では、記憶部１０１には、制御部１、素数生成部２、２変数多項式生成部３、２変数多項式演算部４、セクション生成部５、３次元多様体生成部６、鍵出力部７のそれぞれの機能を実現すための鍵生成制御プログラム、素数生成プログラム、２変数多項式生成プログラム、２変数多項式演算プログラム、セクション生成プログラム、３次元多様体生成プログラム、鍵出力プログラムが記憶されている。
【０１３５】
図２の鍵出力部７から出力された秘密鍵や公開鍵は、例えば、通信部１０４を介して要求元へ送信されたり、後述するデジタル署名生成装置やデジタル署名検証装置へ渡される。
【０１３６】
図４は、デジタル署名生成装置の構成例を示したもので、図５は、図４のデジタル署名生成装置の処理動作を説明するためのフローチャートである。以下、図５に示すフローチャートを参照して、図４のデジタル署名生成装置の構成及び処理動作について説明する。
【０１３７】
図４のデジタル署名生成装置は、平文入力部１１から平文ｍを取得し、秘密鍵入力部１４から秘密鍵であるセクション群Ｄｉ（ｕｘ（ｓ，ｔ），ｕｙ（ｓ，ｙ），ｓ，ｔ）（０≦ｉ≦ｎ）を取得する。
【０１３８】
ここで、秘密鍵を前述の鍵生成処理で生成された
１．素体の標数ｐ＝１７
２．式（１０）に示した有限体Fｐ上定義された３次元多様体Ａの２つのセクションを利用する。尚、全ての演算は鍵生成処理で決定した有限体Ｆ１７で行う。
【０１３９】
まず、平文入力部１１から平文ｍが入力されることによって、デジタル署名生成処理が開始される（ステップＳ１０１）。入力された平文ｍは、ハッシュ値計算部１２に出力され、ＳＨＡ１やＭＤ５などのハッシュ関数を利用してハッシュ値ｈ（ｍ）が計算される。ここでは、簡単のため、ハッシュ値を「０ｘ１５１」とするが、本来は１２０ビット以上である必要がある。計算されたハッシュ値は、ハッシュ値多項式生成部１３に送られ、予め定められた複数のブロックに分割される。ここでは、ｐ＝１７であることから４ビット毎に分割し、各ブロックをハッシュ値多項式ｈ（ｔ）の係数に埋め込む（ステップＳ１０３）。その結果得られるハッシュ値多項式ｈ（ｔ）は ｈ（ｔ）＝ｔ２＋５ｔ＋１ となる。
【０１４０】
秘密鍵記憶部１８には、図２や後述の図８に示した構成の鍵生成装置で生成された秘密鍵である少なくとも１つのセクションを記憶する。
【０１４１】
秘密鍵入力部１４は、秘密鍵記憶部１８から秘密鍵であるセクション群を読み出して、署名生成部１５へ出力する（ステップＳ１０４）。秘密鍵記憶部１８には、複数のセクションが記憶されていることが望ましい。ここでは、式（１０）に示した２つのセクションＤ１、Ｄ２が秘密鍵記憶部１８に記憶されており、秘密鍵入力部１４は、この２つのセクションＤ１、Ｄ２を秘密鍵記憶部１８から読み出し、署名生成部１５へ出力する。これらセクション群は、署名生成部１５から、セクション選択部１６に出力される。セクション選択部１６は、入力されたセクション群のうちから１つのセクションをランダムに選択する（ステップＳ１０５）。ここではＤ１が選択されたとする。選択されたセクションＤ１は、署名生成部１５に出力される。なお、秘密鍵記憶部１８に秘密鍵が１つのみ記憶されている場合には、セクション選択部１６の上記処理は省略される。
【０１４２】
選択されたセクションＤ１を受信した署名生成部１５は、ハッシュ値多項式生成部１３から、ステップＳ１０３で生成されたハッシュ値多項式ｈ（ｔ）を取得して、選択されたセクションＤ１のｓ座標にｈ（ｔ）を代入して（ｓ＝ｈ（ｔ））、セクションＤｓを生成する（ステップＳ１０６）。
【０１４３】
ここでは、次式（１１）に示すようなセクションＤｓが生成される。
【数３３】
【０１４４】
このセクションＤｓは、デジタル署名として署名出力部１７から出力される（ステップＳ１０７）。
【０１４５】
前述の第１、第２のバリエーションは本実施形態において同様の処理で成立する。尚、第１のバリエーションを利用する場合は現状では（ハッシュ値の大きさを考慮して）ｐを１２０ビット以上とする必要がある。
【０１４６】
なお、図４に示す各機能（平文入力部１１、ハッシュ値計算部１２、ハッシュ値多項式生成部１３，秘密鍵入力部１４、署名生成部１５、セクション選択部１６，署名出力部１７など）は、図１１に示すように、各種プログラムなどを記憶する記憶部１０１、ＣＰＵなどの演算部１００、出力部１０２、入力部１０３、通信部１０４などをバスに接続してなるコンピュータに、記憶部１０１に記憶されている各プログラムを実行させることにより、実現することができる。
【０１４７】
図１１では、記憶部１０１には、平文入力部１１、ハッシュ値計算部１２、ハッシュ値多項式生成部１３，秘密鍵入力部１４、署名生成部１５、セクション選択部１６，署名出力部１７のそれぞれの機能を実現すための平文入力プログラム、ハッシュ値計算プログラム、ハッシュ値多項式生成プログラム、秘密鍵入力プログラム、署名生成プログラム、セクション選択プログラム，署名出力プログラムが記憶されている。また、記憶部１０１は、秘密鍵を記憶する秘密鍵記憶部１８としても機能する。
【０１４８】
平文入力部１１で入力されたメッセージｍと、署名出力部１７で出力されたデジタル署名は、例えば、通信部１０４を介して相手端末へ送信される。
【０１４９】
図６は、デジタル署名検証装置の構成例を示したもので、図７は、図６のデジタル署名検証装置の処理動作を説明するためのフローチャートである。以下、図７に示すフローチャートを参照して、図６のデジタル署名検証装置の構成及び処理動作について説明する。
【０１５０】
図６のデジタル署名生成装置は、平文入力部２１から平文ｍを取得し、公開鍵入力部２４から公開鍵である有限体Fｐ上定義された３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）を取得する。
【０１５１】
まず、平文入力部２１から平文ｍが入力されることよって、デジタル署名検証処理が開始される（ステップＳ２０１）。
【０１５２】
入力された平文ｍは、ハッシュ値計算部２２に出力され、署名生成装置で用いられたものと同じハッシュ関数を利用してハッシュ値が計算される（ステップＳ２０２）。ここでは、ハッシュ値は署名生成装置で出力したハッシュ値と同じ「０ｘ１５１」となる。このハッシュ値は、ハッシュ値多項式生成部２３に出力される。
【０１５３】
ハッシュ値多項式生成部２３では、デジタル署名検証装置と同じアルゴリズムで、ハッシュ値多項式ｈ（ｔ）を計算する（ステップＳ２０３）。従って、ここで得られる、ハッシュ値多項式ｈ（ｔ）は、ｈ（ｔ）＝ｔ２＋５ｔ＋１ となる。
【０１５４】
得られたハッシュ値多項式ｈ（ｔ）は、署名検証部２６へ出力される。
【０１５５】
公開鍵記憶部２９は、図２や後述の図８に示した構成の鍵生成装置で生成された公開鍵である有限体Fｐ上定義された３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）の多項式を記憶する。
【０１５６】
公開鍵入力部２４は、公開鍵記憶部２９から公開鍵である３次元多様体の多項式を読み出して、署名生成部１５へ出力する（ステップＳ２０４）。ここでは、式（９）に示した３次元多様体、すなわち、公開鍵が署名検証部２６へ入力される。署名検証部２６は、入力された公開鍵を代数曲面生成部２７に出力する。
【０１５７】
署名検証部２６は、ステップＳ２０３で生成されたハッシュ値多項式ｈ（ｔ）を代数曲面生成部２７へ出力する。
【０１５８】
代数曲面生成部２７は、３次元多様体の変数ｓに、署名検証部２６から出力されたハッシュ値多項式ｈ（ｔ）を代入して、代数曲面Ｘ（ｘ，ｙ，ｔ）を生成する（ステップＳ２０５）。ここでは、次式（１２）に示すような代数曲面Ｘ（ｘ，ｙ，ｔ）が得られる。
【数３４】
【０１５９】
次に、署名入力部２５に入力された式（１１）に示した署名Ｄｓ：（Ｕｘ（ｔ），Ｕｙ（ｔ），ｔ）を署名検証部２６が読み込む（ステップＳ２０６）。この署名Ｄｓのｘ座標Ｕｘ（ｔ）＝ｔ３＋６ｔ２＋６ｔ＋１、ｙ座標Ｕｙ（ｔ）＝ｔ４＋５ｔ３＋２ｔ２＋５ｔ＋１を、それぞれ、式（１２）に示した代数曲面Ｘのｘ，ｙ座標に代入して、展開・整理する（ステップＳ２０７）。前述の通り、デジタル署名Ｄｓは代数曲面Ｘの因子となっているため、代入して整理すれば「０」となるはずである。従って、「０」となれば（ステップＳ２０８）、判定結果出力部２８に、「署名検証成功」を出力する（ステップＳ２０９）。「０」とならなければ、デジタル署名が間違っていたことを意味するので（ステップＳ２０８）、判定結果出力部２８に、「署名検証失敗」を出力する（ステップＳ２１０）。
【０１６０】
判定結果出力部２８は、判定結果を外部へ出力して、全ての処理を終了する。
【０１６１】
ここで示した例では、正当なデジタル署名なので、ステップＳ２０７で、代数曲面Ｘにデジタル署名Ｄｓ代入して整理した結果は、確かに「０」となり、署名検証部２６は、判定結果出力部２８に「署名検証成功」を出力し、判定結果出力部２８はそれを外部に出力して終了する。
【０１６２】
第１、第２のバリエーションは本実施形態において同様の処理で成立する。
【０１６３】
なお、図６に示す各機能（平文入力部２１、ハッシュ値計算部２２、ハッシュ値多項式生成部２３，公開鍵入力部２４、署名入力部２５、署名検証部２６、代数曲面生成部２７、判定結果出力部２８など）は、図１２に示すように、各種プログラムなどを記憶する記憶部１０１、ＣＰＵなどの演算部１００、出力部１０２、入力部１０３、通信部１０４などをバスに接続してなるコンピュータに、記憶部１０１に記憶されている各プログラムを実行させることにより、実現することができる。
【０１６４】
図１２では、記憶部１０１には、平文入力部２１、ハッシュ値計算部２２、ハッシュ値多項式生成部２３，公開鍵入力部２４、署名入力部２５、署名検証部２６、代数曲面生成部２７、判定結果出力部２８のそれぞれの機能を実現すための平文入力プログラム、ハッシュ値計算プログラム、ハッシュ値多項式生成プログラム、公開鍵入力プログラム、署名入力プログラム、署名検証プログラム、代数曲面生成プログラム、判定結果出力プログラムが記憶されている。また、記憶部１０１は、公開鍵を記憶する公開鍵記憶部２９として機能する。
【０１６５】
署名入力部２５には、デジタル署名生成装置で生成されたメッセージｍに対応するデジタル署名が入力される。
【０１６６】
次に、第２の鍵生成方法について説明する。図８は第２の鍵生成方法を用いた鍵生成装置の構成例を示したもので、図９は、図８の鍵生成装置の処理動作を説明するためのフローチャートである。以下、図９に示すフローチャートを参照して、図８の鍵生成装置の構成及び処理動作について説明する。
【０１６７】
鍵生成処理開始の指令が外部装置等から制御部１に伝えられ、鍵生成装置は鍵生成処理を開始する（ステップＳ３０１）。当該指令が制御部１に伝わると、制御部１は、素数生成部２に素数の生成を要請する。素数生成はランダムに素数を発生させても良いが、ここでは大きな素数を使う必要はないので、高々６ビット程度の素数からランダム若しくは（出力順を予め決めておくなどの手段で）恣意的に選択するか、当該鍵生成装置で予め定まっている素数を利用してもよい。ここでは素数ｐ＝１７が生成されたとする（ステップＳ３０２）。
【０１６８】
制御部１は、セクション生成部５に、素数ｐを送信し、セクション生成部５では、セクションの生成を開始する。セクション生成部５では、ｎ個のセクション
Ｄｉ：（ｘ，ｙ，ｓ，ｔ）＝（ｕｘ，ｉ（ｓ，ｔ），ｕｙ，ｉ（ｓ，ｔ），ｓ，ｔ）
（１≦ｉ≦ｎ）
のｘ座標ｕｘ，ｉ（ｓ，ｔ）、ｙ座標ｕｙ，ｉ（ｓ，ｔ）を以下に示す方法で決定する。
【０１６９】
まず、ｘ座標のｓに関する次元の最大値ｈｘ、ｔに関する次元の最大値ｋｘを定める（ステップＳ３０３）。即ち、
【数３５】
【０１７０】
ここでは、簡単のため、ｈｘ＝ｋｘ＝２とする。
【０１７１】
次に、ｓｈｘｔｋｘの項を含み、この次数の範囲内のセクションＤｉのｘ座標ｕｘ，ｉ（ｓ，ｔ）の生成を２変数多項式生成部３に要求する。ここでは、ｎ＝３であるので、２変数多項式生成部３は、ｕｘ，１（ｓ、ｔ）、ｕｘ，２（ｓ、ｔ）、ｕｘ，３（ｓ、ｔ）を、ランダムに順次決定する（ステップＳ３０４）。すなわち、
【数３６】
【０１７２】
が得られる。
【０１７３】
次に、ステップＳ３０３と同様に、ｙ座標のｓに関する次元の最大値ｈｙ、ｔに関する次元の最大値ｋｙを定める（ステップＳ３０５）。即ち、
【数３７】
【０１７４】
ここでは、簡単のためｈｙ＝ｋｙ＝２とする。
【０１７５】
次に、ｓｈｙｔｋｙの項を含み、この次数の範囲内のセクションＤｉのｙ座標ｕｙ，ｉ（ｓ，ｔ）の生成を２変数多項式生成部３に要求する。ここでは、ｎ＝３であるので、２変数多項式生成部３は、ｕｙ，１（ｓ、ｔ）、ｕｙ，２（ｓ、ｔ）、ｕｙ，３（ｓ、ｔ）を、ランダムに順次決定する（ステップＳ３０６）。すなわち、
【数３８】
【０１７６】
が得られる。
【０１７７】
以上で、セクションＤｉが生成された。
【０１７８】
これらセクションは制御部１に出力される。制御部１では、３次元多様体生成部６に、これらセクションを出力して、３次元多様体を生成させる。
【０１７９】
３次元多様体生成部６では、入力されたｕｘ，ｉ（ｓ，ｔ）、ｕｙ，ｉ（ｓ，ｔ）をそれぞれ、
ｘ因子（ｘ−ｕｘ，ｉ（ｓ，ｔ））、ｙ因子（ｙ−ｕｙ，ｉ（ｓ，ｔ））と因子化する（ステップＳ３０７）。
【０１８０】
そして、ｉが同じ値の因子ｘ（ｘ−ｕｘ，ｉ（ｓ，ｔ））及びｙ因子（ｙ−ｕｙ，ｉ（ｓ，ｔ））を、左辺と右辺にランダムに振り分ける。そして、左辺に振り分けられたｎ個の因子の積と、右辺に振り分けられたｎ個の因子の積とを等号で結ぶことにより、次式（１３）に示すような４変数（ｘ、ｙ、ｓ、ｔ）多項式を生成する。
【数３９】
【０１８１】
３次元多様体生成部６は、制御部１を介して、（もしくは直接）４変数多項式演算部８へ、上式（１３）の展開を依頼する。
【０１８２】
４変数多項式演算部８は、上式（１３）を展開して、当該４変数多項式に含まれる各項を、左辺と右辺のいずれか一方にまとめて、次式（１４）に示すような、３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）を得る（ステップＳ３０８）。
【数４０】
【０１８３】
４変数多項式演算部８は、得られた３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）を制御部１へ出力する。制御部１では３つのセクションと３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）を鍵として鍵出力部７へ出力し、鍵出力部７では、これらの鍵を出力する。
【０１８４】
なお、図８に示す各機能（制御部１、素数生成部２、２変数多項式生成部３、４変数多項式演算部８、セクション生成部５、３次元多様体生成部６、鍵出力部７など）は、図１３に示すように、各種プログラムなどを記憶する記憶部１０１、ＣＰＵなどの演算部１００、出力部１０２、入力部１０３、通信部１０４などをバスに接続してなるコンピュータに、記憶部１０１に記憶されている各プログラムを実行させることにより、実現することができる。
【０１８５】
図１３では、記憶部１０１には、制御部１、素数生成部２、２変数多項式生成部３、４変数多項式演算部８、セクション生成部５、３次元多様体生成部６、鍵出力部７のそれぞれの機能を実現すための鍵生成制御プログラム、素数生成プログラム、２変数多項式生成プログラム、４変数多項式演算プログラム、セクション生成プログラム、３次元多様体生成プログラム、鍵出力プログラムが記憶されている。
【０１８６】
図８の鍵出力部７から出力された秘密鍵や公開鍵は、例えば、通信部１０４を介して要求元へ送信されたり、後述するデジタル署名生成装置やデジタル署名検証装置へ渡される。
【０１８７】
図８の示す鍵生成装置の２変数多項式生成部３は、安全性を高めるため、セクションのｘ座標やｙ座標に対応する２変数多項式を生成する際、変数ｓ、ｔについての字数の最大値（ｘ座標の変数ｓの最大次数ｈｘ、ｘ座標の変数ｔの最大次数ｋｘ、ｙ座標の変数ｓの最大次数ｈｙ、ｙ座標の変数ｔの最大多項数ｋｙ）をそれぞれ定め、ｘ座標については、ｓｈｘｔｋｘの項を必ず含む２変数多項式を生成、ｙ座標については、ｓｈｙｔｋｙの項を必ず含む２変数多項式を生成している。
【０１８８】
しかし、この場合に限らず、次数が最大値ｈｘ以下の変数ｓと、次数が最大値ｋｘ以下の変数ｔとのうちの少なくとも１つを因子として有する複数の単項式とを含む２変数多項式ｕｘ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）や、次数が最大値ｈｙ以下の変数ｓと、次数が最大値ｋｙ以下の変数ｔとのうちの少なくとも１つを因子として有する複数の単項式とを含む２変数多項式ｕｙ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）を生成すれば、ｎ個のセクションを持つ３次元多様体を生成することができる。
【０１８９】
以上説明したように、上記実施形態によれば、メッセージ送信側のデジタル署名生成装置は有限体Fｐならびに、ｘ座標、ｙ座標、パラメータｓ、及びパラメータｔで表される前記有限体Fｐ上定義された３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）内の曲面のうち、ｘ座標及びｙ座標がパラメータｓ及びｔの関数で表されたセクションＤ（ｕｘ（ｓ，ｔ），ｕｙ（ｓ，ｙ），ｓ，ｔ）を、署名生成用の秘密鍵として記憶手段に記憶する。ＣＰＵ等の演算手段は、メッセージｍのハッシュ値を計算し、このハッシュ値を前記有限体Fｐ上定義された１変数多項式ｈ（ｔ）の係数に埋め込み、ハッシュ値多項式を生成する。そして、演算手段は、記憶手段からセクションを１つ読み出して、それを署名生成用の秘密鍵として用いて、デジタル署名を生成する。すなわち、セクションのｓ座標に上記ハッシュ値多項式を代入することで、ｘ座標及びｙ座標がパラメータｔの関数で表された前記セクション上の曲線であるデジタル署名Ｄｓ（Ｕｘ（ｔ），Ｕｙ（ｔ），ｔ）を生成する。このようにして生成されたデジタル署名は、上記メッセージｍとともに、メッセージ送信側の送信手段により、メッセージ受信側へ送信される。
【０１９０】
記憶手段は、異なる複数のセクションＤｉ（ｕｘ，ｉ（ｓ，ｔ），ｕｙ，ｉ（ｓ，ｔ），ｓ，ｔ）（ｉは、０≦ｉ≦ｎの任意の正の整数）を記憶し、デジタル署名を生成する度に、この記憶手段に記憶された複数のセクションＤｉのうちの任意の１つのセクションを選択して、デジタル署名を生成することにより、より安全性が高まる。
【０１９１】
また、メッセージ受信側のデジタル署名検証装置は、記憶手段に、有限体Fｐならびに公開鍵として、ｘ座標、ｙ座標、パラメータｓ、及びパラメータｔで表される前記有限体Fｐ上定義された３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）の多項式を記憶する。メッセージｍと当該メッセージｍに対応するデジタル署名Ｄｓ：（Ｕｘ（ｔ），Ｕｙ（ｔ），ｔ）とが入力されると、ＣＰＵ等の演算手段が、メッセージｍのハッシュ値を計算し、このハッシュ値を前記有限体Fｐ上定義された１変数多項式ｈ（ｔ）に埋め込み、ハッシュ値多項式を生成する。そして、演算手段は、記憶手段から上記メッセージ送信側に対応する公開鍵である３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）の多項式のｓ座標に、当該ハッシュ値多項式を代入して、ハッシュ値に対応した代数曲面Ｘ（ｘ，ｙ，ｔ）を計算する。さらに、演算手段は、代数曲面Ｘ（ｘ，ｙ，ｔ）に、上記デジタル署名を代入して、メッセージ及びデジタル署名の正当性を検証する。すなわち、代数曲面Ｘ（ｘ，ｙ，ｔ）のｘ座標に、デジタル署名のｘ座標（変数ｔの多項式で表された）Ｕｘ（ｔ）を代入し、代数曲面Ｘ（ｘ，ｙ，ｔ）のｙ座標に、デジタル署名のｙ座標（変数ｔの多項式で表された）Ｕｙ（ｔ）を代入した後、式を展開し（多項式の積を単項式の和の形で表す）、整理する。この結果（代数曲面Ｘ（ｘ，ｙ，ｔ）にデジタル署名のｘ座標およびｙ座標を代入した結果）が「０」であるとき、メッセージｍが改竄されていないこと、及び、メッセージｍが、上記公開鍵に対応する正当なメッセージ送信者から送信されたことが検証されたことになる（署名検証成功）。
【０１９２】
鍵生成装置では、ＣＰＵ等の演算手段が、前記有限体Fｐ上定義された、パラメータｓ、ｔに関する第１の２変数多項式λｘ（ｓ，ｔ）と、この第１の２変数多項式λｘ（ｓ，ｔ）で割り切れる、前記有限体Fｐ上定義された第２の２変数多項式λｙ（ｓ，ｔ）を生成し、次に、前記有限体Fｐ上定義された、変数ｘがパラメータｓ，ｔで表される２つの２変数多項式ｕｘ（ｓ，ｔ）、ｖｘ（ｓ，ｔ）を、当該２つの２変数多項式の差分｛ｕｘ（ｓ，ｔ）−ｖｘ（ｓ，ｔ）｝がλｘ（ｓ，ｔ）となるように生成し、さらに、前記有限体Fｐ上定義された、変数ｙがパラメータｓ，ｔで表される２つの２変数多項式ｕｙ（ｓ，ｔ）、ｖｙ（ｓ，ｔ）を、当該２つの２変数多項式の差分｛ｕｙ（ｓ，ｔ）−ｖｙ（ｓ，ｔ）｝がλｙ（ｓ，ｔ）となるように生成する。そして、演算手段は、２変数多項式ｕｘ（ｓ，ｔ）をｘ座標、２変数関数ｕｙ（ｓ，ｔ）をｙ座標とするセクションＤ１：（ｘ，ｙ，ｓ，ｔ）＝（ｕｘ（ｓ，ｔ），ｕｙ（ｓ，ｔ），ｓ，ｔ）と、２変数多項式ｖｘ（ｓ，ｔ）をｘ座標、２変数関数ｖｙ（ｓ，ｔ）をｙ座標とするセクションＤ２：（ｘ，ｙ，ｓ，ｔ）＝（ｖｘ（ｓ，ｔ），ｖｙ（ｓ，ｔ），ｓ，ｔ）を生成する。これら２つのセクションＤ１、Ｄ２が秘密鍵である。また、この２つのセクションＤ１，Ｄ２を持つ３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）を生成する。この３次元多様体Ａが、公開鍵である。
【０１９３】
他の鍵生成装置では、ＣＰＵ等の演算手段が、パラメータｓ、ｔに関する第１番目から第ｎ（ｎは正の整数）番目までのｎ（ｎは正の整数）個の前記有限体Fｐ上定義された２変数多項式ｕｘ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）と、パラメータｓ、ｔに関する第１番目から第ｎ番目までのｎ個の前記有限体Fｐ上定義された２変数多項式ｕｙ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）を生成する。演算手段は、生成された第ｉ（１≦ｉ≦ｎ）番目の２変数多項式ｕｘ，ｉ（ｓ，ｔ）及びｕｙ，ｉ（ｓ，ｔ）をそれぞれｘ座標、ｙ座標とする第ｉ番目のセクションＤｉ：（ｘ，ｙ，ｓ，ｔ）＝（ｕｘ，ｉ（ｓ，ｔ）、ｕｙ，ｉ（ｓ，ｔ），ｓ，ｔ）（１≦ｉ≦ｎ）を生成することにより、第１番目から第ｎ番目までのｎ個のセクションＤｉ（１≦ｉ≦ｎ）を求める。このｎ個のセクションが秘密鍵である。さらに、演算手段は、生成された第ｉ（１≦ｉ≦ｎ）番目の２変数多項式ｕｘ，ｉ（ｓ，ｔ）及びｕｙ，ｉ（ｓ，ｔ）を用いて、第ｉ番目のｘ因子（ｘ−ｕｘ，ｉ（ｓ，ｔ））及びｙ因子（ｙ−ｕｙ，ｉ（ｓ，ｔ））を生成することにより、第１番目から第ｎ番目までのｘ因子及びｙ因子を求める。演算手段は、生成された第ｉ（１≦ｉ≦ｎ）番目のｘ因子及びｙ因子を左辺と右辺に振り分けて、左辺に振り分けられたｎ個のｘ因子及びｙ因子の積と、右辺に振り分けられたｎ個のｘ因子及びｙ因子の積とを等号で結ぶことにより得られる等式を生成すると、この生成された等式を展開することにより、公開鍵である、３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）の多項式を生成する。
【０１９４】
このように、上記実施形態にかかる公開鍵暗号に基づくデジタル署名システムは、頑健（robust）で、安全性・信頼性の高いデジタル署名を生成することができ、しかも少ない計算量で実現可能である。
【符号の説明】
【０１９５】
１…制御部、２…素数生成部、３…２変数多項式生成部、４…２変数多項式演算部、５…セクション生成部、６…３次元多様体生成部、７…鍵出力部、１１…平文入力部、１２…ハッシュ値計算部、１３…ハッシュ値多項式生成部、１４…秘密鍵入力部、１５…署名生成部、１６…セクション選択部、１７…署名出力部、２１…平文入力部、２２…ハッシュ値計算部、２３…ハッシュ値多項式生成部、２４…公開鍵入力部、２５…署名入力部、２６…署名検証部、２７…代数曲面生成部、２８…判定結果出力部、８…４変数多項式演算部。
【特許請求の範囲】
【請求項１】
有限体Fｑならびに署名検証用の公開鍵として用いられる、ｘ座標、ｙ座標、パラメータｓ、及びパラメータｔで表される前記有限体Fｑ上定義された３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）と、署名生成用の秘密鍵として用いられる前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）内の曲面のうち、ｘ座標及びｙ座標がパラメータｓ及びｔの関数で表されたセクションを生成する鍵生成装置であって、
前記有限体Fｑ上定義された、パラメータｓ、ｔに関する第１の２変数多項式λｘ（ｓ，ｔ）を生成する第１の生成手段と、
前記第１の２変数多項式λｘ（ｓ，ｔ）で割り切れる、前記有限体Fｑ上定義された第２の２変数多項式λｙ（ｓ，ｔ）を生成する第２の生成手段と、
前記有限体Fｑ上定義された、パラメータｓ，ｔに関する２つの２変数多項式ｕｘ（ｓ，ｔ）、ｖｘ（ｓ，ｔ）を、当該２つの２変数多項式の差分｛ｕｘ（ｓ，ｔ）−ｖｘ（ｓ，ｔ）｝が前記第１の２変数多項式λｘ（ｓ，ｔ）となるように生成する第３の生成手段と、
前記有限体Fｑ上定義された、パラメータｓ，ｔに関する２つの２変数多項式ｕｙ（ｓ，ｔ）、ｖｙ（ｓ，ｔ）を、当該２つの２変数多項式の差分｛ｕｙ（ｓ，ｔ）−ｖｙ（ｓ，ｔ）｝が前記第２の２変数多項式λｙ（ｓ，ｔ）となるように生成する第４の生成手段と、
前記第３の生成手段で生成された２変数多項式ｕｘ（ｓ，ｔ）をｘ座標、前記第４の生成手段で生成された２変数関数ｕｙ（ｓ，ｔ）をｙ座標とするセクションＤ１：（ｘ，ｙ，ｓ，ｔ）＝（ｕｘ（ｓ，ｔ），ｕｙ（ｓ，ｔ），ｓ，ｔ）と、前記第３の生成手段で生成された２変数多項式ｖｘ（ｓ，ｔ）をｘ座標、前記第４の生成手段で生成された２変数関数ｖｙ（ｓ，ｔ）をｙ座標とするセクションＤ２：（ｘ，ｙ，ｓ，ｔ）＝（ｖｘ（ｓ，ｔ），ｖｙ（ｓ，ｔ），ｓ，ｔ）を生成するセクション生成手段と、
前記セクションＤ１及び前記セクションＤ２を含む前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）の多項式を生成する３次元多様体生成手段と、
を具備したことを特徴とする鍵生成装置。
【請求項２】
有限体Fｑならびにｘ座標、ｙ座標、パラメータｓ、及びパラメータｔで表された、署名検証用の公開鍵として用いられる前記有限体Fｑ上定義された３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）と、前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）内の曲面のうち、ｘ座標及びｙ座標がパラメータｓ及びｔの関数で表された、署名生成用の秘密鍵として用いられるセクションを生成する鍵生成装置であって、
パラメータｓ、ｔに関する第１番目から第ｎ（ｎは正の整数）番目までのｎ（ｎは正の整数）個の前記有限体Fｑ上定義された２変数多項式ｕｘ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）と、パラメータｓ、ｔに関する第１番目から第ｎ番目までのｎ個の前記有限体Fｑ上定義された２変数多項式ｕｙ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）を生成する第１の生成手段と、
前記第１の生成手段で生成された第ｉ（１≦ｉ≦ｎ）番目の２変数多項式ｕｘ，ｉ（ｓ，ｔ）及びｕｙ，ｉ（ｓ，ｔ）をそれぞれｘ座標、ｙ座標とする第ｉ番目のセクションＤｉ：（ｘ，ｙ，ｓ，ｔ）＝（ｕｘ，ｉ（ｓ，ｔ）、ｕｙ，ｉ（ｓ，ｔ），ｓ，ｔ）（１≦ｉ≦ｎ）を生成することにより、第１番目から第ｎ番目までのｎ個のセクションＤｉ（１≦ｉ≦ｎ）を求める第２の生成手段と、
前記第１の生成手段で生成された第ｉ（１≦ｉ≦ｎ）番目の２変数多項式ｕｘ，ｉ（ｓ，ｔ）及びｕｙ，ｉ（ｓ，ｔ）を用いて、第ｉ番目のｘ因子（ｘ−ｕｘ，ｉ（ｓ，ｔ））及びｙ因子（ｙ−ｕｙ，ｉ（ｓ，ｔ））を生成することにより、第１番目から第ｎ番目までのｘ因子及びｙ因子を求める第３の生成手段と、
前記第３の生成手段で生成された第ｉ（１≦ｉ≦ｎ）番目のｘ因子及びｙ因子を左辺と右辺に振り分けて、左辺に振り分けられたｎ個のｘ因子及びｙ因子の積と、右辺に振り分けられたｎ個のｘ因子及びｙ因子の積とを等号で結ぶことにより得られる等式を生成する第４の生成手段と、
前記第４の生成手段で生成された等式を展開することにより、前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）の多項式を生成する第５の生成手段と、
を具備したことを特徴とする鍵生成装置。
【請求項３】
前記第１の生成手段は、
前記２変数多項式ｕｘ，ｉ（ｓ，ｔ）のパラメータｓについての次数の最大値ｈｘと、パラメータｔについての次数の最大値ｋｘを決定する手段と、
次数が最大値ｈｘ以下の変数ｓと次数が最大値ｋｘ以下の変数ｔとのうちの少なくとも１つを因子として有する複数の単項式と、ｓｈｘｔｋｘの項とを含む第ｉ番目の２変数多項式ｕｘ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）を生成する手段と、
前記２変数多項式ｕｙ，ｉ（ｓ，ｔ）の変数ｓについての次数の最大値ｈｙと、変数ｔについての次数の最大値ｋｙを決定する手段と、
次数が最大値ｈｙ以下の変数ｓと次数が最大値ｋｙ以下の変数ｔとのうちの少なくとも１つを因子として有する複数の単項式と、ｓｈｙｔｋｙの項とを含む第ｉ番目の前記２変数多項式ｕｙ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）を生成する手段と、
を含むことを特徴とする請求項２記載の鍵生成装置。
【請求項４】
第１の生成手段と第２の生成手段と第３の生成手段と第４の生成手段とセクション生成手段と３次元多様体生成手段とを備え、有限体Fｑならびに署名検証用の公開鍵として用いられる、ｘ座標、ｙ座標、パラメータｓ、及びパラメータｔで表される前記有限体Fｑ上定義された３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）と、署名生成用の秘密鍵として用いられる前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）内の曲面のうち、ｘ座標及びｙ座標がパラメータｓ及びｔの関数で表されたセクションを生成する鍵生成装置の鍵生成方法であって、
前記第１の生成手段が、前記有限体Fｑ上定義された、パラメータｓ、ｔに関する第１の２変数多項式λｘ（ｓ，ｔ）を生成する第１のステップと、
前記第２の生成手段が、前記第１の２変数多項式λｘ（ｓ，ｔ）で割り切れる、前記有限体Fｑ上定義された第２の２変数多項式λｙ（ｓ，ｔ）を生成する第２のステップと、
前記第３の生成手段が、前記有限体Fｑ上定義された、パラメータｓ，ｔに関する２つの２変数多項式ｕｘ（ｓ，ｔ）、ｖｘ（ｓ，ｔ）を、当該２つの２変数多項式の差分｛ｕｘ（ｓ，ｔ）−ｖｘ（ｓ，ｔ）｝が前記第１の２変数多項式λｘ（ｓ，ｔ）となるように生成する第３のステップと、
前記第４の生成手段が、前記有限体Fｑ上定義された、パラメータｓ，ｔに関する２つの２変数多項式ｕｙ（ｓ，ｔ）、ｖｙ（ｓ，ｔ）を、当該２つの２変数多項式の差分｛ｕｙ（ｓ，ｔ）−ｖｙ（ｓ，ｔ）｝が前記第２の２変数多項式λｙ（ｓ，ｔ）となるように生成する第４のステップと、
前記セクション生成手段が、前記第３のステップにおいて前記前記第３の生成手段により生成された２変数多項式ｕｘ（ｓ，ｔ）をｘ座標、前記第４のステップにおいて前記第４の生成手段により生成された２変数関数ｕｙ（ｓ，ｔ）をｙ座標とするセクションＤ１：（ｘ，ｙ，ｓ，ｔ）＝（ｕｘ（ｓ，ｔ），ｕｙ（ｓ，ｔ），ｓ，ｔ）と、前記第３のステップにおいて前記前記第３の生成手段により生成された２変数多項式ｖｘ（ｓ，ｔ）をｘ座標、前記第４のステップにおいて前記第４の生成手段により生成された２変数関数ｖｙ（ｓ，ｔ）をｙ座標とするセクションＤ２：（ｘ，ｙ，ｓ，ｔ）＝（ｖｘ（ｓ，ｔ），ｖｙ（ｓ，ｔ），ｓ，ｔ）を生成する第５のステップと、
前記３次元多様体生成手段が、前記セクションＤ１及び前記セクションＤ２を含む前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）の多項式を生成する第６のステップと、
を有することを特徴とする鍵生成方法。
【請求項５】
第１の生成手段と第２の生成手段と第３の生成手段と第４の生成手段と第５の生成手段とを備え、有限体Fｑならびにｘ座標、ｙ座標、パラメータｓ、及びパラメータｔで表された、署名検証用の公開鍵として用いられる前記有限体Fｑ上定義された３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）と、前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）内の曲面のうち、ｘ座標及びｙ座標がパラメータｓ及びｔの関数で表された、署名生成用の秘密鍵として用いられるセクションを生成する鍵生成装置の鍵生成方法であって、
前記第１の生成手段が、パラメータｓ、ｔに関する第１番目から第ｎ（ｎは正の整数）番目までのｎ（ｎは正の整数）個の前記有限体Fｑ上定義された２変数多項式ｕｘ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）と、パラメータｓ、ｔに関する第１番目から第ｎ番目までのｎ個の前記有限体Fｑ上定義された２変数多項式ｕｙ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）を生成する第１のステップと、
前記第２の生成手段が、前記第１のステップにおいて前記第１の生成手段により生成された第ｉ（１≦ｉ≦ｎ）番目の２変数多項式ｕｘ，ｉ（ｓ，ｔ）及びｕｙ，ｉ（ｓ，ｔ）をそれぞれｘ座標、ｙ座標とする第ｉ番目のセクションＤｉ：（ｘ，ｙ，ｓ，ｔ）＝（ｕｘ，ｉ（ｓ，ｔ）、ｕｙ，ｉ（ｓ，ｔ），ｓ，ｔ）（１≦ｉ≦ｎ）を生成することにより、第１番目から第ｎ番目までのｎ個のセクションＤｉ（１≦ｉ≦ｎ）を求める第２のステップと、
前記第３の生成手段が、前記第１のステップにおいて前記第１の生成手段により生成された第ｉ（１≦ｉ≦ｎ）番目の２変数多項式ｕｘ，ｉ（ｓ，ｔ）及びｕｙ，ｉ（ｓ，ｔ）を用いて、第ｉ番目のｘ因子（ｘ−ｕｘ，ｉ（ｓ，ｔ））及びｙ因子（ｙ−ｕｙ，ｉ（ｓ，ｔ））を生成することにより、第１番目から第ｎ番目までのｘ因子及びｙ因子を求める第３のステップと、
前記第４の生成手段が、前記第３のステップにおいて前記第３の生成手段により生成された第ｉ（１≦ｉ≦ｎ）番目のｘ因子及びｙ因子を左辺と右辺に振り分けて、左辺に振り分けられたｎ個のｘ因子及びｙ因子の積と、右辺に振り分けられたｎ個のｘ因子及びｙ因子の積とを等号で結ぶことにより得られる等式を生成する第４のステップと、
前記第５の生成手段が、前記第４のステップにおいて前記第４の生成手段により生成された等式を展開することにより、前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）の多項式を生成する第５のステップと、
を有することを特徴とする鍵生成方法。
【請求項６】
前記第１のステップは、
前記２変数多項式ｕｘ，ｉ（ｓ，ｔ）のパラメータｓについての次数の最大値ｈｘと、パラメータｔについての次数の最大値ｋｘを決定するステップと、
次数が最大値ｈｘ以下の変数ｓと次数が最大値ｋｘ以下の変数ｔとのうちの少なくとも１つを因子として有する複数の単項式と、ｓｈｘｔｋｘの項とを含む第ｉ番目の２変数多項式ｕｘ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）を生成するステップと、
前記２変数多項式ｕｙ，ｉ（ｓ，ｔ）の変数ｓについての次数の最大値ｈｙと、変数ｔについての次数の最大値ｋｙを決定するステップと、
次数が最大値ｈｙ以下の変数ｓと、次数が最大値ｋｙ以下の変数ｔとのうちの少なくとも１つを因子として有する複数の単項式と、ｓｈｙｔｋｙの項とを含む第ｉ番目の前記２変数多項式ｕｙ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）を生成するステップと、
を含むことを特徴とする請求項５記載の鍵生成装置。
【請求項７】
第１の生成手段と第２の生成手段と第３の生成手段と第４の生成手段とセクション生成手段と３次元多様体生成手段とを備え、有限体Fｑならびに署名検証用の公開鍵として用いられる、ｘ座標、ｙ座標、パラメータｓ、及びパラメータｔで表される前記有限体Fｑ上定義された３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）と、署名生成用の秘密鍵として用いられる前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）内の曲面のうち、ｘ座標及びｙ座標がパラメータｓ及びｔの関数で表されたセクションを生成する鍵生成装置としてコンピュータを機能させるための鍵生成プログラムであって、
前記第１の生成手段が、前記有限体Fｑ上定義された、パラメータｓ、ｔに関する第１の２変数多項式λｘ（ｓ，ｔ）を生成する第１のステップと、
前記第２の生成手段が、前記第１の２変数多項式λｘ（ｓ，ｔ）で割り切れる、前記有限体Fｑ上定義された第２の２変数多項式λｙ（ｓ，ｔ）を生成する第２のステップと、
前記第３の生成手段が、前記有限体Fｑ上定義された、パラメータｓ，ｔに関する２つの２変数多項式ｕｘ（ｓ，ｔ）、ｖｘ（ｓ，ｔ）を、当該２つの２変数多項式の差分｛ｕｘ（ｓ，ｔ）−ｖｘ（ｓ，ｔ）｝が前記第１の２変数多項式λｘ（ｓ，ｔ）となるように生成する第３のステップと、
前記第４の生成手段が、前記有限体Fｑ上定義された、パラメータｓ，ｔに関する２つの２変数多項式ｕｙ（ｓ，ｔ）、ｖｙ（ｓ，ｔ）を、当該２つの２変数多項式の差分｛ｕｙ（ｓ，ｔ）−ｖｙ（ｓ，ｔ）｝が前記第２の２変数多項式λｙ（ｓ，ｔ）となるように生成する第４のステップと、
前記セクション生成手段が、前記第３のステップにおいて前記前記第３の生成手段により生成された２変数多項式ｕｘ（ｓ，ｔ）をｘ座標、前記第４のステップにおいて前記第４の生成手段により生成された２変数関数ｕｙ（ｓ，ｔ）をｙ座標とするセクションＤ１：（ｘ，ｙ，ｓ，ｔ）＝（ｕｘ（ｓ，ｔ），ｕｙ（ｓ，ｔ），ｓ，ｔ）と、前記第３のステップにおいて前記前記第３の生成手段により生成された２変数多項式ｖｘ（ｓ，ｔ）をｘ座標、前記第４のステップにおいて前記第４の生成手段により生成された２変数関数ｖｙ（ｓ，ｔ）をｙ座標とするセクションＤ２：（ｘ，ｙ，ｓ，ｔ）＝（ｖｘ（ｓ，ｔ），ｖｙ（ｓ，ｔ），ｓ，ｔ）を生成する第５のステップと、
前記３次元多様体生成手段が、前記セクションＤ１及び前記セクションＤ２を含む前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）の多項式を生成する第６のステップと、
をコンピュータに実行させるための鍵生成プログラム。
【請求項８】
第１の生成手段と第２の生成手段と第３の生成手段と第４の生成手段と第５の生成手段とを備え、有限体Fｑならびにｘ座標、ｙ座標、パラメータｓ、及びパラメータｔで表された、署名検証用の公開鍵として用いられる前記有限体Fｑ上定義された３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）と、前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）内の曲面のうち、ｘ座標及びｙ座標がパラメータｓ及びｔの関数で表された、署名生成用の秘密鍵として用いられるセクションを生成する鍵生成装置としてコンピュータを機能させるための鍵生成プログラムであって、
前記第１の生成手段が、パラメータｓ、ｔに関する第１番目から第ｎ（ｎは正の整数）番目までのｎ（ｎは正の整数）個の前記有限体Fｑ上定義された２変数多項式ｕｘ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）と、パラメータｓ、ｔに関する第１番目から第ｎ番目までのｎ個の前記有限体Fｑ上定義された２変数多項式ｕｙ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）を生成する第１のステップと、
前記第２の生成手段が、前記第１のステップにおいて前記第１の生成手段により生成された第ｉ（１≦ｉ≦ｎ）番目の２変数多項式ｕｘ，ｉ（ｓ，ｔ）及びｕｙ，ｉ（ｓ，ｔ）をそれぞれｘ座標、ｙ座標とする第ｉ番目のセクションＤｉ：（ｘ，ｙ，ｓ，ｔ）＝（ｕｘ，ｉ（ｓ，ｔ）、ｕｙ，ｉ（ｓ，ｔ），ｓ，ｔ）（１≦ｉ≦ｎ）を生成することにより、第１番目から第ｎ番目までのｎ個のセクションＤｉ（１≦ｉ≦ｎ）を求める第２のステップと、
前記第３の生成手段が、前記第１のステップにおいて前記第１の生成手段により生成された第ｉ（１≦ｉ≦ｎ）番目の２変数多項式ｕｘ，ｉ（ｓ，ｔ）及びｕｙ，ｉ（ｓ，ｔ）を用いて、第ｉ番目のｘ因子（ｘ−ｕｘ，ｉ（ｓ，ｔ））及びｙ因子（ｙ−ｕｙ，ｉ（ｓ，ｔ））を生成することにより、第１番目から第ｎ番目までのｘ因子及びｙ因子を求める第３のステップと、
前記第４の生成手段が、前記第３のステップにおいて前記第３の生成手段により生成された第ｉ（１≦ｉ≦ｎ）番目のｘ因子及びｙ因子を左辺と右辺に振り分けて、左辺に振り分けられたｎ個のｘ因子及びｙ因子の積と、右辺に振り分けられたｎ個のｘ因子及びｙ因子の積とを等号で結ぶことにより得られる等式を生成する第４のステップと、
前記第５の生成手段が、前記第４のステップにおいて前記第４の生成手段により生成された等式を展開することにより、前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）の多項式を生成する第５のステップと、
をコンピュータに実行させるための鍵生成プログラム。
【請求項９】
前記第１のステップは、
前記２変数多項式ｕｘ，ｉ（ｓ，ｔ）のパラメータｓについての次数の最大値ｈｘと、パラメータｔについての次数の最大値ｋｘを決定するステップと、
次数が最大値ｈｘ以下の変数ｓと次数が最大値ｋｘ以下の変数ｔとのうちの少なくとも１つを因子として有する複数の単項式と、ｓｈｘｔｋｘの項とを含む第ｉ番目の２変数多項式ｕｘ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）を生成するステップと、
前記２変数多項式ｕｙ，ｉ（ｓ，ｔ）の変数ｓについての次数の最大値ｈｙと、変数ｔについての次数の最大値ｋｙを決定するステップと、
次数が最大値ｈｙ以下の変数ｓと次数が最大値ｋｙ以下の変数ｔとのうちの少なくとも１つを因子として有する複数の単項式と、ｓｈｙｔｋｙの項とを含む第ｉ番目の前記２変数多項式ｕｙ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）を生成するステップと、
を含むことを特徴とする請求項８記載の鍵生成プログラム。
【請求項１】
有限体Fｑならびに署名検証用の公開鍵として用いられる、ｘ座標、ｙ座標、パラメータｓ、及びパラメータｔで表される前記有限体Fｑ上定義された３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）と、署名生成用の秘密鍵として用いられる前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）内の曲面のうち、ｘ座標及びｙ座標がパラメータｓ及びｔの関数で表されたセクションを生成する鍵生成装置であって、
前記有限体Fｑ上定義された、パラメータｓ、ｔに関する第１の２変数多項式λｘ（ｓ，ｔ）を生成する第１の生成手段と、
前記第１の２変数多項式λｘ（ｓ，ｔ）で割り切れる、前記有限体Fｑ上定義された第２の２変数多項式λｙ（ｓ，ｔ）を生成する第２の生成手段と、
前記有限体Fｑ上定義された、パラメータｓ，ｔに関する２つの２変数多項式ｕｘ（ｓ，ｔ）、ｖｘ（ｓ，ｔ）を、当該２つの２変数多項式の差分｛ｕｘ（ｓ，ｔ）−ｖｘ（ｓ，ｔ）｝が前記第１の２変数多項式λｘ（ｓ，ｔ）となるように生成する第３の生成手段と、
前記有限体Fｑ上定義された、パラメータｓ，ｔに関する２つの２変数多項式ｕｙ（ｓ，ｔ）、ｖｙ（ｓ，ｔ）を、当該２つの２変数多項式の差分｛ｕｙ（ｓ，ｔ）−ｖｙ（ｓ，ｔ）｝が前記第２の２変数多項式λｙ（ｓ，ｔ）となるように生成する第４の生成手段と、
前記第３の生成手段で生成された２変数多項式ｕｘ（ｓ，ｔ）をｘ座標、前記第４の生成手段で生成された２変数関数ｕｙ（ｓ，ｔ）をｙ座標とするセクションＤ１：（ｘ，ｙ，ｓ，ｔ）＝（ｕｘ（ｓ，ｔ），ｕｙ（ｓ，ｔ），ｓ，ｔ）と、前記第３の生成手段で生成された２変数多項式ｖｘ（ｓ，ｔ）をｘ座標、前記第４の生成手段で生成された２変数関数ｖｙ（ｓ，ｔ）をｙ座標とするセクションＤ２：（ｘ，ｙ，ｓ，ｔ）＝（ｖｘ（ｓ，ｔ），ｖｙ（ｓ，ｔ），ｓ，ｔ）を生成するセクション生成手段と、
前記セクションＤ１及び前記セクションＤ２を含む前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）の多項式を生成する３次元多様体生成手段と、
を具備したことを特徴とする鍵生成装置。
【請求項２】
有限体Fｑならびにｘ座標、ｙ座標、パラメータｓ、及びパラメータｔで表された、署名検証用の公開鍵として用いられる前記有限体Fｑ上定義された３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）と、前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）内の曲面のうち、ｘ座標及びｙ座標がパラメータｓ及びｔの関数で表された、署名生成用の秘密鍵として用いられるセクションを生成する鍵生成装置であって、
パラメータｓ、ｔに関する第１番目から第ｎ（ｎは正の整数）番目までのｎ（ｎは正の整数）個の前記有限体Fｑ上定義された２変数多項式ｕｘ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）と、パラメータｓ、ｔに関する第１番目から第ｎ番目までのｎ個の前記有限体Fｑ上定義された２変数多項式ｕｙ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）を生成する第１の生成手段と、
前記第１の生成手段で生成された第ｉ（１≦ｉ≦ｎ）番目の２変数多項式ｕｘ，ｉ（ｓ，ｔ）及びｕｙ，ｉ（ｓ，ｔ）をそれぞれｘ座標、ｙ座標とする第ｉ番目のセクションＤｉ：（ｘ，ｙ，ｓ，ｔ）＝（ｕｘ，ｉ（ｓ，ｔ）、ｕｙ，ｉ（ｓ，ｔ），ｓ，ｔ）（１≦ｉ≦ｎ）を生成することにより、第１番目から第ｎ番目までのｎ個のセクションＤｉ（１≦ｉ≦ｎ）を求める第２の生成手段と、
前記第１の生成手段で生成された第ｉ（１≦ｉ≦ｎ）番目の２変数多項式ｕｘ，ｉ（ｓ，ｔ）及びｕｙ，ｉ（ｓ，ｔ）を用いて、第ｉ番目のｘ因子（ｘ−ｕｘ，ｉ（ｓ，ｔ））及びｙ因子（ｙ−ｕｙ，ｉ（ｓ，ｔ））を生成することにより、第１番目から第ｎ番目までのｘ因子及びｙ因子を求める第３の生成手段と、
前記第３の生成手段で生成された第ｉ（１≦ｉ≦ｎ）番目のｘ因子及びｙ因子を左辺と右辺に振り分けて、左辺に振り分けられたｎ個のｘ因子及びｙ因子の積と、右辺に振り分けられたｎ個のｘ因子及びｙ因子の積とを等号で結ぶことにより得られる等式を生成する第４の生成手段と、
前記第４の生成手段で生成された等式を展開することにより、前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）の多項式を生成する第５の生成手段と、
を具備したことを特徴とする鍵生成装置。
【請求項３】
前記第１の生成手段は、
前記２変数多項式ｕｘ，ｉ（ｓ，ｔ）のパラメータｓについての次数の最大値ｈｘと、パラメータｔについての次数の最大値ｋｘを決定する手段と、
次数が最大値ｈｘ以下の変数ｓと次数が最大値ｋｘ以下の変数ｔとのうちの少なくとも１つを因子として有する複数の単項式と、ｓｈｘｔｋｘの項とを含む第ｉ番目の２変数多項式ｕｘ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）を生成する手段と、
前記２変数多項式ｕｙ，ｉ（ｓ，ｔ）の変数ｓについての次数の最大値ｈｙと、変数ｔについての次数の最大値ｋｙを決定する手段と、
次数が最大値ｈｙ以下の変数ｓと次数が最大値ｋｙ以下の変数ｔとのうちの少なくとも１つを因子として有する複数の単項式と、ｓｈｙｔｋｙの項とを含む第ｉ番目の前記２変数多項式ｕｙ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）を生成する手段と、
を含むことを特徴とする請求項２記載の鍵生成装置。
【請求項４】
第１の生成手段と第２の生成手段と第３の生成手段と第４の生成手段とセクション生成手段と３次元多様体生成手段とを備え、有限体Fｑならびに署名検証用の公開鍵として用いられる、ｘ座標、ｙ座標、パラメータｓ、及びパラメータｔで表される前記有限体Fｑ上定義された３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）と、署名生成用の秘密鍵として用いられる前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）内の曲面のうち、ｘ座標及びｙ座標がパラメータｓ及びｔの関数で表されたセクションを生成する鍵生成装置の鍵生成方法であって、
前記第１の生成手段が、前記有限体Fｑ上定義された、パラメータｓ、ｔに関する第１の２変数多項式λｘ（ｓ，ｔ）を生成する第１のステップと、
前記第２の生成手段が、前記第１の２変数多項式λｘ（ｓ，ｔ）で割り切れる、前記有限体Fｑ上定義された第２の２変数多項式λｙ（ｓ，ｔ）を生成する第２のステップと、
前記第３の生成手段が、前記有限体Fｑ上定義された、パラメータｓ，ｔに関する２つの２変数多項式ｕｘ（ｓ，ｔ）、ｖｘ（ｓ，ｔ）を、当該２つの２変数多項式の差分｛ｕｘ（ｓ，ｔ）−ｖｘ（ｓ，ｔ）｝が前記第１の２変数多項式λｘ（ｓ，ｔ）となるように生成する第３のステップと、
前記第４の生成手段が、前記有限体Fｑ上定義された、パラメータｓ，ｔに関する２つの２変数多項式ｕｙ（ｓ，ｔ）、ｖｙ（ｓ，ｔ）を、当該２つの２変数多項式の差分｛ｕｙ（ｓ，ｔ）−ｖｙ（ｓ，ｔ）｝が前記第２の２変数多項式λｙ（ｓ，ｔ）となるように生成する第４のステップと、
前記セクション生成手段が、前記第３のステップにおいて前記前記第３の生成手段により生成された２変数多項式ｕｘ（ｓ，ｔ）をｘ座標、前記第４のステップにおいて前記第４の生成手段により生成された２変数関数ｕｙ（ｓ，ｔ）をｙ座標とするセクションＤ１：（ｘ，ｙ，ｓ，ｔ）＝（ｕｘ（ｓ，ｔ），ｕｙ（ｓ，ｔ），ｓ，ｔ）と、前記第３のステップにおいて前記前記第３の生成手段により生成された２変数多項式ｖｘ（ｓ，ｔ）をｘ座標、前記第４のステップにおいて前記第４の生成手段により生成された２変数関数ｖｙ（ｓ，ｔ）をｙ座標とするセクションＤ２：（ｘ，ｙ，ｓ，ｔ）＝（ｖｘ（ｓ，ｔ），ｖｙ（ｓ，ｔ），ｓ，ｔ）を生成する第５のステップと、
前記３次元多様体生成手段が、前記セクションＤ１及び前記セクションＤ２を含む前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）の多項式を生成する第６のステップと、
を有することを特徴とする鍵生成方法。
【請求項５】
第１の生成手段と第２の生成手段と第３の生成手段と第４の生成手段と第５の生成手段とを備え、有限体Fｑならびにｘ座標、ｙ座標、パラメータｓ、及びパラメータｔで表された、署名検証用の公開鍵として用いられる前記有限体Fｑ上定義された３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）と、前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）内の曲面のうち、ｘ座標及びｙ座標がパラメータｓ及びｔの関数で表された、署名生成用の秘密鍵として用いられるセクションを生成する鍵生成装置の鍵生成方法であって、
前記第１の生成手段が、パラメータｓ、ｔに関する第１番目から第ｎ（ｎは正の整数）番目までのｎ（ｎは正の整数）個の前記有限体Fｑ上定義された２変数多項式ｕｘ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）と、パラメータｓ、ｔに関する第１番目から第ｎ番目までのｎ個の前記有限体Fｑ上定義された２変数多項式ｕｙ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）を生成する第１のステップと、
前記第２の生成手段が、前記第１のステップにおいて前記第１の生成手段により生成された第ｉ（１≦ｉ≦ｎ）番目の２変数多項式ｕｘ，ｉ（ｓ，ｔ）及びｕｙ，ｉ（ｓ，ｔ）をそれぞれｘ座標、ｙ座標とする第ｉ番目のセクションＤｉ：（ｘ，ｙ，ｓ，ｔ）＝（ｕｘ，ｉ（ｓ，ｔ）、ｕｙ，ｉ（ｓ，ｔ），ｓ，ｔ）（１≦ｉ≦ｎ）を生成することにより、第１番目から第ｎ番目までのｎ個のセクションＤｉ（１≦ｉ≦ｎ）を求める第２のステップと、
前記第３の生成手段が、前記第１のステップにおいて前記第１の生成手段により生成された第ｉ（１≦ｉ≦ｎ）番目の２変数多項式ｕｘ，ｉ（ｓ，ｔ）及びｕｙ，ｉ（ｓ，ｔ）を用いて、第ｉ番目のｘ因子（ｘ−ｕｘ，ｉ（ｓ，ｔ））及びｙ因子（ｙ−ｕｙ，ｉ（ｓ，ｔ））を生成することにより、第１番目から第ｎ番目までのｘ因子及びｙ因子を求める第３のステップと、
前記第４の生成手段が、前記第３のステップにおいて前記第３の生成手段により生成された第ｉ（１≦ｉ≦ｎ）番目のｘ因子及びｙ因子を左辺と右辺に振り分けて、左辺に振り分けられたｎ個のｘ因子及びｙ因子の積と、右辺に振り分けられたｎ個のｘ因子及びｙ因子の積とを等号で結ぶことにより得られる等式を生成する第４のステップと、
前記第５の生成手段が、前記第４のステップにおいて前記第４の生成手段により生成された等式を展開することにより、前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）の多項式を生成する第５のステップと、
を有することを特徴とする鍵生成方法。
【請求項６】
前記第１のステップは、
前記２変数多項式ｕｘ，ｉ（ｓ，ｔ）のパラメータｓについての次数の最大値ｈｘと、パラメータｔについての次数の最大値ｋｘを決定するステップと、
次数が最大値ｈｘ以下の変数ｓと次数が最大値ｋｘ以下の変数ｔとのうちの少なくとも１つを因子として有する複数の単項式と、ｓｈｘｔｋｘの項とを含む第ｉ番目の２変数多項式ｕｘ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）を生成するステップと、
前記２変数多項式ｕｙ，ｉ（ｓ，ｔ）の変数ｓについての次数の最大値ｈｙと、変数ｔについての次数の最大値ｋｙを決定するステップと、
次数が最大値ｈｙ以下の変数ｓと、次数が最大値ｋｙ以下の変数ｔとのうちの少なくとも１つを因子として有する複数の単項式と、ｓｈｙｔｋｙの項とを含む第ｉ番目の前記２変数多項式ｕｙ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）を生成するステップと、
を含むことを特徴とする請求項５記載の鍵生成装置。
【請求項７】
第１の生成手段と第２の生成手段と第３の生成手段と第４の生成手段とセクション生成手段と３次元多様体生成手段とを備え、有限体Fｑならびに署名検証用の公開鍵として用いられる、ｘ座標、ｙ座標、パラメータｓ、及びパラメータｔで表される前記有限体Fｑ上定義された３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）と、署名生成用の秘密鍵として用いられる前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）内の曲面のうち、ｘ座標及びｙ座標がパラメータｓ及びｔの関数で表されたセクションを生成する鍵生成装置としてコンピュータを機能させるための鍵生成プログラムであって、
前記第１の生成手段が、前記有限体Fｑ上定義された、パラメータｓ、ｔに関する第１の２変数多項式λｘ（ｓ，ｔ）を生成する第１のステップと、
前記第２の生成手段が、前記第１の２変数多項式λｘ（ｓ，ｔ）で割り切れる、前記有限体Fｑ上定義された第２の２変数多項式λｙ（ｓ，ｔ）を生成する第２のステップと、
前記第３の生成手段が、前記有限体Fｑ上定義された、パラメータｓ，ｔに関する２つの２変数多項式ｕｘ（ｓ，ｔ）、ｖｘ（ｓ，ｔ）を、当該２つの２変数多項式の差分｛ｕｘ（ｓ，ｔ）−ｖｘ（ｓ，ｔ）｝が前記第１の２変数多項式λｘ（ｓ，ｔ）となるように生成する第３のステップと、
前記第４の生成手段が、前記有限体Fｑ上定義された、パラメータｓ，ｔに関する２つの２変数多項式ｕｙ（ｓ，ｔ）、ｖｙ（ｓ，ｔ）を、当該２つの２変数多項式の差分｛ｕｙ（ｓ，ｔ）−ｖｙ（ｓ，ｔ）｝が前記第２の２変数多項式λｙ（ｓ，ｔ）となるように生成する第４のステップと、
前記セクション生成手段が、前記第３のステップにおいて前記前記第３の生成手段により生成された２変数多項式ｕｘ（ｓ，ｔ）をｘ座標、前記第４のステップにおいて前記第４の生成手段により生成された２変数関数ｕｙ（ｓ，ｔ）をｙ座標とするセクションＤ１：（ｘ，ｙ，ｓ，ｔ）＝（ｕｘ（ｓ，ｔ），ｕｙ（ｓ，ｔ），ｓ，ｔ）と、前記第３のステップにおいて前記前記第３の生成手段により生成された２変数多項式ｖｘ（ｓ，ｔ）をｘ座標、前記第４のステップにおいて前記第４の生成手段により生成された２変数関数ｖｙ（ｓ，ｔ）をｙ座標とするセクションＤ２：（ｘ，ｙ，ｓ，ｔ）＝（ｖｘ（ｓ，ｔ），ｖｙ（ｓ，ｔ），ｓ，ｔ）を生成する第５のステップと、
前記３次元多様体生成手段が、前記セクションＤ１及び前記セクションＤ２を含む前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）の多項式を生成する第６のステップと、
をコンピュータに実行させるための鍵生成プログラム。
【請求項８】
第１の生成手段と第２の生成手段と第３の生成手段と第４の生成手段と第５の生成手段とを備え、有限体Fｑならびにｘ座標、ｙ座標、パラメータｓ、及びパラメータｔで表された、署名検証用の公開鍵として用いられる前記有限体Fｑ上定義された３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）と、前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）内の曲面のうち、ｘ座標及びｙ座標がパラメータｓ及びｔの関数で表された、署名生成用の秘密鍵として用いられるセクションを生成する鍵生成装置としてコンピュータを機能させるための鍵生成プログラムであって、
前記第１の生成手段が、パラメータｓ、ｔに関する第１番目から第ｎ（ｎは正の整数）番目までのｎ（ｎは正の整数）個の前記有限体Fｑ上定義された２変数多項式ｕｘ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）と、パラメータｓ、ｔに関する第１番目から第ｎ番目までのｎ個の前記有限体Fｑ上定義された２変数多項式ｕｙ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）を生成する第１のステップと、
前記第２の生成手段が、前記第１のステップにおいて前記第１の生成手段により生成された第ｉ（１≦ｉ≦ｎ）番目の２変数多項式ｕｘ，ｉ（ｓ，ｔ）及びｕｙ，ｉ（ｓ，ｔ）をそれぞれｘ座標、ｙ座標とする第ｉ番目のセクションＤｉ：（ｘ，ｙ，ｓ，ｔ）＝（ｕｘ，ｉ（ｓ，ｔ）、ｕｙ，ｉ（ｓ，ｔ），ｓ，ｔ）（１≦ｉ≦ｎ）を生成することにより、第１番目から第ｎ番目までのｎ個のセクションＤｉ（１≦ｉ≦ｎ）を求める第２のステップと、
前記第３の生成手段が、前記第１のステップにおいて前記第１の生成手段により生成された第ｉ（１≦ｉ≦ｎ）番目の２変数多項式ｕｘ，ｉ（ｓ，ｔ）及びｕｙ，ｉ（ｓ，ｔ）を用いて、第ｉ番目のｘ因子（ｘ−ｕｘ，ｉ（ｓ，ｔ））及びｙ因子（ｙ−ｕｙ，ｉ（ｓ，ｔ））を生成することにより、第１番目から第ｎ番目までのｘ因子及びｙ因子を求める第３のステップと、
前記第４の生成手段が、前記第３のステップにおいて前記第３の生成手段により生成された第ｉ（１≦ｉ≦ｎ）番目のｘ因子及びｙ因子を左辺と右辺に振り分けて、左辺に振り分けられたｎ個のｘ因子及びｙ因子の積と、右辺に振り分けられたｎ個のｘ因子及びｙ因子の積とを等号で結ぶことにより得られる等式を生成する第４のステップと、
前記第５の生成手段が、前記第４のステップにおいて前記第４の生成手段により生成された等式を展開することにより、前記３次元多様体Ａ（ｘ，ｙ，ｓ，ｔ）の多項式を生成する第５のステップと、
をコンピュータに実行させるための鍵生成プログラム。
【請求項９】
前記第１のステップは、
前記２変数多項式ｕｘ，ｉ（ｓ，ｔ）のパラメータｓについての次数の最大値ｈｘと、パラメータｔについての次数の最大値ｋｘを決定するステップと、
次数が最大値ｈｘ以下の変数ｓと次数が最大値ｋｘ以下の変数ｔとのうちの少なくとも１つを因子として有する複数の単項式と、ｓｈｘｔｋｘの項とを含む第ｉ番目の２変数多項式ｕｘ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）を生成するステップと、
前記２変数多項式ｕｙ，ｉ（ｓ，ｔ）の変数ｓについての次数の最大値ｈｙと、変数ｔについての次数の最大値ｋｙを決定するステップと、
次数が最大値ｈｙ以下の変数ｓと次数が最大値ｋｙ以下の変数ｔとのうちの少なくとも１つを因子として有する複数の単項式と、ｓｈｙｔｋｙの項とを含む第ｉ番目の前記２変数多項式ｕｙ，ｉ（ｓ，ｔ）（ｉ：１≦ｉ≦ｎ）を生成するステップと、
を含むことを特徴とする請求項８記載の鍵生成プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２０１０−２４４０７０（Ｐ２０１０−２４４０７０Ａ）
【公開日】平成２２年１０月２８日（２０１０．１０．２８）
【国際特許分類】
【出願番号】特願２０１０−１４６２５９（Ｐ２０１０−１４６２５９）
【出願日】平成２２年６月２８日（２０１０．６．２８）
【分割の表示】特願２００５−２１４９９４（Ｐ２００５−２１４９９４）の分割
【原出願日】平成１７年７月２５日（２００５．７．２５）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
【公開日】平成２２年１０月２８日（２０１０．１０．２８）
【国際特許分類】
【出願日】平成２２年６月２８日（２０１０．６．２８）
【分割の表示】特願２００５−２１４９９４（Ｐ２００５−２１４９９４）の分割
【原出願日】平成１７年７月２５日（２００５．７．２５）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
[ Back to top ]