説明

電子署名システム、鍵合意システム、電子署名方法および鍵合意方法

【課題】Waters偽造不可署名と同程度の効率を有する強偽造不可署名方式のスタンダードモデルおよび安全性と効率性とを有する三者間SAKAPのスタンダードモデルを提供する。
【解決手段】電子署名方式が、送信者が自分自身のlong-term private keyを知っているという事実を受信者が送信文書から検証することができるという基本的な属性を含む強偽造不可(定理1)であり、かつ、送信者の認証機能付き鍵合意プロトコルSAKAPとして、キー生成、メッセージ生成、ベリフィケーション、キー・アグリーメントの4つのフェーズを有し、そのうち、前3つの各フェーズが、前記電子署名方式により構成され、かつ、如何なる送信者もshort-term secretを漏洩せず(定理2)、かつ、Known Key Security(定理3)、Perfect Forward Secrecy(定理4)、Key Compromise Impersonation Secure(定理5)の属性を満たす仕組みを実現する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、電子署名システム、鍵合意システム、電子署名方法および鍵合意方法に関する。
【背景技術】
【0002】
送信者認証機能付き鍵合意プロトコル(SAKAP:Sender Authenticated Key Agreement Protocols)は認証機能付きの鍵合意を実施するプロトコルの一種である。SAKAPでは、送信者がlong-termのprivate keyを持っているかどうかを、第三者によって検証することができる。SAKAPは、非特許文献1の“On one-pass authenticated key establishment schemes”,(Workshop Record of Workshop on Selected Areas in Cryptography(SAC‘95)、pp.2-8,1995)において、K.Nybergによって最初に提案されたが、該非特許文献1にて提案されたプロトコルは、鍵合意として望ましい要件であるForward Secrecy(FS:フォワード秘匿性)を満たしていなかった。
【0003】
その後、Y.J.Choie-E.Jeong-E.LeeおよびC.Popescuは、それぞれ、非特許文献2の“Efficient identity-based authenticated key agreement protocol from pairings”(Appl.Math.Comput.,vol.162,pp.179-188,2005)、および、非特許文献3の“A secure key agreement protocol using elliptic curves”,Int.J.Comput.Appl.vol.27,pp.147-152,2005”において、Perfect FS(完全フォワード秘匿性)を満たす二者間モデルを提案した。
【0004】
また、F.Zhang-S.Liu-K.Kim、D.NallaおよびK.Shimは、それぞれ、非特許文献4の““ID-based one round authenticated tripartite key agreement protocol with pairings”(2003 IEEE International Symposium on Information Theory,Yokohama,JAPAN,2003)、非特許文献5の“ID-based tripartite key agreement with signatures”(Cryptology ePrint Archive,available at http://eprint.iacr.org/2003/144/)、および、非特許文献6の“Cryptanalysis of ID-based tripartite authenticated key agreement protocols”(Cryptology ePrint Archive,available at http://eprint.iacr.org/2003/115/)において、三者間IDベースSAKAPを提案した。
【0005】
また、X.Du-Y.Wang−J.Ge- Y.Wangは、非特許文献7の“An ID-based authenticated two round multi-party key agreement”(Cryptology ePrint Archive,available at http://eprint.iacr.org/2003/247/)および非特許文献8の“An improved ID-based authenticated group key agreement scheme”,(Cryptology ePrint Archive,available at http://eprint.iacr.org/2003/260/)において、多者間でのプロトコルを提案した。さらに、SAKAPの最初のスタンダードモデル(すなわち、ランダムオラクルを仮定せずに安全性を証明できるモデル)が、本発明者により、非特許文献9の“Sender authenticated key agreements without random oracles”(Proc. ICCIT 2007,IEEE CS Press,pp.2156-2162,2007)において提案された。
【0006】
SAKAPおよび電子署名方式について考えてみると、多くの署名方式は、SAKAPの構成に利用できそうである。その理由の一つとして、これまでに提案されたSAKAPが、基本的に、非特許文献10のW.Diffie-M.E.Hellmanによる“New directions in cryptography”(IEEE Trans. Inf. Theory,vo1.22,pp.644-654,1976)に記載のDiffie-Hellman(DH)鍵合意(あるいは、非特許文献11のA.Jouxによる“A one round protocol for tripartite Diffie-Hallman”(in Algorithmic Number Theory,ed.W.Bosma,LNCS1838,pp,385-393,2000/J.Cryptology,vol.17,pp.263-276,2004)に記載のJoux鍵合意)をベースに構成されているのに対して、署名方式は、gのような成分をフェーズに含んでいることが挙げられる。ここで、g は十分大きな素数p を位数とする乗法巡回群の生成元であり、r∈Z:={1,2,・・・,p-1}は乱数である。
【0007】
その他の理由として、署名方式の各フェーズは、以下のように、SAKAPのフェーズに対応することが挙げられる。署名方式は、3つのフェーズ(KeyGen:キー生成,Sign:サイン,Verify:ベリファイ)から構成され、SAKAPは、4つのフェーズ(Key Generation:キー生成,Message Generation:メッセージ生成,Verification:ベリフィケーション,Key Agreement:キー・アグリーメント(鍵合意))から構成されるものとする。そのとき、署名方式の各フェーズは、それぞれ、SAKAPのフェーズKey Generation,Message Generation,Verificationに対応する。また、DH鍵合意をベースとしていない鍵合意プロトコルは、一般に、計算量的なアドバンテージを有するものの、FSを満たしていない。よって、本発明においては、前記被特許文献10に記載のDH鍵合意ベースのSAKAPに応用可能な電子署名方式を対象とすることとする。
【0008】
SAKAPとしての署名が、例えば適応的選択文書攻撃に対する(弱)存在的偽造不可(偽造不可:(weakly) Existential Unforgeable under an adaptive Chosen Message Attack)ではあるが、強偽造不可(strongly Existential Unforgeable under an adaptive Chosen Message Attack:適応的選択文書攻撃に対する強存在的偽造不可)ではないと仮定する。この場合、もし、SAKAPのある正当な合意文書が存在すれば、攻撃者は、valid(正当)な別の合意文書を偽造することができる。(例としては、非特許文献12のB.Watersによる“Efficient identity-based encryption without random oracles”(Proc. Eurocrypt 2005,LNCS 3027,pp.223-238,2005)を参照のこと。)それゆえ、SAKAPに応用可能な署名は、少なくとも、強偽造不可の安全性が必要である。
【0009】
ランダムオラクルは、理想的なハッシュ関数と考えられるが、MD5(Message Digest Algorithm 5)やSHA−1(Secure Hash Algorithm-1)のような一般に利用されているハッシュ関数を含んでいない。ランダムオラクルを仮定しない署名(またはIDベース暗号)方式の研究は、公開鍵基盤における最重要テーマの一つである。よって、本発明が対象とする電子署名方式およびSAKAPつまり鍵合意方式は、スタンダードモデル(ランダムオラクル仮定を用いない)のみとする。
【0010】
現在、効率的である強偽造不可安全な署名のスタンダードモデルが、非特許文献13のR.Gennaro,S.Halevi and T.Rabinによる“Secure hash-and-sign signatures without the random oracle”(Proc.Eurocrypt 1999,LNCS 1592, pp.123-139,1999)、および、非特許文献14のR.Cramer and V.Shoupによる“Signature schemes based on the strong RSA assumption”(ACM TISSEC,vol.3,pp.161-185,2000./Proc. 6th ACM CCS,1999)において提案されている。しかし、これらの署名方式から構成されるSAKAPは、DH鍵合意をベースとしていないものと思われる。FS(フォワード秘匿性)の観点から、本発明においては、前記非特許文献13,14の各方式についてこれ以上論じないことにする。
【0011】
非特許文献15のD.Boneh and X.Boyenによる“Short signatures without random oracles”(Proc.Eurocrypt 2004,LNCS 3027,pp.56-73,2004)、非特許文献16のF.Zhang,X.Chen,W.Susilo and Y,Muによる“A new short signature scheme without random oracles from bilinear pairings”(Proc.Vietcrypt 2006, LNCS 4341,pp.67-80,2006)、非特許文献17のJ.Camenisch and A.Lysyanskayaによる“Signature schemes and anonymous credentials from bilinear maps”(Proc.Crypto 2004,LNCS 3152, pp.56-72,2004)において提案された署名方式のスタンダードモデルは、それぞれ強DH仮定、square root仮定、LRSW仮定のもと、強偽造不可安全である。
【0012】
しかし、前記非特許文献15,16,17の三方式においては、private keyは、(1つではなく、)2つのパラメータにより定義されるので、これらの方式から構成されるSAKAPは、一部の結託攻撃に対する耐性がない。詳細は後述するが、かくのごとき攻撃に対する耐性を持つ署名は、非特許文献18のT.Okamotoにより“Efficient blind and partially blind signatures without random oracles”(Proc. TCC 2006,LNCS 3876, pp.80-99,2006)において提案されているOkamoto方式、および、非特許文献19のD.Boneh,E,Shen and B.Watersにより “Strongly unforgeable signatures based on computational Diffie-Hallman”(Proc. PKC 2006,LNCS 3958, pp.229-240,2006)において提案されているBSW方式のみである。BSW方式ベースのSAKAPは、Okamoto方式ベースのものよりも効率が良い。しかしながら、BSW方式は、B.Watersにより前記非特許文献12にて提案された偽造不可方式(Waters方式)から構成されたものであるにも関わらず、BSW方式ベースのSAKAPは、Waters方式ベースのものよりも効率が悪いという問題がある。署名システムと認証機能付き鍵合意システムを考えるとき、各entityに関する鍵合意の成分が署名文書にのみに含まれている場合、この鍵合意方式は前記結託攻撃に対する耐性を持つことができないことに注意せよ。
【非特許文献1】K.Nyberg,“On one-pass authenticated key establishment schemes”,Workshop Record of Workshop on Selected Areas in Cryptography(SAC‘95),pp.2-8,1995
【非特許文献2】Y.J.Choie,E.Jeong and E.Lee,“Efficient identity-based authenticated key agreement protocol from pairings”,Appl.Math.Comput.,vol.162,pp.179-188,2005
【非特許文献3】C.Popescu,“A secure key agreement protocol using elliptic curves”,Int.J.Comput.Appl.vol.27,pp.147-152,2005
【非特許文献4】F.Zhang,S.Liu and K.Kim,“ID-based one round authenticated tripartite key agreement protocol with pairings”,2003 IEEE International Symposium onInformation Theory,Yokohama,JAPAN,2003
【非特許文献5】D.Nalla,“ID-based tripartite key agreement with signatures”,Cryptology ePrint Archive,available at http://eprint.iacr.org/2003/144/
【非特許文献6】K.Shim,“Cryptanalysis of ID-based tripartite authenticated key agreement protocols”,Cryptology ePrint Archive,available athttp://eprint.iacr.org/2003/115/
【非特許文献7】X.Du,Y.Wang,J.Ge and Y.Wang,“An ID-based authenticated two round multi-party key agreement”,Cryptology ePrint Archive,available athttp://eprint.iacr.org/2003/247/
【非特許文献8】X.Du,Y.Wang,J.Ge and Y.Wang,“An improved ID-based authenticated group key agreement scheme”,Cryptology ePrint Archive,available athttp://eprint.iacr.org/2003/260/
【非特許文献9】C.Sato,T.Okamoto and E.Okamoto,“Sender authenticated key agreements without random oracles”,Proc. ICCIT 2007,IEEE CS Press,pp.2156-2162,2007
【非特許文献10】W.Diffie and M.E.Hellman,“New directions in cryptography”, IEEETrans. Inf. Theory,vo1.22,pp.644-654,1976
【非特許文献11】A.Joux,“A one round protocol for tripartite Diffie-Hallman”,in Algorithmic Number Theory,ed.W.Bosma,LNCS1838,pp,385-393,2000/J.Cryptology,vol.17,pp.263-276,2004
【非特許文献12】B.Waters,“Efficient identity-based encryption without random oracles”,Proc.Eurocrypt 2005,LNCS 3027,pp.223-238,2005
【非特許文献13】R.Gennaro,S.Halevi and T.Rabin,“Secure hash-and-sign signatures without the random oracle”,Proc.Eurocrypt1999,LNCS 1592,pp.123-139,1999
【非特許文献14】R.Cramer and V.Shoup,“Signature schemes based on the strong RSA assumption”, ACM TISSEC,vol.3,pp.161-185,2000./Proc. 6th ACMCCS,1999
【非特許文献15】D.Boneh and X.Boyen,“Short signatures without random oracles”,Proc.Eurocrypt 2004,LNCS 3027,pp.56-73,2004
【非特許文献16】F.Zhang,X.Chen,W.Susilo and Y,Mu,“A new short signature scheme without random oracles from bilinear pairings”,Proc.Vietcrypt 2006, LNCS4341,pp.67-80,2006
【非特許文献17】J.Camenisch and A.Lysyanskaya,“Signature schemes and anonymous credentials from bilinear maps”,Proc. Crypto 2004,LNCS 3152, pp.56-72,2004
【非特許文献18】T.Okamoto,“Efficient blind and partially blind signatures without random oracles”,Proc. TCC 2006,LNCS 3876,pp.80-99,2006
【非特許文献19】D.Boneh,E,Shen and B.Waters,“Strongly unforgeable signatures based on computational Diffie-Hallman”,Proc. PKC 2006,LNCS 3958, pp.229-240,2006
【発明の開示】
【発明が解決しようとする課題】
【0013】
本発明は、前述したような従来技術の問題に鑑みてなされたものであり、本発明においては、Waters署名方式における偽造不可署名と同程度の効率を有する、強偽造不可署名方式のスタンダードモデルを提供することを目的とする。さらに、該強偽造不可署名方式をベースに、三者間SAKAPのスタンダードモデルを提供することを目的とする。
【課題を解決するための手段】
【0014】
前述の課題を解決するため、本発明による電子署名システム、鍵合意システム、電子署名方法および鍵合意方法は、次のような特徴的な構成を採用している。
【0015】
(1)パブリックキー(Public Key)PKとプライベートキー(Private Key)SKとのペアを出力するキー生成(KeyGen)フェーズと、該キー生成フェーズが出力する前記プライベートキーSKおよび署名文書Mを入力として、署名σを返すサイン(Sign)フェーズと、前記キー生成フェーズが出力する前記パブリックキーPKおよび前記署名文書Mと前記サインフェーズが出力する前記署名σとの組合せ(M、σ)を入力として、valid(正当)またはinvalid(不当)を返すベリファイ(Verify)フェーズとの各フェーズの演算部を備えた電子署名システムにおいて、
G,G,Gが素数p の位数を持つ乗法巡回群であり(一般的に、G,Gは、加法巡回群として定義されるが、表記の簡略化のため、乗法巡回群とする)、gはGのランダムな生成元であり、f:G→Gが、次の式(A1)を満たす一方向性同型写像であり、e: G×G→Gが、次の式(A2)を満たす双線形写像とした場合、
【数1】

【数2】

式(A3)に示す生成元g,gおよび乱数x,r(i=1,2,…,q)となる式(A4)に示す入力に対し、式(A5)に示すようなあるrとなる式(A6)の計算を、
【数3】

【数4】

【数5】

【数6】

攻撃者が、時間t以内で、高々、あらかじめ定めた定数εの確率でしか行うことができない電子署名システム。
【発明の効果】
【0016】
本発明の電子署名システム、鍵合意システム、電子署名方法および鍵合意方法によれば、以下のような効果を得ることができる。
【0017】
つまり、本発明においては、偽造不可署名であるWaters署名方式と同程度の効率を有する強偽造不可の電子署名方式のスタンダードモデルを実現している。さらに、本発明による三者間SAKAPのスタンダードモデルのプロトコルは、鍵合意方式としての安全性を確保するとともに、Waters署名方式から構成されるSAKAPと同程度の効率性を実現している。この結果、本発明の対象とする分野における安全性を満たすプロトコルのスタンダードモデルとして最も効率が良いモデルを実現することができる。
【発明を実施するための最良の形態】
【0018】
以下、本発明による電子署名システム、鍵合意システム、電子署名方法および鍵合意方法の好適な実施例について説明する。なお、以下の説明においては、本発明による電子署名方法および鍵合意方法の一例について説明するが、該電子署名方法および鍵合意方法を、例えば演算部(CPUを含む)を備えるコンピュータシステムとして構築した電子署名システムおよび鍵合意システムとして実現することも、或いはその電子署名方法および鍵合意方法を、コンピュータにより実行可能なプログラム(電子署名プログラムおよび鍵合意プログラム)として実現することも、もちろん可能であることは言うまでもない。
【0019】
(本発明の特徴)
本発明の実施形態の説明に先立って、本発明の特徴についてまず説明する。本発明は、送信者認証機能付き鍵合意方式に利用可能な電子署名方式を実現している。本発明による電子署名方式は、さらに、送信者がlong-termのprivate keyを持っているかどうかを、第三者によって検証することができる認証機能を有する鍵合意方式を構成している。すなわち、本電子署名方式においては、Waters署名(偽造不可安全)と同程度の効率性を持つ強偽造不可(strongly Existential Unforgeable under an adaptive Chosen Message Attack:適応的選択文書攻撃に対する強存在的偽造不可)安全な署名方式のスタンダードモデルを実現している。該電子署名方式に基づいて、さらに、三者間で行う送信者認証機能付き鍵合意方式に関するSAKAPプロトコルのスタンダードモデルを構成する。該プロトコルは、以下に詳細に説明するように、署名ベースのスタンダードモデルとして、本発明の対象分野において扱う安全性(強偽造不可,Private KeyのKnowledge(プライベートキー知識),Known Key Security(既知キー安全性),Perfect Forward Secrecy(完全フォワード秘匿性),Key Compromise Impersonation Secure(キー漏洩なりすなし安全性))の各要件を満たすプロトコルの中で、最も効率が良い。
【0020】
つまり、送信者認証機能付き鍵合意プロトコル(SAKAP:Sender Authenticated Key Agreement Protocols)の最も基本的な性質は、送信者が自分自身のlong-term private keyを知っているという事実を、受信者が、送信文書から検証することができることである。本発明による電子署名方式の安全性(強偽造不可、定理1)は、この基本的な属性を含んでいる。また、本発明による電子署名方式に基づく送信者認証機能付き鍵合意プロトコルSAKAPは、いかなる送信者もshort-term secretを漏洩しない(定理2)。加えて、本プロトコルは、ほとんどの鍵合意プロトコルで議論されるKnown Key Security(定理3)、Perfect Forward Secrecy(定理4)、Key Compromise Impersonation Secure(定理5)の属性を満たしている。
【0021】
以下に、本発明による実施形態の詳細について、次の順番に説明する。第1番目の「準備段階」の項において、本発明による電子署名方式および送信者認証機能付き鍵合意プロトコルSAKAPつまり鍵合意方式の構成および安全性証明のための準備として各種の定義を行う。次の第2番目の「本発明による実施形態」の項において、本発明の一例である電子署名方式を説明し、さらに、該電子署名方式をベースにした送信者認証機能付き鍵合意プロトコルSAKAPのプロトコル構成つまり鍵合意方式構成の一例を説明する。しかる後、第3番目の「安全性および効率性の証明」の項において、本発明に係わるいくつかの定理を設定して、それらの定理の証明を行った後、既存技術との比較を行うことにより、本発明における電子署名方式、送信者認証機能付き鍵合意プロトコルSAKAP(鍵合意方式)が、強偽造不可安全を満たす安全性および効率性を十分に備えていることを説明し、最後の第4番目の「結論」の項において本発明のまとめを説明する。
【0022】
1.準備段階
ここでは、本発明による実施形態の説明に用いる一方向性同型写像(One Way Isomorphism)、双線形写像(Bilinear Map)、Computational Diffie-Hellman(CDH)問題に関連した2つの仮定、署名方式、強偽造不可、Known Key Security、Perfect Forward SecrecyおよびKey Compromise Impersonation Secureをそれぞれ定義する。
【0023】
1.1.一方向性同型写像および双線形写像
一方向性同型写像および双線形写像に関する以下の定義は、T. Saitoらによる“Candidate one-way functions on non-supersingular elliptic curves”(IEICE Trans. Fundamentals, vol.E89, pp.144-150, 2006)、および、D.Boneh and M. Franklinによる“Identity-based encryption from the Weil pairing”(Proc. Crypto 2001, LNCS 2139,pp.213-229, 2001)に従っている。
(1)G,G,Gは素数p の位数を持つ乗法巡回群である(一般的に、G,Gは、加法巡回群として定義されるが、表記の簡略化のため、乗法巡回群とする);
(2)gはGの生成元である;
(3)f:G→Gは一方向性同型写像であり、次の式(1)を満たす;
【0024】
【数67】

【0025】
(4)e : G×G→Gは双線形写像であり、以下の属性(a)〜(c)を持つ:
【0026】
(a)双線形性: 任意のu ∈ G、v ∈ Gと任意のa,b ∈ Zに対し、次の式(2)を満たす。
【0027】
【数68】

【0028】
(b)非退化:次の式(3)を満たす。
【0029】
【数69】

【0030】
(c)計算可能:任意のu ∈ G と任意のv ∈ Gに対し,e(u,v)を計算する効率的な計算アルゴリズムが存在する。
【0031】
ここで、G,Gは、一般的に、一方向性同型写像f や双線形写像e 上において加法巡回群として定義されるが、以下の説明においては、表記の簡略化のため、乗法巡回群とする。
【0032】
1.2.CDH問題に関連した2つの仮定
以下の定義は、前記非特許文献9、および、C.Satoらによる“Strongly unforgeable ID-based signatures without random oracles”(Cryptology ePrint Archive,available at http://eprint.iacr.org/2008/095/)に準拠して定めている。
【0033】
まず、本実施形態における電子署名方式およびSAKAPプロトコルのベースとなる、CDH問題に関連のある仮定1および仮定2について説明する。
【0034】
アドバンテージεおよび時間t以内で実行する任意の攻撃者Aに対し、次の式(4)が成り立つならば、G上の(t,ε)−CDH仮定は成り立つという。ここで、式(4)の確率Prは、ランダムな生成元gG、乱数a,b ∈およびAのランダムなビット列から選ばれている。
【0035】
【数70】

【0036】
第一の問題は、以下のように与えられる。
つまり、第一の問題は、式(5)に示すようなランダムな生成元gG,gGおよび乱数x,r,r,…,rZ*となる式(6)に示す入力に対し、式(7)に示すようなあるrとなる式(8)を計算せよというものである。ここで、式(8)に示すように、第2項のgの指数{x+1/r}は、{x +(1/r)}を意味していることに注意を要する。
【0037】
【数71】

【0038】
【数72】

【0039】
【数73】

【0040】
【数74】

【0041】
もし、式(9)が成り立つならば、アルゴリズムA は、第一の問題を解くためのあらかじめ定めた定数εのアドバンテージを持っているという。ここで、式(9)の確率Pは、式(5)、式(7)およびAのランダムなビット列から選ばれている。
【0042】
【数75】

【0043】
ここで、仮定1を次のように設定する。
(仮定1)攻撃者A が、時間t以内で、第一の問題を解くアドバンテージを高々あらかじめ定めた確率εしか持たないとき、(q,t,ε)−仮定1は成り立つという。
【0044】
なお、ランダムな生成元gGに対し、一方向性同型写像f: G→Gをg := f(g) ∈ G で定義するとき、生成元gはランダムではないことに注意することを要する。
【0045】
次の第二の問題は、以下のように与えられる。
つまり、第二の問題は、式(10)に示すようなランダムな生成元gG,gG,乱数r,r,rZ*およびR∈Gとなる式(11)に示す入力に対し、式(12)に示すようなR となるならば1を出力し、それ以外のときは0を出力せよというものである。
【0046】
【数76】

【0047】
【数77】

【0048】
【数78】

【0049】
もし、式(13)が成り立つならば、アルゴリズムA は、第二の問題を解くためのあらかじめ定めた定数εのアドバンテージを持っているという。ここで、式(13)の確率Pは、式(10)およびAのランダムなビット列から選ばれている。
【0050】
【数79】

【0051】
ここで、仮定2を次のように設定する。
(仮定2)攻撃者A が、時間t以内で、第二の問題を解くアドバンテージを高々あらかじめ定めた確率εしか持たないとき、(t,ε)−仮定2は成り立つという。
【0052】
なお、前述のように、ランダムな生成元gGに対し、一方向性同型写像f : G→Gをg :=f(g) ∈ G で定義するとき、生成元gはランダムではないことに注意することを要する。
【0053】
この仮定2は、R∈Gを除いた式(11)の成分から、アルゴリズムAが式(14)に示すについての如何なる部分情報も得ることができないということを意味している。
【0054】
【数80】

【0055】
1.3.電子署名方式
ここでの電子署名方式の定義は、前記非特許文献15および前記非特許文献19に記載された内容に準拠している。
【0056】
本電子署名方式は、次の3つのフェーズ(KeyGen,Sign,Verify)から以下のように構成される。
【0057】
(a)キー生成(KeyGen)フェーズ:
ランダムなkeyペア(PK,SK)つまりPublic key PK,Private Key SKのペアを出力する。
【0058】
(b)サイン(Sign)フェーズ:
Private Key SKおよび(ある集合μ内の)署名文書Mを入力として、署名σを返す。
【0059】
(c)ベリファイ(Verify)フェーズ:
Public key PKおよび署名文書、署名の組合せ(M、σ)を入力として、valid(正当)またはinvalid(不当)を返す。
【0060】
つまり、本電子署名方式においては、次の式(15)を満たすとき、Correct(正常)またはConsistent(一致)と呼ばれる。
【0061】
【数81】

【0062】
1.4.強偽造不可
ここでの強偽造不可の定義は、前記非特許文献15および前記非特許文献19の記載内容に従っている。
【0063】
ここで、本発明においては、強偽造不可を定義するために、以下のような挑戦者B と攻撃者A によるゲームを考える。
【0064】
(1)Setup:
挑戦者B は、KeyGenフェーズを実行する。Public key PKとprivate key SKとを生成し、Public key PKを攻撃者Aへ与える。
【0065】
(2)Signature Queries:
Signature queries M,M,…,Mが攻撃者Aから発行される。各query Mに対し、挑戦者Bは、Signを実行し、各query Mの署名σを生成し、σを攻撃者Aへ送信する。なお、各query Mは、M,M,…,Mi−1についての返答を受け取った後、適応的に質問して良い。
【0066】
(3)Output:
最後に、攻撃者Aは組(M,σ)を出力する。ここで、query Mの署名σは、Verifyにおける署名文書Mのvalidな署名であり、(M,σ)はQueryフェーズにおける(M,σ)ではないとする。このとき、攻撃者Aは強偽造不可ゲームに勝ったという。
【0067】
ここで、AdvSigAを、挑戦者B と攻撃者A によるコイントスを用いた際に、攻撃者A が該ゲームに勝つ確率とする。
【0068】
つまり、定義1として次を定義する。
(定義1)攻撃者A が署名方式を(q,t,ε)で破るとは、時間t以内に、攻撃者Aが高々q回のSignature QueriesおよびAdvSig Aが少なくともεであることと定義する。署名方式が、適応的選択文書攻撃に対する(q,t,ε)−強存在的偽造不可(強偽造不可)であるとは、強偽造不可ゲームを(q,t,ε)で破る攻撃者A がいないことと定義する。
【0069】
1.5.鍵合意の安全性
以下の定義は、前記非特許文献9の記載内容に準拠している。次に定義されるKnown Key Security(KKS:既知キー安全性)、Perfect Forward Secrecy(PFS:完全フォワード秘匿性)およびKey Compromise Impersonation Secure(KCIS:キー漏洩なりすまし安全性)は、鍵合意についてのほとんどのプロトコルで解析される安全性である。
【0070】
(1)KKS:
たとえ、攻撃者がある以前のsessionにおけるagreement keyが分かっても、その攻撃者は他のsessionにおけるagreement keyを知ることができない。
【0071】
(2)PFS:
たとえ、すべてのprivate keyが漏洩しても、以前のsessionにおけるagreement keyの秘密には影響がない。
【0072】
(3)KCIS:
あるentityのlong-term private keyが漏洩しても、攻撃者は他のentityになりすますことはできない。
【0073】
2.本発明による実施形態
次に、本発明による電子署名方式および送信者認証機能付き鍵合意プロトコルSAKAPのプロトコル構成(鍵合意方式)の一例について説明する。
【0074】
2.1.本実施形態における電子署名方式
まず、本実施形態における電子署名方式の一例について説明する。本電子署名方式は、前述に定義したような(KeyGen,Sign,Verify)の3つのフェーズから構成される。
【0075】
ここで、式(16)はshared informationである。差し当たり、署名文書Mを式(17)の要素と仮定するが、式(18)に示すような衝突耐性を持つハッシュ関数Hを使って、領域を式(19)のように拡張することもできる。
【0076】
【数82】

【0077】
【数83】

【0078】
【数84】

【0079】
【数85】

【0080】
(a)キー生成(KeyGen)フェーズ:
Public keyは、以下のように生成される。ランダムな生成元gGを選び、次の式(20)とおく。式(21)のsecret αから、式(22)に示すprivate key SKを生成し、式(23)を計算する。
【0081】
【数86】

【0082】
【数87】

【0083】
【数88】

【0084】
【数89】

【0085】
つまり、次の式(24)、式(25)を計算する。
【0086】
【数90】

【0087】
【数91】

【0088】
加えて、アルゴリズムは、次の式(26)に示すランダムな値u′およびランダムなn-length vector Uを選択する。ここで生成されるpublic key PKとprivate key SKとは、それぞれ、式(27)となる。
【0089】
【数92】

【0090】
【数93】

【0091】
(b)サイン(Sign)フェーズ:
M をnビットの署名文書とし、式(28)に示すmを、Mの(左から)j 番目のビットとする。署名文書Mの署名σを、乱数r ∈ Z*を使って、次の式(29)とする。
【0092】
【数94】

【0093】
【数95】

【0094】
(c)ベリファイ(Verify)フェーズ:
署名はpublic key PK、署名文書Mおよび署名σ=(σ,σ)を使い、次の式(30)の等式が成り立つかどうかを検証する。式(30)の等式が成り立つとき、valid(正当)を出力し、それ以外のときinvalid(不当)を出力する。
【0095】
【数96】

【0096】
2.2.本実施形態におけるSAKAP(鍵合意方式)
次に、本実施形態における送信者認証機能付き鍵合意プロトコル(SAKAP:Sender
Authenticated Key Agreement Protocols)つまり鍵合意方式の一例について説明する。本SAKAPは、前述の2.1項において説明した電子署名方式から構成され、プロトコルは(Key Generation,Message Generation,Verification,Key Agreement)の4つのフェーズから構成される。
【0097】
ランダムな生成元gGを選び、式(31)とおく。加えて、アルゴリズムは、式(32)に示すようなランダムな値u′およびランダムなn-length vector Uを選択する。ここで、式(33)をshared informationとし、A,B,Cをプロトコルのentityとする。
【0098】
【数97】

【0099】
【数98】

【0100】
【数99】

【0101】
(a)キー生成(Key Generation)フェーズ:
entity A(エンティティA)は、secret a∈Zから式(34)に示す(long-term)private key SKを生成し、(long-term)public keyとして式(35)に示すPKを計算する。
【0102】
【数100】

【0103】
【数101】

【0104】
つまり、次の式(36)、式(37)を計算する。
【0105】
【数102】

【0106】
【数103】

【0107】
ここで、PKは、ある第三者信頼機関(TTP:Trusted Third Party)によって認証される。同様に、entity Bおよびentity Cについても、それぞれ、(SK,PK)および(SK,PK)を計算する。entity A,B,Cそれぞれのprivate key SKおよびpublic key PKの生成結果をまとめて表1に示す。
【0108】
【表1】

【0109】
(b)メッセージ生成(Message Generation)フェーズ:
差し当たり、署名文書Mを式(38)の要素と仮定するが、式(39)に示すような衝突耐性を持つハッシュ関数Hを使って、領域を式(40)のように拡張することもできる。
【0110】
【数104】

【0111】
【数105】

【0112】
【数106】

【0113】
entity
A(エンティティA)について考える。entity Aの文書Mをnビット署名文書とし、式(41)に示すmA,jをMの(左から)j番目のビットとする。Aは、short-term secret rZから、次の式(42)のように合意文書を生成する。
【0114】
【数107】

【0115】
【数108】

【0116】
entity Aは、生成した(A,A)をentity Bとentity Cへ送信する。同様に、entity Bは、生成した(B,B)をentity Cとentity Aへ、entity Cは、生成した(C,C)をentity Aとentity Bへ送信する。entity A,B,Cそれぞれが生成し、他のentityへ送信した合意文書の生成結果をまとめて表2に示す。ここで、各entityの合意文書は、前述の2.1.項において説明した電子署名方式の署名に対応することに注意を要する。
【0117】
【表2】

【0118】
(c)ベリフィケーション(Verification)フェーズ:
entity Aは、entity Bとentity Cとからそれぞれ受け取った合意文書(B,B)と合意文書(C,C)とを使って、次の式(43)が成り立つかどうかを検証する。
【0119】
【数109】

【0120】
式(43)に示す2つの等式が成り立つとき、valid(正当)を出力し、それ以外の場合、invalid(不当)を出力する。entity Bおよびentity CにおけるVerificationもentity Aの場合と同様である。各entity A,B,Cそれぞれにおける検証内容をまとめて表3に示す。
【0121】
【表3】

【0122】
(d)キー・アグリーメント(Key Agreement:鍵合意)フェーズ:
entity Aは、r,B,Cから、次の式(44)によりagreement key Zを計算する。同様に、entity Bおよびentity Cも、それぞれZとZを計算する。各entity A,B,Cそれぞれにおけるagreement keyをまとめて表4に示す。
【0123】
【数110】

【0124】
【表4】

【0125】
したがって、entity A,B,Cの間の三者間agreement keyは、次の式(45)となる。
【0126】
【数111】

【0127】
3.安全性および効率性の証明
次に、2項にて説明した本実施形態における電子署名方式およびプロトコルSAKAP(鍵合意方式)の安全性および効率性について、さらに説明する。つまり、本実施形態における電子署名方式およびSAKAPの安全性(強偽造不可,Private KeyのKnowledge,Known Key Security(KKS),Perfect Forward Secrecy(PFS)、Key Compromise Impersonation Secure(KCIS))に対する5つの定理、1つの系、および、2つの補題について、それぞれが成立し、さらに、効率性を有することを説明する。
【0128】
3.1.強偽造不可
(定理1)g:=f(g)となる条件で、(q,t,ε)−仮定1が成り立つと仮定する。そのとき、前述の本実施形態の電子署名方式は、(q,t,ε)−強偽造不可であり、次の式(46)を満たす。ここで,T はGにおけるべき剰余計算1回にかかる最大時間とする。
【0129】
【数112】

【0130】
(証明)後述する補題1と補題2とから、式(47)を得ることができる。よって、定理1は証明される。
【0131】
【数113】

【0132】
(補題1)g:=f(g)となる条件で、G上の(t,ε)−CDH仮定、および、(q,t,ε)−仮定1が成り立つと仮定する。そのとき、本実施形態における電子署名方式は(q,t,ε)−強偽造不可であり、式(48)を満たす。ここで、TはGにおけるべき剰余計算1回にかかる最大時間とする。
【0133】
【数114】

【0134】
次に、以下のアウトラインに沿って、前述した本実施形態の電子署名方式に関する安全性つまり補題1の証明を行う。
【0135】
まず、前述した本実施形態の電子署名方式の安全性を破る攻撃者A の存在および仮定1のチャレンジを受け取る挑戦者B の存在を仮定する。攻撃者Aと挑戦者B とは強偽造不可ゲームを実行し、攻撃者Aはvalidとなる(文書,署名)の一組を出力する。次に、挑戦者B は仮定1においてvalidとなるレスポンスを計算する。ここで、攻撃者Aの出力は、CDH仮定に矛盾してはならない。
【0136】
(安全性の証明)
本実施形態の電子署名方式の安全性を、(q,t,ε)で破る攻撃者Aの存在を仮定する。ここで、仮定1ゲームを行うシミュレータB を構成する。シミュレータB は、式(49)に示す仮定1ゲームのチャレンジを受け取る。
【0137】
【数115】

【0138】
式(49)において、α,rは、次の式(50)の通りである。また、シミュレータB は、攻撃者Aと以下の手順を実行する。
【0139】
【数116】

【0140】
A.Simulator Description(シミュレータの構成)
Setup(セットアップ):
シミュレータB は、まず、式(51)の乱数から式(52)の情報を生成し、Aに対して、(G, G2, GT, p, e, f)および式(53)の情報を送信する。
【0141】
【数117】

【0142】
【数118】

【0143】
【数119】

【0144】
(1)シグネチャ・クエリ(Signature Queries):
攻撃者A は、シミュレータBに対し、適応的に、Signature Queries M,M,…,Mを行う。式(54)に対し、次の式(55)と仮定する。
【0145】
【数120】

【0146】
【数121】

【0147】
(A−1):
もし、式(56)が成立するならば、シミュレータB はこのゲームを中断する。
【0148】
【数122】

【0149】
(A−2):
式(56)が成立しないその他の場合(すなわち、式(57)の場合)、シミュレータB はゲームを中断せずに、Mに対応するσ=(σi,1,σi,2)を、次の式(58)、式(59)のように、生成し、それをAへ送信する。
【0150】
【数123】

【0151】
【数124】

【0152】
【数125】

【0153】
なお、式(59)において、sは、次の式(60)で与えられる。
【0154】
【数126】

【0155】
式(58)のすべてのr,r,…,rZを消去することにより、式(59)のすべてのs,s,…,sZは乱数と看做すことができることに注意を要する。
【0156】
(2)アウトプット(Output):
攻撃者Aは、(M,σ)を出力する。ただし、式(61)に示すσは、Mに対するvalidな署名であり、次の式(62)の関係にある。
【0157】
【数127】

【0158】
【数128】

【0159】
(3)アーティフィシャル・アボート(Artificial Abort):
式(63)に示す文書Mに対し、式(64)と仮定する。
【0160】
【数129】

【0161】
【数130】

【0162】
ここで、次の式(65)であり、さらに、式(66)が成立するならば、シミュレータB はこのゲームを強制的に中断する。
【0163】
【数131】

【0164】
【数132】

【0165】
B.シミュレーション結果の分析
攻撃者A は、式(67)が成立するときとして、前述の(A−1)に示すような中断があるSimulator Descriptionゲームと、中断のない強偽造不可ゲームとを区別することができない。
【0166】
【数133】

【0167】
その理由は、式(68)の条件を満たす確率Pは、式(69)が成立するとき、negligibleな値となるからである。ゆえに、以降では、Simulator Descriptionゲ−ムのみを考えていけば良い。
【0168】
【数134】

【0169】
【数135】

【0170】
Simulator Descriptionゲームの場合、σはvalidなので、式(70)と仮定する。なお、式(70)において、s∈ Zである。
【0171】
【数136】

【0172】
(B−1)
もし、式(71)が成立するならば、式(72)である。そのとき、B は、式(73)に示すあるrとなる組を式(74)として生成する。式(74)に示す組は、仮定1チャレンジに対するvalidな出力となる。
【0173】
【数137】

【0174】
【数138】

【0175】
【数139】

【0176】
【数140】

【0177】
(B−2)
次に、式(71)が成立しないその他の場合(すなわち、式(75)の場合)について考える。
【0178】
【数141】

【0179】
式(76)の関係にある場合において、Aはεのアドバンテージを持っている。ここで、この問題は、式(77)、式(55)におけるH,H,…,H、式(64)におけるH、式(78)およびAのランダムなビット列から選ばれる。
【0180】
【数142】

【0181】
【数143】

【0182】
【数144】

【0183】
また、式(79)と式(80)とは、式(81)および関係式(55)、(64)から、Aによって選ばれる。
【0184】
【数145】

【0185】
【数146】

【0186】
【数147】

【0187】
また、式(82)の計算から、Bは、式(83)を解くためのεのアドバンテージを持つ。ここで、この問題は、式(84)およびAのランダムなビット列から選ばれる。
【0188】
【数148】

【0189】
【数149】

【0190】
【数150】

【0191】
(B−2.1)
まず、式(85)と仮定する。
【0192】
【数151】

【0193】
(B−2.1.1)
r = rを満たす数k ∈ {1,2,…,q}が存在すると仮定する。式(76)において、もし、Aが、すべてのs(i=1,2,…,q)および式(86)に示すgαを知っているならば、式(76)から式(87)を消去することができる。
【0194】
【数152】

【0195】
【数153】

【0196】
また、式(88)が成立するので、出力の第2成分を式(89)に置き換え、第3成分を消去する。
【0197】
【数154】

【0198】
【数155】

【0199】
ゆえに、A は、式(90)を解くためのアドバンテージεを持つ。ここで、この問題は、式(91)、式(55)におけるH,H,…,H、式(64)におけるHおよびA のランダムなビット列から選ばれる。
【0200】
【数156】

【0201】
【数157】

【0202】
ここで、i=1,2,…,qに対して、式(92)と置く。
【0203】
【数158】

【0204】
また、式(93)が成立するので、A は式(94)から式(95)を計算することができる。
【0205】
【数159】

【0206】
【数160】

【0207】
【数161】

【0208】
よって、式(95)に示す各パラメータを式(90)から消去する。また、式(90)において、式(96)を式(97)へ置き換えることにより、A は、式(98)を解くためのアドバンテージεを持つ。
【0209】
【数162】

【0210】
【数163】

【0211】
【数164】

【0212】
式(99)と仮定する。式(100)に示すy′を式(90)から消去したため,h をZの乱数と看做して良い。
【0213】
【数165】

【0214】
【数166】

【0215】
アーティフィシャル・アボート(Artificial Abort)から式(101)が成り立つことから、前述の問題は、A が、式(102)を解くのにεのアドバンテージを持つことに等しい。ここで、この問題は、式(103)およびAのランダムなビット列から選ばれる。
【0216】
【数167】

【0217】
【数168】

【0218】
【数169】

【0219】
F. Baoらによる“Variations of Diffie-Hellman problem”(Proc. ICICS 2003, Springer-Verlag, 2003)の記載内容から、これは、Aが、式(104)を解くのにεのアドバンテージを持つことに等しい。
【0220】
【数170】

【0221】
これは、A が、CDH問題をnon-negligibleな確率で解くことができることを意味している。
【0222】
(B−2.1.2)
r = rを満たす数k ∈ {1,2,…,q}が存在しないその他の場合(すなわち、式(105)の場合)、式(106)に示す組は、仮定Iチャレンジのvalid(正当)な出力である。
【0223】
【数171】

【0224】
【数172】

【0225】
(B−2.2)
式(85)が成り立たないその他の場合(すなわち、式(107)の場合)、式(108)を式(109)となるすべての添字集合とする。そのとき、式(110)から、r は式(111)となる。
【0226】
【数173】

【0227】
【数174】

【0228】
【数175】

【0229】
【数176】

【0230】
【数177】

【0231】
{j,j,…jq−c}を{1,2,…,q}における{i,i,…i}の補集合とする。そのとき、式(112)が得られる。
【0232】
【数178】

【0233】
(B−2.2.1)
式(113)であり、かつ、r=rとなる数k∈{j,j,…,jq−c}が存在すると仮定する。このとき、(B−2.1.1)項にて説明したように、AはCDH問題をnon-negligibleな確率で解くことができる。
【0234】
【数179】

【0235】
(B−2.2.2)
式(113)ではないか、あるいは、r=rとなる数k∈{j,j,…,jq−c}が存在しないその他の場合(すなわち、c=q、あるいは、式(114)の場合)、式(115)に示す組は、仮定1チャレンジのvalid(正当)な出力である。
【0236】
【数180】

【0237】
【数181】

【0238】
シミュレーション(simulation)において、式(116)のいずれも満たさない場合の確率Pは、次の式(117)で与えられる。
【0239】
【数182】

【0240】
【数183】

【0241】
よって、本発明に係わる電子署名方式S においては、式(118)が成立する。
【0242】
【数184】

【0243】
以上の(B−1)および(B−2)の項における説明から、式(119)に示す確率P (≧ε)は、少なくとも、式(118)の左辺の確率Pより高いということができる。事象A,Aに対し、式(120)であるので、式(121)である。
【0244】
【数185】

【0245】
【数186】

【0246】
【数187】

【0247】
これは、(t,ε)−CDH仮定、または、(q,t,ε)−仮定1に矛盾する。よって、本発明に係わる電子署名方式は、(q,t,ε)−強偽造不可安全である。
【0248】
もし、A が、前述のSimulator Descriptionゲームにおいて、時間t 内の確率ε で、validな偽造を出力したならば、それは、B が仮定1ゲームについて、または、A がCDHゲームについて、式(122)に示す時間以内に、式(123)に示す確率で成功することを意味している。
【0249】
【数188】

【0250】
【数189】

【0251】
よって、式(124)に示す仮定が必要である。これは、式(125)であることを意味している。以上より、前述した補題1は証明された。
【0252】
【数190】

【0253】
【数191】

【0254】
次に、以下に示す補題2について証明する。
(補題2)(q,t,ε)−仮定1が成り立つと仮定する。そのとき、G上の(t,ε)−CDH仮定は成り立つ。ここで、t≦tおよびε≧εであり、TはGにおけるべき剰余計算1回にかかる最大時間とする。
【0255】
(証明)Aを(t,ε)−CDH仮定を破る攻撃者とする。もし、Aが、式(126)に示す情報を受け取ったとき、そのAは、式(127)の入力から式(128)を計算することができる。
【0256】
【数192】

【0257】
【数193】

【0258】
【数194】

【0259】
ここで、sおよびgを式(129)とする。Aは式(130)から式(131)を計算し、式(132)に示すあるrから式(133)を生成する。これは(q,t,ε)−仮定1に矛盾する。
【0260】
【数195】

【0261】
【数196】

【0262】
【数197】

【0263】
【数198】

【0264】
【数199】

【0265】
3.2.Private KeyのKnowledge(プライベートキー知識)
(定理2)もし、攻撃者が、あるshort-term secretおよびその合意文書(の第2成分)を持つならば、その攻撃者は、対応するprivate keyを抽出することができる。
【0266】
(証明)もし、攻撃者が、Aのshort-term secret r∈Zと式(134)に示すAを知っているならば、攻撃者は、式(135)の計算から、対応するprivate key gを抽出することができる。よって、定理2は成り立つ。
【0267】
【数200】

【0268】
【数201】

【0269】
(系1)
本実施形態のSAKAPプロトコルにおいて、参加者Pが式(136)の情報をentity Aへ送信すると仮定する。さらに、Aは、(M,A,A2,0)および自分自身のprivate key g∈ Zから生成した式(137)の文書を送信すると仮定する。そのとき、参加者PがAを知ることと、参加者PがAのprivate keyを得ることとは必要十分の関係にある。
【0270】
【数202】

【0271】
【数203】

【0272】
前記非特許文献15、前記非特許文献16、前記非特許文献17において提案された署名方式から構成されたSAKAPは、プロトコルの各entityのprivate keyに2つのパラメータを使う。このようなプロトコルは、entityと攻撃者による結託攻撃に対し、脆弱性を持つ。
【0273】
例えば、前記非特許文献15の場合を考えてみる。ここで、GとGとを十分大きな素数pの位数を持つ乗法巡回群とする。gをGのランダムな生成元とする。また、式(138)を双線形写像とする。SAKAPは三者のentity A,B,C間で合意するものと仮定する。まず、entity Aは次の4つのフェーズを実行する。
【0274】
【数204】

【0275】
(a)AのKey Generationフェーズ:long-term private key(x,y)∈(Zを生成し、対応するpublic key(P,Q):=(gxA,gyA)∈ Gを計算する。
【0276】
(b)AのMessage Generationフェーズ:ある文書M∈Z、および、t:=x+m+yr∈Zに対し、式(139)を生成する。Aは、BとCとへ(r,A)を送信する。
【0277】
【数205】

【0278】
(c)AのVerificationフェーズ:式(140)が成り立つかどうかを検証する。
【0279】
【数206】

【0280】
(d)AのKey Agreementフェーズ:式(141)を計算する。
【0281】
【数207】

【0282】
entity Bおよびentity Cについても同様に4つのフェーズを行う。entity A,B,Cのagreement keyは、次の式(142)である。
【0283】
【数208】

【0284】
本プロトコルにおいて、entity Aと攻撃者とは以下の結託攻撃を成功させることができる。Message Generationにおいて、攻撃者はt′∈ Zを生成し、それをentity Aへ送信する。entity Aは、式(143)を計算し、計算結果を他のentity B,Cへ送信する。そのとき、entity Bおよびentity C(および外部の参加者)は(r′,A′)をAのvalidな文書と信じてしまう。しかしながら、式(144)に示すagreement keyは、実際には、攻撃者、entity B, Cの三者間で合意されている。
【0285】
【数209】

【0286】
【数210】

【0287】
3.3.Known Key Security(KKS:既知キー安全性)
本実施形態においては、もし、任意の攻撃者Aが時間t内で、次の式(145)を満たすとき、SAKAPは、(q,t,ε)−KKSを持つという。ここで、この確率Pは、式(146)、式(55)における式(147)、R ∈G,j(1≦j≦q-1)およびAのランダムなビット列から選ばれる。
【0288】
【数211】

【0289】
【数212】

【0290】
【数213】

【0291】
(q,t,ε)−KKSは、Aが、式(148)から式(149)についての如何なる部分情報も得ることができないことを意味している。
【0292】
【数214】

【0293】
【数215】

【0294】
(定理3)g:=f(g)となる条件で、(t,ε)−仮定2が成り立つと仮定する。そのとき、本発明に係わるSAKAPプロトコルは(q,t,ε)−Known Key Securityを持つ。ここで、t≦tおよびε≧εである。
【0295】
(証明)Aを(q,t,ε)−KKSを破る攻撃者とする。証明を簡単にするために、private key g,g,gは漏洩していると仮定する。また、y′=y=y=…=y=1と仮定する。ここで、前述の式(145)の中から式(150)を消去し、式(151)に示す成分を式(152)に置き換える。
【0296】
【数216】

【0297】
【数217】

【0298】
【数218】

【0299】
そのとき、式(153)が成立する。ここで、各rA,i,rB,i,rC,i(i=1,2,…,q)はランダムであるから、式(153)の不等式は(t、ε)−仮定2に矛盾する。よって、定理2は成り立つ。
【0300】
【数219】

【0301】
3.4.Perfect Forward Secrecy(PFS:完全フォワード秘匿性)
本実施形態において、SAKAPプロトコルのprivate keyとは、g,g,gを意味している。もし、任意の攻撃者Aが、時間t以内で、式(154)の条件を満たすとき、SAKAPは、(t,ε)−PFSを持つという。ここで、この確率Pは、式(155)、前述の式(55)における式(156)、R ∈GおよびAのランダムなビット列から選ばれる。
【0302】
【数220】

【0303】
【数221】

【0304】
【数222】

【0305】
(t,ε)−PFSは、Aが、式(157)から式(158)についての如何なる部分惰報も得ることができないことを意味している。
【0306】
【数223】

【0307】
【数224】

【0308】
(定理4)g:=f(g)となる条件で、(t,ε)−仮定2が成り立つと仮定する。そのとき、本発明に係わるSAKAPプロトコルは(t,ε)−Perfect Forward Secrecyを持つ。ここで、t≦tおよびε≧εである。
【0309】
(証明)Aを(t,ε)−PFSを破る攻撃者とする。y′=y=y=…=y=1と仮定する。ここで、前述の式(154)の中から式(159)を消去し、式(160)に示す成分を式(161)に置き換える。また、式(162)に示す組は、式(163)に無関係なので、これらの成分を式(154)から消去する。これは、(t,ε)−仮定2に矛盾する。よって、定理4は成り立つ。
【0310】
【数225】

【0311】
【数226】

【0312】
【数227】

【0313】
【数228】

【0314】
【数229】

【0315】
3.5.Key Compromise Impersonation Secure(KCIS:キー漏洩なりすまし安全性)
本実施形態のSAKAPプロトコルにおけるKCISの失敗は、entity Bのprivate key gを知ったentity Aが、entity Cの正当な(C,C)を生成することができることを意味している。より正確には、もし、任意の攻撃者Aが、時間t以内に、式(164)の条件を満たすとき、プロトコルは(q,t,ε)−KCISであるという。ここで、この確率Pは、式(165)、前述の式(55)における式(166)、前述の式(64)におけるHC,*、式(167)およびAのランダムなビット列から選ばれる。
【0316】
【数230】

【0317】
【数231】

【0318】
【数232】

【0319】
【数233】

【0320】
(定理5)g:=f(g)となる条件で、(q,t,ε)−仮定1が成り立つと仮定する。そのとき、本発明に係わるSAKAPプロトコルは、(q,t,ε)−Key Compromise Impersonation Secureである。ここで、式(168)の関係にある。また、TはGにおけるべき剰余計算1回にかかる最大時間とする。
【0321】
【数234】

【0322】
(証明)Aを(q,t,ε)−KCISを破る攻撃者とする。y′=y=y=…=y=1と仮定する。そのとき、式(169)は、前述の式(164)の出力には無関係なので、この問題は、以下のように簡単にすることができる。つまり、Aは、式(170)を解くためのアドバンテージεを持つ。
【0323】
【数235】

【0324】
【数236】

【0325】
また、式(171)が成立するので、値HC,i(i=1,2,…,q)およびHC,*はZに属している。また、Aは、これらの値を計算することができるので、式(172)を、それぞれ、式(173)へ置き換える。MC,*を消去する。これは、(q,t,ε)−仮定1に矛盾する。
【0326】
【数237】

【0327】
【数238】

【0328】
【数239】

【0329】
もし、Aが、KCISの(q,t,ε)−攻撃に成功したならば、そのとき、Aは、時間t+O(qT)以内に、確率εで、仮定1ゲームにおけるvalidな偽造の出力に成功する。よって、定理5が成り立つ。
【0330】
3.6.安全性と効率性
次に、本発明に係わるSAKAPの安全性と効率性とについてさらに説明する。ここでは、本発明に係わるSAKAPプロトコルを、従来技術として前記非特許文献12に記載のWaters方式(これは強偽造不可ではない)ベースのプロトコルおよび前記非特許文献19に記載のBSW(Boneh−Shen−Waters)方式ベースのプロトコルと、安全性の面と効率性の面とから比較した結果を説明する。
【0331】
3.6.1.安全性
表5は、SAKAPの安全性について、本発明に係わるSAKAPプロトコルを、従来技術のWaters方式ベースのモデルとBSW方式ベースのモデルと比較した結果を示すものである。ここで、従来技術のWatersベースモデル、BSWベースモデルに記述している“Yes”は、それぞれの定理がある仮定の下では成り立つようであるが、フォーマルな証明がまだ与えられていないことを意味している。この表5から、本発明に係わるプロトコルの安全性は、少なくともBSWベースモデルのSAKAPと同等であり、Watersベースモデルのものよりも高いことが分かる。
【表5】

【0332】
つまり、本発明に係わるSAKAPプロトコルは、前記非特許文献9の中で説明されているSAKAPプロトコルの(一般的に必要とされる)安全性を満たしている。特に、前述の定理1は、前記非特許文献9におけるNew-Legitimate-Message(新適合メッセージ)のresilience(レジリエンス)についての結果(該非特許文献9における定理1)をも包含していることに注意を要する。また、前記非特許文献9におけるSato-Okamoto-Okamoto SAKAPは、署名方式をベースとしていないので、Replay攻撃に対する耐性を持たない。そこでは、攻撃者は、プロトコルのあるSessionでの情報を記録しておき、後のSessionにおいて同一のあるいは異なるentityへその情報を送信する。これに対して、本発明に係わるプロトコルは、ある信頼できる第三者機関により発行されたtime stampを署名文書に含めることにより、このReplay攻撃に対する耐性を持つことが可能である。
【0333】
3.6.2.効率性
表6は、SAKAPの効率性について、SAKAPの各entityによって実行される計算数を、本発明に係わるSAKAPプロトコルと、従来技術のWaters方式ベースのモデルとBSW方式ベースのモデルとで比較した結果を示している。ここで、括弧の中の和は、SAKAPプロトコルの各フェーズ(Message Generation,Verification,Key Agreement)それぞれにおける計算数の和を表している。
【0334】
例えば、一方向性同型写像f:G→Gの効率について説明する。前述したT. Saitoらによる“Candidate one-way functions on non-supersingular elliptic curves”(IEICE Trans. Fundamentals,vol.E89, pp.144-150, 2006)の文献に記載されたプロトコルの場合、E[p]は、2次元Z/pZ−線形空間、φはE[p]のFrobenius自己準同型写像、P,Qはφの固有ベクトルである。よって、E[p]は、式(174)と表すことができる。2つの群G,GはE[p]の部分集合である。Gは式(175)であり、Gはこれらのどちらでもない。同型写像fは、式(176)に示すように、E[p]から第1成分または第2成分への射影である。
【0335】
【数240】

【0336】
【数241】

【0337】
【数242】

【0338】
ゆえに、一方向性同型写像fは、表6の他の演算に比べ著しく効率的である。以上より、本発明に係わるSAKAPプロトコルの効率は、Watersベースモデルの場合と同程度であり、BSWベースモデルの場合よりも高いということができる。
【表6】

【0339】
4.結論
以上に詳細に説明したように、本発明においては、SAKAPに利用可能な電子署名として、Waters署名(偽造不可安全)と同程度の効率性を持つ強偽造不可安全な電子署名方式のスタンダードモデルを提供している。本電子署名方式に基づいて、鍵合意方式であるSAKAPプロトコルとして三者間SAKAPのスタンダードモデルを構成することができ、本プロトコルは、本発明の対象分野である署名ベースのスタンダードモデルとして安全性を満たすプロトコルの中で最も効率が良い仕組みを提供している。
【0340】
以上、本発明の好適実施例の構成を説明した。しかし、斯かる実施例は、本発明の単なる例示に過ぎず、何ら本発明を限定するものではないことに留意されたい。本発明の要旨を逸脱することなく、特定用途に応じて種々の変形変更が可能であることが、当業者には容易に理解できよう。例えば、本発明の実施態様は、課題を解決するための手段における構成(1)に加えて、次のような構成として表現できる。
(2)前記キー生成フェーズにおいて、ランダムな生成元gGを選び、式(A7)と置き、式(A8)のsecret αから、式(A9)に示す前記プライベートキーSKを生成して、式(A10)を計算することにより、P1を生成し、
【数7】

【数8】

【数9】

【数10】

式(A11)に示すランダムな値u′およびランダムなn-length vector Uを選択した場合、生成される前記パブリックキーPKと前記プライベートキーSKとは、それぞれ、式(A12)の関係になる
【数11】

【数12】

上記(1)の電子署名システム。
(3)前記サインフェーズにおいて、前記署名文書Mをnビットとし、式(A13)に示すmを、前記署名文書M のj 番目のビットとする場合、前記署名文書Mの前記署名σを、乱数r ∈ Z*を使って、式(A14)とする
【数13】

【数14】

上記(2)の電子署名システム。
(4)前記ベリファイフェーズにおいて、前記パブリックキーPK、前記署名文書Mおよび前記署名σとしてσ=(σ,σ)を用い、次の式(A15)の等式が成り立つかどうかを検証し、式(A15)の等式が成り立つとき、valid(正当)を出力し、成り立たないとき、invalid(不当)を出力する
【数15】

上記(3)の電子署名システム。
(5)送信者の認証機能付き鍵合意プロトコル(SAKAP:Sender Authenticated Key Agreement Protocols)として、あるエンティティ(entity)X(X=A,B,C)のパブリックキーPKとプライベートキーSKとを生成するキー生成(Key Generation)フェーズと、前記エンティティXの署名σを生成し、生成した前記署名σを付した署名文書を他のエンティティへ送信するメッセージ生成(Message Generation)フェーズと、他のエンティティから受信した前記署名文書を検証するベリフィケーション(Verification)フェーズと、他のエンティティとの合意鍵(agreement key)を算出するキー・アグリーメント(Key Agreement)フェーズとの各フェーズの演算部を備えた鍵合意システムにおいて、
G,G,Gが素数p の位数を持つ乗法巡回群であり、gはGの生成元であり、f:G→Gが、次の式(A16)を満たす一方向性同型写像であり、e: G×G→Gが、次の式(A17)を満たす双線形写像とした場合、
【数16】

【数17】

式(A18)に示す生成元g,gおよび乱数x,r(i=1,2,…,q)となる式(A19)に示す入力に対し、式(A20)に示すようなあるrとなる式(A21)の計算、
【数18】

【数19】

【数20】

【数21】

および、エンティティX(X=A,B,C)について、式(A22)に示す生成元g,g,乱数rおよびR∈Gとなる式(A23)に示す入力に対し、式(A24)に示すR となるならば1を出力し、それ以外のときは0を出力する計算、
【数22】

【数23】

【数24】

のそれぞれの計算を、攻撃者が、時間t以内で、高々、あらかじめ定めた定数εの確率でしか行うことができない鍵合意システム。
(6)前記キー生成フェーズにおいて、あるエンティティAについて、secreta∈Zから式(A25)に示すプライベートキーSKを生成し、パブリックキーPKとして式(A26)に示すキーを計算し、他のエンティティであるエンティティBおよびエンティティCについても、それぞれ、プライベートキーSKおよびSK、パブリックキーPKおよびPKを、前記エンティティAと同様にして計算し、計算した前記パブリックキーPK,PK,PKそれぞれを、あらかじめ定めた第三者信頼機関によって認証する
【数25】

【数26】

上記(5)の鍵合意システム。
(7)前記メッセージ生成フェーズにおいて、ランダムな生成元gについて、式(A27)と置き、式(A28)に示すランダムな値u′およびランダムなn-lengthのベクトルUを選択した場合であって、
【数27】

【数28】

あるエンティティAの文書Mをnビット署名文書とし、式(A29)に示すmA,jを該署名文書Mのj番目のビットとする場合、short-term secret rZから、式(A30)のように合意文書(A,A)を生成し、生成した該合意文書(A,A)を、他のエンティティであるエンティティBおよびエンティティCに送信し、
【数29】

【数30】

かつ、エンティティBは、前記エンティティAと同様にして生成した合意文書(B,B)を他のエンティティであるエンティティCおよびエンティティAへ送信し、また、エンティティCは、前記エンティティAと同様にして生成した合意文書(C,C)を他のエンティティであるエンティティAおよびエンティティBへ送信する上記(6)の鍵合意システム。
(8)前記ベリフィケーションフェーズにおいて、あるエンティティAは、他のエンティティであるエンティティBとエンティティCとからそれぞれ受け取った前記合意文書(B,B)と前記合意文書(C,C)とを使って、次の式(A31)が成り立つかどうかを検証し、
【数31】

検証結果として、式(A31)に示す2つの等式が成り立つとき、valid(正当)を出力し、成り立たない場合、invalid(不当)を出力し、かつ、エンティティBは、前記エンティティAと同様にして、他のエンティティであるエンティティCとエンティティAとからそれぞれ受け取った合意文書(C,C)と合意文書(A,A)の検証結果を出力し、また、エンティティCは、前記エンティティAと同様にして、他のエンティティであるエンティティAとエンティティBとからそれぞれ受け取った合意文書(A,A)と合意文書(B,B)の検証結果を出力する上記(7)の鍵合意システム。
(9)前記キー・アグリーメントフェーズにおいて、あるエンティティAは、前記short-term secret r,受け取った前記合意文書(B,B)のB,前記合意文書(C,C)のCから、次の式(A32)により、該エンティティAの合意鍵Zを計算し、
【数32】

かつ、他のエンティティであるエンティティB,エンティティCにおいても、前記エンティティAと同様にして、エンティティBの合意鍵ZB、エンティティCの合意鍵ZCをそれぞれ計算し、エンティティA,B,Cの間の三者間の合意鍵を、式(A33)とする
【数33】

上記(8)の鍵合意システム。
(10)パブリックキー(Public Key)PKとプライベートキー(Private Key)SKとのペアを出力するキー生成(KeyGen)フェーズと、該キー生成フェーズが出力する前記プライベートキーSKおよび署名文書Mを入力として、署名σを返すサイン(Sign)フェーズと、前記キー生成フェーズが出力する前記パブリックキーPKおよび前記署名文書Mと前記サインフェーズが出力する前記署名σとの組合せ(M、σ)を入力として、valid(正当)またはinvalid(不当)を返すベリファイ(Verify)フェーズとの各フェーズを有する電子署名方法において、
G,G,Gが素数p の位数を持つ乗法巡回群であり、gはGのランダムな生成元であり、f:G→Gが、次の式(A34)を満たす一方向性同型写像であり、e: G×G→Gが、次の式(A35)を満たす双線形写像とした場合、
【数34】

【数35】

式(A36)に示す生成元g,gおよび乱数x,r(i=1,2,…,q)となる式(A37)に示す入力に対し、式(A38)に示すようなあるrとなる式(A39)の計算を、
【数36】

【数37】

【数38】

【数39】

攻撃者が、時間t以内で、高々、あらかじめ定めた定数εの確率でしか行うことができない電子署名方法。
(11)前記キー生成フェーズにおいて、ランダムな生成元gGを選び、式(A40)と置き、式(A41)のsecret αから、式(A42)に示す前記プライベートキーSKを生成して、式(A43)を計算することにより、P1を生成し、
【数40】

【数41】

【数42】

【数43】

式(A44)に示すランダムな値u′およびランダムなn-length vector Uを選択した場合、生成される前記パブリックキーPKと前記プライベートキーSKとは、それぞれ、式(A45)の関係になる
【数44】

【数45】

上記(10)の電子署名方法。
(12)前記サインフェーズにおいて、前記署名文書Mをnビットとし、式(A46)に示すmを、前記署名文書M のj 番目のビットとする場合、前記署名文書Mの前記署名σを、乱数r ∈ Z*を使って、式(A47)とする
【数46】

【数47】

上記(11)の電子署名方法。
(13)前記ベリファイフェーズにおいて、前記パブリックキーPK、前記署名文書Mおよび前記署名σとしてσ=(σ,σ)を用い、次の式(A48)の等式が成り立つかどうかを検証し、式(A48)の等式が成り立つとき、valid(正当)を出力し、成り立たないとき、invalid(不当)を出力する
【数48】

上記(12)の電子署名方法。
(14)送信者の認証機能付き鍵合意プロトコル(SAKAP:Sender Authenticated Key Agreement Protocols)として、あるエンティティ(entity)X(X=A,B,C)のパブリックキーPKとプライベートキーSKとを生成するキー生成(Key Generation)フェーズと、前記エンティティXの署名σを生成し、生成した前記署名σを付した署名文書を他のエンティティへ送信するメッセージ生成(Message Generation)フェーズと、他のエンティティから受信した前記署名文書を検証するベリフィケーション(Verification)フェーズと、他のエンティティとの合意鍵(agreement key)を算出するキー・アグリーメント(Key Agreement)フェーズとの各フェーズを有する鍵合意方法において、
G,G,Gが素数p の位数を持つ乗法巡回群であり、gはGのランダムな生成元であり、f:G→Gが、次の式(A49)を満たす一方向性同型写像であり、e: G×G→Gが、次の式(A50)を満たす双線形写像とした場合、
【数49】

【数50】

式(A51)に示す生成元g,gおよび乱数x,r(i=1,2,…,q)となる式(A52)に示す入力に対し、式(A53)に示すようなあるrとなる式(A54)の計算、
【数51】

【数52】

【数53】

【数54】

および、エンティティX(X=A,B,C)について、式(A55)に示す生成元g,g,乱数rおよびR∈Gとなる式(A56)に示す入力に対し、式(A57)に示すR となるならば1を出力し、それ以外のときは0を出力する計算、
【数55】

【数56】

【数57】

のそれぞれの計算を、攻撃者が、時間t以内で、高々、あらかじめ定めた定数εの確率でしか行うことができない鍵合意方法。
(15)前記キー生成フェーズにおいて、あるエンティティAについて、secreta∈Zから式(A58)に示すプライベートキーSKを生成し、パブリックキーPKとして式(A59)に示すキーを計算し、他のエンティティであるエンティティBおよびエンティティCについても、それぞれ、プライベートキーSKおよびSK、パブリックキーPKおよびPKを、前記エンティティAと同様にして計算し、計算した前記パブリックキーPK,PK,PKそれぞれを、あらかじめ定めた第三者信頼機関によって認証する
【数58】

【数59】

上記(14)の鍵合意方法。
(16)前記メッセージ生成フェーズにおいて、ランダムな生成元gについて、式(A60)と置き、式(A61)に示すランダムな値u′およびランダムなn-lengthのベクトルUを選択した場合であって、
【数60】

【数61】

あるエンティティAの文書Mをnビット署名文書とし、式(A62)に示すmA,jを該署名文書Mのj番目のビットとする場合、short-term secret rZから、式(A63)のように合意文書(A,A)を生成し、生成した該合意文書(A,A)を、他のエンティティであるエンティティBおよびエンティティCに送信し、
【数62】

【数63】

かつ、エンティティBは、前記エンティティAと同様にして生成した合意文書(B,B)を他のエンティティであるエンティティCおよびエンティティAへ送信し、また、エンティティCは、前記エンティティAと同様にして生成した合意文書(C,C)を他のエンティティであるエンティティAおよびエンティティBへ送信する上記(15)の鍵合意方法。
(17)前記ベリフィケーションフェーズにおいて、あるエンティティAは、他のエンティティであるエンティティBとエンティティCとからそれぞれ受け取った前記合意文書(B,B)と前記合意文書(C,C)とを使って、次の式(A64)が成り立つかどうかを検証し、
【数64】

検証結果として、式(A64)に示す2つの等式が成り立つとき、valid(正当)を出力し、成り立たない場合、invalid(不当)を出力し、かつ、エンティティBは、前記エンティティAと同様にして、他のエンティティであるエンティティCとエンティティAとからそれぞれ受け取った合意文書(C,C)と合意文書(A,A)の検証結果を出力し、また、エンティティCは、前記エンティティAと同様にして、他のエンティティであるエンティティAとエンティティBとからそれぞれ受け取った合意文書(A,A)と合意文書(B,B)の検証結果を出力する上記(16)の鍵合意方法。
(18)前記キー・アグリーメントフェーズにおいて、あるエンティティAは、前記short-term secret r,受け取った前記合意文書(B,B)のB,前記合意文書(C,C)のCから、次の式(A65)により、該エンティティAの合意鍵Zを計算し、
【数65】

かつ、他のエンティティであるエンティティB,エンティティCにおいても、前記エンティティAと同様にして、エンティティBの合意鍵ZB、エンティティCの合意鍵ZCをそれぞれ計算し、エンティティA,B,Cの間の三者間の合意鍵を、式(A66)とする
【数66】

上記(17)の鍵合意方法。
(19)前記課題を解決する手段における(1)及び前記(2)乃至(4)に記載の電子署名システムをコンピュータシステムとして構築したことを特徴とする電子署名システム。
(20)前記(5)乃至(9)に記載の鍵合意システムをコンピュータシステムとして構築したことを特徴とする鍵合意システム。
(21)前記(10)乃至(13)に記載の電子署名方法を、コンピュータにより実行可能なプログラムとして実施することを特徴とする電子署名プログラム。
(22)前記(14)乃至(18)に記載の鍵合意方法を、コンピュータにより実行可能なプログラムとして実施することを特徴とする鍵合意プログラム。
(23)前記(21)に記載の電子署名プログラムをコンピュータにより読取可能な記録媒体に記録することを特徴とするプログラム記録媒体。
(24)前記(22)に記載の鍵合意プログラムをコンピュータにより読取可能な記録媒体に記録することを特徴とするプログラム記録媒体。

【特許請求の範囲】
【請求項1】
パブリックキー(Public Key)PKとプライベートキー(Private Key)SKとのペアを出力するキー生成(KeyGen)フェーズと、該キー生成フェーズが出力する前記プライベートキーSKおよび署名文書Mを入力として、署名σを返すサイン(Sign)フェーズと、前記キー生成フェーズが出力する前記パブリックキーPKおよび前記署名文書Mと前記サインフェーズが出力する前記署名σとの組合せ(M、σ)を入力として、valid(正当)またはinvalid(不当)を返すベリファイ(Verify)フェーズとの各フェーズの演算部を備えた電子署名システムにおいて、
G,G,Gが素数p の位数を持つ乗法巡回群であり、gはGのランダムな生成元であり、f:G→Gが、次の式(A1)を満たす一方向性同型写像であり、e: G×G→Gが、次の式(A2)を満たす双線形写像とした場合、
【数1】

【数2】

式(A3)に示す生成元g,gおよび乱数x,r(i=1,2,…,q)となる式(A4)に示す入力に対し、式(A5)に示すようなあるrとなる式(A6)の計算を、
【数3】

【数4】

【数5】

【数6】

攻撃者が、時間t以内で、高々、あらかじめ定めた定数εの確率でしか行うことができないことを特徴とする電子署名システム。
【請求項2】
前記キー生成フェーズにおいて、ランダムな生成元gGを選び、式(A7)と置き、式(A8)のsecret αから、式(A9)に示す前記プライベートキーSKを生成して、式(A10)を計算することにより、P1を生成し、
【数7】

【数8】

【数9】

【数10】

式(A11)に示すランダムな値u′およびランダムなn-length vector Uを選択した場合、生成される前記パブリックキーPKと前記プライベートキーSKとは、それぞれ、式(A12)の関係になる
【数11】

【数12】

ことを特徴とする請求項1に記載の電子署名システム。
【請求項3】
前記サインフェーズにおいて、前記署名文書Mをnビットとし、式(A13)に示すmを、前記署名文書M のj 番目のビットとする場合、前記署名文書Mの前記署名σを、乱数r ∈ Z*を使って、式(A14)とする
【数13】

【数14】

ことを特徴とする請求項2に記載の電子署名システム。
【請求項4】
前記ベリファイフェーズにおいて、前記パブリックキーPK、前記署名文書Mおよび前記署名σとしてσ=(σ,σ)を用い、次の式(A15)の等式が成り立つかどうかを検証し、式(A15)の等式が成り立つとき、valid(正当)を出力し、成り立たないとき、invalid(不当)を出力する
【数15】

ことを特徴とする請求項3に記載の電子署名システム。
【請求項5】
送信者の認証機能付き鍵合意プロトコル(SAKAP:Sender Authenticated Key Agreement Protocols)として、あるエンティティ(entity)X(X=A,B,C)のパブリックキーPKとプライベートキーSKとを生成するキー生成(Key Generation)フェーズと、前記エンティティXの署名σを生成し、生成した前記署名σを付した署名文書を他のエンティティへ送信するメッセージ生成(Message Generation)フェーズと、他のエンティティから受信した前記署名文書を検証するベリフィケーション(Verification)フェーズと、他のエンティティとの合意鍵(agreement key)を算出するキー・アグリーメント(Key Agreement)フェーズとの各フェーズの演算部を備えた鍵合意システムにおいて、
G,G,Gが素数p の位数を持つ乗法巡回群であり、gはGの生成元であり、f:G→Gが、次の式(A16)を満たす一方向性同型写像であり、e: G×G→Gが、次の式(A17)を満たす双線形写像とした場合、
【数16】

【数17】

式(A18)に示す生成元g,gおよび乱数x,r(i=1,2,…,q)となる式(A19)に示す入力に対し、式(A20)に示すようなあるrとなる式(A21)の計算、
【数18】

【数19】

【数20】

【数21】

および、エンティティX(X=A,B,C)について、式(A22)に示す生成元g,g,乱数rおよびR∈Gとなる式(A23)に示す入力に対し、式(A24)に示すR となるならば1を出力し、それ以外のときは0を出力する計算、
【数22】

【数23】

【数24】

のそれぞれの計算を、攻撃者が、時間t以内で、高々、あらかじめ定めた定数εの確率でしか行うことができないことを特徴とする鍵合意システム。
【請求項6】
前記キー生成フェーズにおいて、あるエンティティAについて、secret a∈Zから式(A25)に示すプライベートキーSKを生成し、パブリックキーPKとして式(A26)に示すキーを計算し、他のエンティティであるエンティティBおよびエンティティCについても、それぞれ、プライベートキーSKおよびSK、パブリックキーPKおよびPKを、前記エンティティAと同様にして計算し、計算した前記パブリックキーPK,PK,PKそれぞれを、あらかじめ定めた第三者信頼機関によって認証する
【数25】

【数26】

ことを特徴とする請求項5に記載の鍵合意システム。
【請求項7】
前記メッセージ生成フェーズにおいて、ランダムな生成元gについて、式(A27)と置き、式(A28)に示すランダムな値u′およびランダムなn-lengthのベクトルUを選択した場合であって、
【数27】

【数28】

あるエンティティAの文書Mをnビット署名文書とし、式(A29)に示すmA,jを該署名文書Mのj番目のビットとする場合、short-term secret rZから、式(A30)のように合意文書(A,A)を生成し、生成した該合意文書(A,A)を、他のエンティティであるエンティティBおよびエンティティCに送信し、
【数29】

【数30】

かつ、エンティティBは、前記エンティティAと同様にして生成した合意文書(B,B)を他のエンティティであるエンティティCおよびエンティティAへ送信し、また、エンティティCは、前記エンティティAと同様にして生成した合意文書(C,C)を他のエンティティであるエンティティAおよびエンティティBへ送信することを特徴とする請求項6に記載の鍵合意システム。
【請求項8】
前記ベリフィケーションフェーズにおいて、あるエンティティAは、他のエンティティであるエンティティBとエンティティCとからそれぞれ受け取った前記合意文書(B,B)と前記合意文書(C,C)とを使って、次の式(A31)が成り立つかどうかを検証し、
【数31】

検証結果として、式(A31)に示す2つの等式が成り立つとき、valid(正当)を出力し、成り立たない場合、invalid(不当)を出力し、かつ、エンティティBは、前記エンティティAと同様にして、他のエンティティであるエンティティCとエンティティAとからそれぞれ受け取った合意文書(C,C)と合意文書(A,A)の検証結果を出力し、また、エンティティCは、前記エンティティAと同様にして、他のエンティティであるエンティティAとエンティティBとからそれぞれ受け取った合意文書(A,A)と合意文書(B,B)の検証結果を出力することを特徴とする請求項7に記載の鍵合意システム。
【請求項9】
前記キー・アグリーメントフェーズにおいて、あるエンティティAは、前記short-term secret r,受け取った前記合意文書(B,B)のB,前記合意文書(C,C)のCから、次の式(A32)により、該エンティティAの合意鍵Zを計算し、
【数32】

かつ、他のエンティティであるエンティティB,エンティティCにおいても、前記エンティティAと同様にして、エンティティBの合意鍵ZB、エンティティCの合意鍵ZCをそれぞれ計算し、エンティティA,B,Cの間の三者間の合意鍵を、式(A33)とする
【数33】

ことを特徴とする請求項8に記載の鍵合意システム。
【請求項10】
パブリックキー(Public Key)PKとプライベートキー(Private Key)SKとのペアを出力するキー生成(KeyGen)フェーズと、該キー生成フェーズが出力する前記プライベートキーSKおよび署名文書Mを入力として、署名σを返すサイン(Sign)フェーズと、前記キー生成フェーズが出力する前記パブリックキーPKおよび前記署名文書Mと前記サインフェーズが出力する前記署名σとの組合せ(M、σ)を入力として、valid(正当)またはinvalid(不当)を返すベリファイ(Verify)フェーズとの各フェーズを有する電子署名方法において、
G,G,Gが素数p の位数を持つ乗法巡回群であり、gはGのランダムな生成元であり、f:G→Gが、次の式(A34)を満たす一方向性同型写像であり、e: G×G→Gが、次の式(A35)を満たす双線形写像とした場合、
【数34】

【数35】

式(A36)に示す生成元g,gおよび乱数x,r(i=1,2,…,q)となる式(A37)に示す入力に対し、式(A38)に示すようなあるrとなる式(A39)の計算を、
【数36】

【数37】

【数38】

【数39】

攻撃者が、時間t以内で、高々、あらかじめ定めた定数εの確率でしか行うことができないことを特徴とする電子署名方法。
【請求項11】
前記キー生成フェーズにおいて、ランダムな生成元gGを選び、式(A40)と置き、式(A41)のsecret αから、式(A42)に示す前記プライベートキーSKを生成して、式(A43)を計算することにより、P1を生成し、
【数40】

【数41】

【数42】

【数43】

式(A44)に示すランダムな値u′およびランダムなn-length vector Uを選択した場合、生成される前記パブリックキーPKと前記プライベートキーSKとは、それぞれ、式(A45)の関係になる
【数44】

【数45】

ことを特徴とする請求項10に記載の電子署名方法。
【請求項12】
前記サインフェーズにおいて、前記署名文書Mをnビットとし、式(A46)に示すmを、前記署名文書M のj 番目のビットとする場合、前記署名文書Mの前記署名σを、乱数r ∈ Z*を使って、式(A47)とする
【数46】

【数47】

ことを特徴とする請求項11に記載の電子署名方法。
【請求項13】
前記ベリファイフェーズにおいて、前記パブリックキーPK、前記署名文書Mおよび前記署名σとしてσ=(σ,σ)を用い、次の式(A48)の等式が成り立つかどうかを検証し、式(A48)の等式が成り立つとき、valid(正当)を出力し、成り立たないとき、invalid(不当)を出力する
【数48】

ことを特徴とする請求項12に記載の電子署名方法。
【請求項14】
送信者の認証機能付き鍵合意プロトコル(SAKAP:Sender Authenticated Key Agreement Protocols)として、あるエンティティ(entity)X(X=A,B,C)のパブリックキーPKとプライベートキーSKとを生成するキー生成(Key Generation)フェーズと、前記エンティティXの署名σを生成し、生成した前記署名σを付した署名文書を他のエンティティへ送信するメッセージ生成(Message Generation)フェーズと、他のエンティティから受信した前記署名文書を検証するベリフィケーション(Verification)フェーズと、他のエンティティとの合意鍵(agreement key)を算出するキー・アグリーメント(Key Agreement)フェーズとの各フェーズを有する鍵合意方法において、
G,G,Gが素数p の位数を持つ乗法巡回群であり、gはGの生成元であり、f:G→Gが、次の式(A49)を満たす一方向性同型写像であり、e: G×G→Gが、次の式(A50)を満たす双線形写像とした場合、
【数49】

【数50】

式(A51)に示す生成元g,gおよび乱数x,r(i=1,2,…,q)となる式(A52)に示す入力に対し、式(A53)に示すようなあるrとなる式(A54)の計算、
【数51】

【数52】

【数53】

【数54】

および、エンティティX(X=A,B,C)について、式(A55)に示す生成元g,g,乱数rおよびR∈Gとなる式(A56)に示す入力に対し、式(A57)に示すR となるならば1を出力し、それ以外のときは0を出力する計算、
【数55】

【数56】

【数57】

のそれぞれの計算を、攻撃者が、時間t以内で、高々、あらかじめ定めた定数εの確率でしか行うことができないことを特徴とする鍵合意方法。
【請求項15】
前記キー生成フェーズにおいて、あるエンティティAについて、secret a∈Zから式(A58)に示すプライベートキーSKを生成し、パブリックキーPKとして式(A59)に示すキーを計算し、他のエンティティであるエンティティBおよびエンティティCについても、それぞれ、プライベートキーSKおよびSK、パブリックキーPKおよびPKを、前記エンティティAと同様にして計算し、計算した前記パブリックキーPK,PK,PKそれぞれを、あらかじめ定めた第三者信頼機関によって認証する
【数58】

【数59】

ことを特徴とする請求項14に記載の鍵合意方法。
【請求項16】
前記メッセージ生成フェーズにおいて、ランダムな生成元gについて、式(A60)と置き、式(A61)に示すランダムな値u′およびランダムなn-lengthのベクトルUを選択した場合であって、
【数60】

【数61】

あるエンティティAの文書Mをnビット署名文書とし、式(A62)に示すmA,jを該署名文書Mのj番目のビットとする場合、short-term secret rZから、式(A63)のように合意文書(A,A)を生成し、生成した該合意文書(A,A)を、他のエンティティであるエンティティBおよびエンティティCに送信し、
【数62】

【数63】

かつ、エンティティBは、前記エンティティAと同様にして生成した合意文書(B,B)を他のエンティティであるエンティティCおよびエンティティAへ送信し、また、エンティティCは、前記エンティティAと同様にして生成した合意文書(C,C)を他のエンティティであるエンティティAおよびエンティティBへ送信することを特徴とする請求項15に記載の鍵合意方法。
【請求項17】
前記ベリフィケーションフェーズにおいて、あるエンティティAは、他のエンティティであるエンティティBとエンティティCとからそれぞれ受け取った前記合意文書(B,B)と前記合意文書(C,C)とを使って、次の式(A64)が成り立つかどうかを検証し、
【数64】

検証結果として、式(A64)に示す2つの等式が成り立つとき、valid(正当)を出力し、成り立たない場合、invalid(不当)を出力し、かつ、エンティティBは、前記エンティティAと同様にして、他のエンティティであるエンティティCとエンティティAとからそれぞれ受け取った合意文書(C,C)と合意文書(A,A)の検証結果を出力し、また、エンティティCは、前記エンティティAと同様にして、他のエンティティであるエンティティAとエンティティBとからそれぞれ受け取った合意文書(A,A)と合意文書(B,B)の検証結果を出力することを特徴とする請求項16に記載の鍵合意方法。
【請求項18】
前記キー・アグリーメントフェーズにおいて、あるエンティティAは、前記short-term secret r,受け取った前記合意文書(B,B)のB,前記合意文書(C,C)のCから、次の式(A65)により、該エンティティAの合意鍵Zを計算し、
【数65】

かつ、他のエンティティであるエンティティB,エンティティCにおいても、前記エンティティAと同様にして、エンティティBの合意鍵ZB、エンティティCの合意鍵ZCをそれぞれ計算し、エンティティA,B,Cの間の三者間の合意鍵を、式(A66)とする
【数66】

ことを特徴とする請求項17に記載の鍵合意方法。
【請求項19】
請求項1乃至4に記載の電子署名システムをコンピュータシステムとして構築したことを特徴とする電子署名システム。
【請求項20】
請求項5乃至9に記載の鍵合意システムをコンピュータシステムとして構築したことを特徴とする鍵合意システム。
【請求項21】
請求項10乃至13に記載の電子署名方法を、コンピュータにより実行可能なプログラムとして実施することを特徴とする電子署名プログラム。
【請求項22】
請求項14乃至18に記載の鍵合意方法を、コンピュータにより実行可能なプログラムとして実施することを特徴とする鍵合意プログラム。
【請求項23】
請求項21に記載の電子署名プログラムをコンピュータにより読取可能な記録媒体に記録いることを特徴とするプログラム記録媒体。
【請求項24】
請求項22に記載の鍵合意プログラムをコンピュータにより読取可能な記録媒体に記録いることを特徴とするプログラム記録媒体。

【公開番号】特開2010−122626(P2010−122626A)
【公開日】平成22年6月3日(2010.6.3)
【国際特許分類】
【出願番号】特願2008−298526(P2008−298526)
【出願日】平成20年11月21日(2008.11.21)
【出願人】(300029617)SBIネットシステムズ株式会社 (5)
【出願人】(508347100)
【出願人】(304000456)
【Fターム(参考)】