(57)【要約】【課題】Waters偽造不可署名と同程度の効率を有する強偽造不可署名方式のスタンダードモデルおよび安全性と効率性とを有する三者間ＳＡＫＡＰのスタンダードモデルを提供する。【解決手段】電子署名方式が、送信者が自分自身のlong-term private keyを知っているという事実を受信者が送信文書から検証することができるという基本的な属性を含む強偽造不可（定理１）であり、かつ、送信者の認証機能付き鍵合意プロトコルＳＡＫＡＰとして、キー生成、メッセージ生成、ベリフィケーション、キー・アグリーメントの４つのフェーズを有し、そのうち、前３つの各フェーズが、前記電子署名方式により構成され、かつ、如何なる送信者もshort-term secretを漏洩せず（定理２）、かつ、Known Key Security（定理３）、Perfect Forward Secrecy（定理４）、Key Compromise Impersonation Secure（定理５）の属性を満たす仕組みを実現する。【選択図】なし【特許請求の範囲】
【請求項１】
パブリックキー（Public Key）ＰＫとプライベートキー（Private Key）ＳＫとのペアを出力するキー生成（KeyGen）フェーズと、該キー生成フェーズが出力する前記プライベートキーＳＫおよび署名文書Mを入力として、署名σを返すサイン（Ｓｉｇｎ）フェーズと、前記キー生成フェーズが出力する前記パブリックキーＰＫおよび前記署名文書Mと前記サインフェーズが出力する前記署名σとの組合せ（M、σ）を入力として、valid（正当）またはinvalid（不当）を返すベリファイ（Ｖｅｒｉｆｙ）フェーズとの各フェーズの演算部を備えた電子署名システムにおいて、
G１,G２,GＴが素数p の位数を持つ乗法巡回群であり、g２はG２のランダムな生成元であり、ｆ：G２→G１が、次の式（Ａ１）を満たす一方向性同型写像であり、e: G１×G２→GＴが、次の式（Ａ２）を満たす双線形写像とした場合、
【数１】
2010122626.tif 000250
【数２】
2010122626.tif 000251
式（Ａ３）に示す生成元g１，g２および乱数x，rｉ（i＝1,2,…,q）となる式（Ａ４）に示す入力に対し、式（Ａ５）に示すようなあるr＊となる式（Ａ６）の計算を、
【数３】
2010122626.tif 000252
【数４】
2010122626.tif 000253
【数５】
2010122626.tif 000254
【数６】
2010122626.tif 000255
攻撃者が、時間t以内で、高々、あらかじめ定めた定数εの確率でしか行うことができないことを特徴とする電子署名システム。
【請求項２】
前記キー生成フェーズにおいて、ランダムな生成元g２ ∈Ｒ G２を選び、式（Ａ７）と置き、式（Ａ８）のsecret αから、式（Ａ９）に示す前記プライベートキーＳＫを生成して、式（Ａ１０）を計算することにより、Ｐ1を生成し、
【数７】
2010122626.tif 000256
【数８】
2010122626.tif 000257
【数９】
2010122626.tif 000258
【数１０】
2010122626.tif 000259
式（Ａ１１）に示すランダムな値u′およびランダムなn-length vector Uを選択した場合、生成される前記パブリックキーＰＫと前記プライベートキーＳＫとは、それぞれ、式（Ａ１２）の関係になる
【数１１】
2010122626.tif 000260
【数１２】
2010122626.tif 000261
ことを特徴とする請求項１に記載の電子署名システム。
【請求項３】
前記サインフェーズにおいて、前記署名文書Mをnビットとし、式（Ａ１３）に示すmｊを、前記署名文書M のｊ 番目のビットとする場合、前記署名文書Mの前記署名σを、乱数r ∈ Zｐ*を使って、式（Ａ１４）とする
【数１３】
2010122626.tif 000262
【数１４】
2010122626.tif 000263
ことを特徴とする請求項２に記載の電子署名システム。
【請求項４】
前記ベリファイフェーズにおいて、前記パブリックキーＰＫ、前記署名文書Mおよび前記署名σとしてσ＝（σ１，σ２）を用い、次の式（Ａ１５）の等式が成り立つかどうかを検証し、式（Ａ１５）の等式が成り立つとき、valid（正当）を出力し、成り立たないとき、invalid（不当）を出力する
【数１５】
2010122626.tif 000264
ことを特徴とする請求項３に記載の電子署名システム。
【請求項５】
送信者の認証機能付き鍵合意プロトコル（ＳＡＫＡＰ：Sender Authenticated Key Agreement Protocols）として、あるエンティティ（entity）Ｘ（Ｘ＝Ａ，Ｂ，Ｃ）のパブリックキーＰＫＸとプライベートキーＳＫＸとを生成するキー生成（Key Generation）フェーズと、前記エンティティＸの署名σＸを生成し、生成した前記署名σＸを付した署名文書を他のエンティティへ送信するメッセージ生成（Message Generation）フェーズと、他のエンティティから受信した前記署名文書を検証するベリフィケーション（Verification）フェーズと、他のエンティティとの合意鍵（agreement key）を算出するキー・アグリーメント（Key Agreement）フェーズとの各フェーズの演算部を備えた鍵合意システムにおいて、
G１,G２,GＴが素数p の位数を持つ乗法巡回群であり、g２はG２の生成元であり、ｆ：G２→G１が、次の式（Ａ１６）を満たす一方向性同型写像であり、e: G１×G２→GＴが、次の式（Ａ１７）を満たす双線形写像とした場合、
【数１６】
2010122626.tif 000265
【数１７】
2010122626.tif 000266
式（Ａ１８）に示す生成元g１，g２および乱数x，rｉ（i＝1,2,…,q）となる式（Ａ１９）に示す入力に対し、式（Ａ２０）に示すようなあるr＊となる式（Ａ２１）の計算、
【数１８】
2010122626.tif 000267
【数１９】
2010122626.tif 000268
【数２０】
2010122626.tif 000269
【数２１】
2010122626.tif 000270
および、エンティティX（X＝A,B,C）について、式（Ａ２２）に示す生成元g１，g２，乱数rｘおよびR∈GＴとなる式（Ａ２３）に示す入力に対し、式（Ａ２４）に示すR となるならば１を出力し、それ以外のときは０を出力する計算、
【数２２】
2010122626.tif 000271
【数２３】
2010122626.tif 000272
【数２４】
2010122626.tif 000273
のそれぞれの計算を、攻撃者が、時間t以内で、高々、あらかじめ定めた定数εの確率でしか行うことができないことを特徴とする鍵合意システム。
【請求項６】
前記キー生成フェーズにおいて、あるエンティティAについて、secret ａ∈Ｒ Zｐ＊から式（Ａ２５）に示すプライベートキーＳＫＡを生成し、パブリックキーＰＫＡとして式（Ａ２６）に示すキーを計算し、他のエンティティであるエンティティBおよびエンティティCについても、それぞれ、プライベートキーＳＫＢおよびＳＫＣ、パブリックキーＰＫＢおよびＰＫＣを、前記エンティティAと同様にして計算し、計算した前記パブリックキーＰＫＡ，ＰＫＢ，ＰＫＣそれぞれを、あらかじめ定めた第三者信頼機関によって認証する
【数２５】
2010122626.tif 000274
【数２６】
2010122626.tif 000275
ことを特徴とする請求項５に記載の鍵合意システム。
【請求項７】
前記メッセージ生成フェーズにおいて、ランダムな生成元g２ について、式（Ａ２７）と置き、式（Ａ２８）に示すランダムな値u′およびランダムなn-lengthのベクトルUを選択した場合であって、
【数２７】
2010122626.tif 000276
【数２８】
2010122626.tif 000277
あるエンティティAの文書MＡをｎビット署名文書とし、式（Ａ２９）に示すmＡ，ｊを該署名文書MＡのｊ番目のビットとする場合、short-term secret  rＡ∈Ｒ Zｐ＊から、式（Ａ３０）のように合意文書（A１，A２）を生成し、生成した該合意文書（A１，A２）を、他のエンティティであるエンティティBおよびエンティティCに送信し、
【数２９】
2010122626.tif 000278
【数３０】
2010122626.tif 000279
かつ、エンティティBは、前記エンティティAと同様にして生成した合意文書（B１，B２）を他のエンティティであるエンティティCおよびエンティティAへ送信し、また、エンティティCは、前記エンティティAと同様にして生成した合意文書（C１，C２）を他のエンティティであるエンティティAおよびエンティティBへ送信することを特徴とする請求項６に記載の鍵合意システム。
【請求項８】
前記ベリフィケーションフェーズにおいて、あるエンティティAは、他のエンティティであるエンティティBとエンティティCとからそれぞれ受け取った前記合意文書（B１，B２）と前記合意文書（C１，C２）とを使って、次の式（Ａ３１）が成り立つかどうかを検証し、
【数３１】
2010122626.tif 000280
検証結果として、式（Ａ３１）に示す２つの等式が成り立つとき、valid（正当）を出力し、成り立たない場合、invalid（不当）を出力し、かつ、エンティティBは、前記エンティティAと同様にして、他のエンティティであるエンティティCとエンティティAとからそれぞれ受け取った合意文書（C１，C２）と合意文書（A１，A２）の検証結果を出力し、また、エンティティCは、前記エンティティAと同様にして、他のエンティティであるエンティティAとエンティティBとからそれぞれ受け取った合意文書（A１，A２）と合意文書（B１，B２）の検証結果を出力することを特徴とする請求項７に記載の鍵合意システム。
【請求項９】
前記キー・アグリーメントフェーズにおいて、あるエンティティAは、前記short-term secret rＡ，受け取った前記合意文書（B１，B２）のB１，前記合意文書（C１，C２）のC１から、次の式（Ａ３２）により、該エンティティAの合意鍵ZＡを計算し、
【数３２】
2010122626.tif 000281
かつ、他のエンティティであるエンティティB，エンティティCにおいても、前記エンティティAと同様にして、エンティティBの合意鍵ZB、エンティティCの合意鍵ZCをそれぞれ計算し、エンティティA，B，Cの間の三者間の合意鍵を、式（Ａ３３）とする
【数３３】
2010122626.tif 000282
ことを特徴とする請求項８に記載の鍵合意システム。
【請求項１０】
パブリックキー（Public Key）ＰＫとプライベートキー（Private Key）ＳＫとのペアを出力するキー生成（KeyGen）フェーズと、該キー生成フェーズが出力する前記プライベートキーＳＫおよび署名文書Mを入力として、署名σを返すサイン（Ｓｉｇｎ）フェーズと、前記キー生成フェーズが出力する前記パブリックキーＰＫおよび前記署名文書Mと前記サインフェーズが出力する前記署名σとの組合せ（M、σ）を入力として、valid（正当）またはinvalid（不当）を返すベリファイ（Ｖｅｒｉｆｙ）フェーズとの各フェーズを有する電子署名方法において、
G１,G２,GＴが素数p の位数を持つ乗法巡回群であり、g２はG２のランダムな生成元であり、ｆ：G２→G１が、次の式（Ａ３４）を満たす一方向性同型写像であり、e: G１×G２→GＴが、次の式（Ａ３５）を満たす双線形写像とした場合、
【数３４】
2010122626.tif 000283
【数３５】
2010122626.tif 000284
式（Ａ３６）に示す生成元g１，g２および乱数x，rｉ（i＝1,2,…,q）となる式（Ａ３７）に示す入力に対し、式（Ａ３８）に示すようなあるr＊となる式（Ａ３９）の計算を、
【数３６】
2010122626.tif 000285
【数３７】
2010122626.tif 000286
【数３８】
2010122626.tif 000287
【数３９】
2010122626.tif 000288
攻撃者が、時間t以内で、高々、あらかじめ定めた定数εの確率でしか行うことができないことを特徴とする電子署名方法。
【請求項１１】
前記キー生成フェーズにおいて、ランダムな生成元g２ ∈Ｒ G２を選び、式（Ａ４０）と置き、式（Ａ４１）のsecret αから、式（Ａ４２）に示す前記プライベートキーＳＫを生成して、式（Ａ４３）を計算することにより、Ｐ1を生成し、
【数４０】
2010122626.tif 000289
【数４１】
2010122626.tif 000290
【数４２】
2010122626.tif 000291
【数４３】
2010122626.tif 000292
式（Ａ４４）に示すランダムな値u′およびランダムなn-length vector Uを選択した場合、生成される前記パブリックキーＰＫと前記プライベートキーＳＫとは、それぞれ、式（Ａ４５）の関係になる
【数４４】
2010122626.tif 000293
【数４５】
2010122626.tif 000294
ことを特徴とする請求項１０に記載の電子署名方法。
【請求項１２】
前記サインフェーズにおいて、前記署名文書Mをnビットとし、式（Ａ４６）に示すmｊを、前記署名文書M のｊ 番目のビットとする場合、前記署名文書Mの前記署名σを、乱数r ∈ Zｐ*を使って、式（Ａ４７）とする
【数４６】
2010122626.tif 000295
【数４７】
2010122626.tif 000296
ことを特徴とする請求項１１に記載の電子署名方法。
【請求項１３】
前記ベリファイフェーズにおいて、前記パブリックキーＰＫ、前記署名文書Mおよび前記署名σとしてσ＝（σ１，σ２）を用い、次の式（Ａ４８）の等式が成り立つかどうかを検証し、式（Ａ４８）の等式が成り立つとき、valid（正当）を出力し、成り立たないとき、invalid（不当）を出力する
【数４８】
2010122626.tif 000297
ことを特徴とする請求項１２に記載の電子署名方法。
【請求項１４】
送信者の認証機能付き鍵合意プロトコル（ＳＡＫＡＰ：Sender Authenticated Key Agreement Protocols）として、あるエンティティ（entity）Ｘ（Ｘ＝Ａ，Ｂ，Ｃ）のパブリックキーＰＫＸとプライベートキーＳＫＸとを生成するキー生成（Key Generation）フェーズと、前記エンティティＸの署名σＸを生成し、生成した前記署名σＸを付した署名文書を他のエンティティへ送信するメッセージ生成（Message Generation）フェーズと、他のエンティティから受信した前記署名文書を検証するベリフィケーション（Verification）フェーズと、他のエンティティとの合意鍵（agreement key）を算出するキー・アグリーメント（Key Agreement）フェーズとの各フェーズを有する鍵合意方法において、
G１,G２,GＴが素数p の位数を持つ乗法巡回群であり、g２はG２の生成元であり、ｆ：G２→G１が、次の式（Ａ４９）を満たす一方向性同型写像であり、e: G１×G２→GＴが、次の式（Ａ５０）を満たす双線形写像とした場合、
【数４９】
2010122626.tif 000298
【数５０】
2010122626.tif 000299
式（Ａ５１）に示す生成元g１，g２および乱数x，rｉ（i＝1,2,…,q）となる式（Ａ５２）に示す入力に対し、式（Ａ５３）に示すようなあるr＊となる式（Ａ５４）の計算、
【数５１】
2010122626.tif 000300
【数５２】
2010122626.tif 000301
【数５３】
2010122626.tif 000302
【数５４】
2010122626.tif 000303
および、エンティティX（X＝A,B,C）について、式（Ａ５５）に示す生成元g１，g２，乱数rｘおよびR∈GＴとなる式（Ａ５６）に示す入力に対し、式（Ａ５７）に示すR となるならば１を出力し、それ以外のときは０を出力する計算、
【数５５】
2010122626.tif 000304
【数５６】
2010122626.tif 000305
【数５７】
2010122626.tif 000306
のそれぞれの計算を、攻撃者が、時間t以内で、高々、あらかじめ定めた定数εの確率でしか行うことができないことを特徴とする鍵合意方法。
【請求項１５】
前記キー生成フェーズにおいて、あるエンティティAについて、secret ａ∈Ｒ Zｐ＊から式（Ａ５８）に示すプライベートキーＳＫＡを生成し、パブリックキーＰＫＡとして式（Ａ５９）に示すキーを計算し、他のエンティティであるエンティティBおよびエンティティCについても、それぞれ、プライベートキーＳＫＢおよびＳＫＣ、パブリックキーＰＫＢおよびＰＫＣを、前記エンティティAと同様にして計算し、計算した前記パブリックキーＰＫＡ，ＰＫＢ，ＰＫＣそれぞれを、あらかじめ定めた第三者信頼機関によって認証する
【数５８】
2010122626.tif 000307
【数５９】
2010122626.tif 000308
ことを特徴とする請求項１４に記載の鍵合意方法。
【請求項１６】
前記メッセージ生成フェーズにおいて、ランダムな生成元g２ について、式（Ａ６０）と置き、式（Ａ６１）に示すランダムな値u′およびランダムなn-lengthのベクトルUを選択した場合であって、
【数６０】
2010122626.tif 000309
【数６１】
2010122626.tif 000310
あるエンティティAの文書MＡをｎビット署名文書とし、式（Ａ６２）に示すmＡ，ｊを該署名文書MＡのｊ番目のビットとする場合、short-term secret  rＡ∈Ｒ Zｐ＊から、式（Ａ６３）のように合意文書（A１，A２）を生成し、生成した該合意文書（A１，A２）を、他のエンティティであるエンティティBおよびエンティティCに送信し、
【数６２】
2010122626.tif 000311
【数６３】
2010122626.tif 000312
かつ、エンティティBは、前記エンティティAと同様にして生成した合意文書（B１，B２）を他のエンティティであるエンティティCおよびエンティティAへ送信し、また、エンティティCは、前記エンティティAと同様にして生成した合意文書（C１，C２）を他のエンティティであるエンティティAおよびエンティティBへ送信することを特徴とする請求項１５に記載の鍵合意方法。
【請求項１７】
前記ベリフィケーションフェーズにおいて、あるエンティティAは、他のエンティティであるエンティティBとエンティティCとからそれぞれ受け取った前記合意文書（B１，B２）と前記合意文書（C１，C２）とを使って、次の式（Ａ６４）が成り立つかどうかを検証し、
【数６４】
2010122626.tif 000313
検証結果として、式（Ａ６４）に示す２つの等式が成り立つとき、valid（正当）を出力し、成り立たない場合、invalid（不当）を出力し、かつ、エンティティBは、前記エンティティAと同様にして、他のエンティティであるエンティティCとエンティティAとからそれぞれ受け取った合意文書（C１，C２）と合意文書（A１，A２）の検証結果を出力し、また、エンティティCは、前記エンティティAと同様にして、他のエンティティであるエンティティAとエンティティBとからそれぞれ受け取った合意文書（A１，A２）と合意文書（B１，B２）の検証結果を出力することを特徴とする請求項１６に記載の鍵合意方法。
【請求項１８】
前記キー・アグリーメントフェーズにおいて、あるエンティティAは、前記short-term secret rＡ，受け取った前記合意文書（B１，B２）のB１，前記合意文書（C１，C２）のC１から、次の式（Ａ６５）により、該エンティティAの合意鍵ZＡを計算し、
【数６５】
2010122626.tif 000314
かつ、他のエンティティであるエンティティB，エンティティCにおいても、前記エンティティAと同様にして、エンティティBの合意鍵ZB、エンティティCの合意鍵ZCをそれぞれ計算し、エンティティA，B，Cの間の三者間の合意鍵を、式（Ａ６６）とする
【数６６】
2010122626.tif 000315
ことを特徴とする請求項１７に記載の鍵合意方法。
【請求項１９】
請求項１乃至４に記載の電子署名システムをコンピュータシステムとして構築したことを特徴とする電子署名システム。
【請求項２０】
請求項５乃至９に記載の鍵合意システムをコンピュータシステムとして構築したことを特徴とする鍵合意システム。
【請求項２１】
請求項１０乃至１３に記載の電子署名方法を、コンピュータにより実行可能なプログラムとして実施することを特徴とする電子署名プログラム。
【請求項２２】
請求項１４乃至１８に記載の鍵合意方法を、コンピュータにより実行可能なプログラムとして実施することを特徴とする鍵合意プログラム。
【請求項２３】
請求項２１に記載の電子署名プログラムをコンピュータにより読取可能な記録媒体に記録いることを特徴とするプログラム記録媒体。
【請求項２４】
請求項２２に記載の鍵合意プログラムをコンピュータにより読取可能な記録媒体に記録いることを特徴とするプログラム記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子署名システム、鍵合意システム、電子署名方法および鍵合意方法に関する。
【背景技術】
【０００２】
送信者認証機能付き鍵合意プロトコル（ＳＡＫＡＰ：Sender Authenticated Key Agreement Protocols）は認証機能付きの鍵合意を実施するプロトコルの一種である。ＳＡＫＡＰでは、送信者がlong-termのprivate keyを持っているかどうかを、第三者によって検証することができる。ＳＡＫＡＰは、非特許文献１の“On one-pass authenticated key establishment schemes”，（Workshop Record of Workshop on Selected Areas in Cryptography（SAC‘95）、pp．2-8,1995）において、K.Nybergによって最初に提案されたが、該非特許文献１にて提案されたプロトコルは、鍵合意として望ましい要件であるForward Secrecy（ＦＳ：フォワード秘匿性）を満たしていなかった。
【０００３】
その後、Y.J.Choie-E.Jeong-E.LeeおよびC.Popescuは、それぞれ、非特許文献２の“Efficient identity-based authenticated key agreement protocol from pairings”（Appl.Math.Comput.,vol.162,pp.179-188,2005）、および、非特許文献３の“A secure key agreement protocol using elliptic curves”,Int.J.Comput．Appl.vol.27,pp.147-152,2005”において、Perfect  ＦＳ（完全フォワード秘匿性）を満たす二者間モデルを提案した。
【０００４】
また、F.Zhang-S.Liu-K.Kim、D.NallaおよびK.Shimは、それぞれ、非特許文献４の““ID-based one round authenticated tripartite key agreement protocol with pairings”(2003 IEEE International Symposium on Information Theory,Yokohama,JAPAN,2003)、非特許文献５の“ID-based tripartite key agreement with signatures”(Cryptology ePrint Archive，available at  http://eprint.iacr.org/2003/144/)、および、非特許文献６の“Cryptanalysis of ID-based tripartite authenticated key agreement protocols”(Cryptology ePrint Archive，available at http://eprint.iacr.org/2003/115/)において、三者間ＩＤベースＳＡＫＡＰを提案した。
【０００５】
また、X.Du-Y.Wang−J.Ge- Y.Wangは、非特許文献７の“An ID-based authenticated two round multi-party key agreement”(Cryptology ePrint Archive,available at http://eprint.iacr.org/2003/247/)および非特許文献８の“An improved ID-based authenticated group key agreement scheme”，（Cryptology ePrint Archive,available at http://eprint.iacr.org/2003/260/）において、多者間でのプロトコルを提案した。さらに、ＳＡＫＡＰの最初のスタンダードモデル（すなわち、ランダムオラクルを仮定せずに安全性を証明できるモデル）が、本発明者により、非特許文献９の“Sender authenticated key agreements without random oracles”(Proc. ICCIT 2007,IEEE CS Press，pp.2156-2162,2007)において提案された。
【０００６】
ＳＡＫＡＰおよび電子署名方式について考えてみると、多くの署名方式は、ＳＡＫＡＰの構成に利用できそうである。その理由の一つとして、これまでに提案されたＳＡＫＡＰが、基本的に、非特許文献１０のW.Diffie-M.E.Hellmanによる“New directions in cryptography”（IEEE Trans. Inf. Theory,vo1.22，pp.644-654,1976）に記載のDiffie-Hellman（ＤＨ）鍵合意（あるいは、非特許文献１１の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 を位数とする乗法巡回群の生成元であり、ｒ∈Ｚｐ＊:＝｛1,2,・・・,p-1｝は乱数である。
【０００７】
その他の理由として、署名方式の各フェーズは、以下のように、ＳＡＫＡＰのフェーズに対応することが挙げられる。署名方式は、３つのフェーズ（KeyGen：キー生成，Sign：サイン，Verify：ベリファイ）から構成され、ＳＡＫＡＰは、４つのフェーズ（Key Generation：キー生成，Message Generation：メッセージ生成，Verification：ベリフィケーション，Key Agreement：キー・アグリーメント(鍵合意)）から構成されるものとする。そのとき、署名方式の各フェーズは、それぞれ、ＳＡＫＡＰのフェーズKey Generation，Message Generation，Verificationに対応する。また、ＤＨ鍵合意をベースとしていない鍵合意プロトコルは、一般に、計算量的なアドバンテージを有するものの、ＦＳを満たしていない。よって、本発明においては、前記被特許文献１０に記載のＤＨ鍵合意ベースのＳＡＫＡＰに応用可能な電子署名方式を対象とすることとする。
【０００８】
ＳＡＫＡＰとしての署名が、例えば適応的選択文書攻撃に対する(弱)存在的偽造不可（偽造不可：(weakly) Existential Unforgeable under an adaptive Chosen Message Attack）ではあるが、強偽造不可（strongly Existential Unforgeable under an adaptive Chosen Message Attack:適応的選択文書攻撃に対する強存在的偽造不可）ではないと仮定する。この場合、もし、ＳＡＫＡＰのある正当な合意文書が存在すれば、攻撃者は、ｖａｌｉｄ（正当）な別の合意文書を偽造することができる。（例としては、非特許文献１２のB.Watersによる“Efficient identity-based encryption without random oracles”（Proc. Eurocrypt 2005,LNCS 3027,pp.223-238,2005）を参照のこと。）それゆえ、ＳＡＫＡＰに応用可能な署名は、少なくとも、強偽造不可の安全性が必要である。
【０００９】
ランダムオラクルは、理想的なハッシュ関数と考えられるが、ＭＤ５（Message Digest Algorithm 5）やＳＨＡ−１（Secure Hash Algorithm-1）のような一般に利用されているハッシュ関数を含んでいない。ランダムオラクルを仮定しない署名（またはＩＤベース暗号）方式の研究は、公開鍵基盤における最重要テーマの一つである。よって、本発明が対象とする電子署名方式およびＳＡＫＡＰつまり鍵合意方式は、スタンダードモデル（ランダムオラクル仮定を用いない）のみとする。
【００１０】
現在、効率的である強偽造不可安全な署名のスタンダードモデルが、非特許文献１３の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）、および、非特許文献１４の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）において提案されている。しかし、これらの署名方式から構成されるＳＡＫＡＰは、ＤＨ鍵合意をベースとしていないものと思われる。ＦＳ（フォワード秘匿性）の観点から、本発明においては、前記非特許文献１３，１４の各方式についてこれ以上論じないことにする。
【００１１】
非特許文献１５のD.Boneh and X.Boyenによる“Short signatures without random oracles”（Proc.Eurocrypt 2004,LNCS 3027,pp.56-73,2004）、非特許文献１６の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）、非特許文献１７のJ.Camenisch and A.Lysyanskayaによる“Signature schemes and anonymous credentials from bilinear maps”（Proc.Crypto 2004,LNCS 3152, pp.56-72,2004）において提案された署名方式のスタンダードモデルは、それぞれ強ＤＨ仮定、square root仮定、ＬＲＳＷ仮定のもと、強偽造不可安全である。
【００１２】
しかし、前記非特許文献１５，１６，１７の三方式においては、private keyは、（１つではなく、）２つのパラメータにより定義されるので、これらの方式から構成されるＳＡＫＡＰは、一部の結託攻撃に対する耐性がない。詳細は後述するが、かくのごとき攻撃に対する耐性を持つ署名は、非特許文献１８のT.Okamotoにより“Efficient blind and partially blind signatures without random oracles”（Proc. TCC 2006,LNCS 3876, pp.80-99,2006）において提案されているOkamoto方式、および、非特許文献１９のD.Boneh,E,Shen and B.Watersにより “Strongly unforgeable signatures based on computational Diffie-Hallman”（Proc. PKC 2006,LNCS 3958, pp.229-240,2006）において提案されているＢＳＷ方式のみである。ＢＳＷ方式ベースのＳＡＫＡＰは、Okamoto方式ベースのものよりも効率が良い。しかしながら、ＢＳＷ方式は、B.Watersにより前記非特許文献１２にて提案された偽造不可方式(Waters方式)から構成されたものであるにも関わらず、ＢＳＷ方式ベースのＳＡＫＡＰは、Waters方式ベースのものよりも効率が悪いという問題がある。署名システムと認証機能付き鍵合意システムを考えるとき、各entityに関する鍵合意の成分が署名文書にのみに含まれている場合、この鍵合意方式は前記結託攻撃に対する耐性を持つことができないことに注意せよ。
【非特許文献１】K.Nyberg,“On one-pass authenticated key establishment schemes”，Workshop Record of Workshop on Selected Areas in Cryptography（SAC‘95）,pp.2-8,1995
【非特許文献２】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
【非特許文献３】C.Popescu,“A secure key agreement protocol using elliptic curves”,Int.J.Comput.Appl.vol.27,pp.147-152,2005
【非特許文献４】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
【非特許文献５】D.Nalla,“ID-based tripartite key agreement with signatures”，Cryptology ePrint Archive，available at  http://eprint.iacr.org/2003/144/
【非特許文献６】K．Shim，“Cryptanalysis of ID-based tripartite authenticated key agreement protocols”，Cryptology ePrint Archive，available athttp://eprint.iacr.org/2003/115/
【非特許文献７】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/
【非特許文献８】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/
【非特許文献９】C.Sato，T.Okamoto and E.Okamoto，“Sender authenticated key agreements without random oracles”，Proc. ICCIT 2007,IEEE CS Press,pp.2156-2162,2007
【非特許文献１０】W.Diffie and M.E.Hellman,“New directions in cryptography”, IEEETrans. Inf. Theory,vo1.22,pp.644-654,1976
【非特許文献１１】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
【非特許文献１２】B.Waters,“Efficient identity-based encryption without random oracles”,Proc.Eurocrypt 2005,LNCS 3027,pp.223-238,2005
【非特許文献１３】R.Gennaro,S.Halevi and T.Rabin,“Secure hash-and-sign signatures without the random oracle”,Proc．Eurocrypt1999,LNCS 1592,pp.123-139,1999
【非特許文献１４】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
【非特許文献１５】D.Boneh and X.Boyen,“Short signatures without random oracles”，Proc.Eurocrypt 2004,LNCS 3027,pp.56-73,2004
【非特許文献１６】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
【非特許文献１７】J.Camenisch and A.Lysyanskaya,“Signature schemes and anonymous credentials from bilinear maps”，Proc. Crypto 2004,LNCS 3152, pp.56-72,2004
【非特許文献１８】T.Okamoto,“Efficient blind and partially blind signatures without random oracles”,Proc. TCC 2006,LNCS 3876,pp.80-99,2006
【非特許文献１９】D.Boneh,E,Shen and B.Waters,“Strongly unforgeable signatures based on computational Diffie-Hallman”,Proc. PKC 2006,LNCS 3958, pp.229-240,2006
【発明の開示】
【発明が解決しようとする課題】
【００１３】
本発明は、前述したような従来技術の問題に鑑みてなされたものであり、本発明においては、Waters署名方式における偽造不可署名と同程度の効率を有する、強偽造不可署名方式のスタンダードモデルを提供することを目的とする。さらに、該強偽造不可署名方式をベースに、三者間ＳＡＫＡＰのスタンダードモデルを提供することを目的とする。
【課題を解決するための手段】
【００１４】
前述の課題を解決するため、本発明による電子署名システム、鍵合意システム、電子署名方法および鍵合意方法は、次のような特徴的な構成を採用している。
【００１５】
（１）パブリックキー（Public Key）ＰＫとプライベートキー（Private Key）ＳＫとのペアを出力するキー生成（KeyGen）フェーズと、該キー生成フェーズが出力する前記プライベートキーＳＫおよび署名文書Mを入力として、署名σを返すサイン（Ｓｉｇｎ）フェーズと、前記キー生成フェーズが出力する前記パブリックキーＰＫおよび前記署名文書Mと前記サインフェーズが出力する前記署名σとの組合せ（M、σ）を入力として、valid（正当）またはinvalid（不当）を返すベリファイ（Ｖｅｒｉｆｙ）フェーズとの各フェーズの演算部を備えた電子署名システムにおいて、
G１,G２,GＴが素数p の位数を持つ乗法巡回群であり（一般的に、G１，G２は、加法巡回群として定義されるが、表記の簡略化のため、乗法巡回群とする）、g２はG２のランダムな生成元であり、ｆ：G２→G１が、次の式（Ａ１）を満たす一方向性同型写像であり、e: G１×G２→GＴが、次の式（Ａ２）を満たす双線形写像とした場合、
【数１】
2010122626.tif 000002
【数２】
2010122626.tif 000003
式（Ａ３）に示す生成元g１，g２および乱数x，rｉ（i＝1,2,…,q）となる式（Ａ４）に示す入力に対し、式（Ａ５）に示すようなあるr＊となる式（Ａ６）の計算を、
【数３】
2010122626.tif 000004
【数４】
2010122626.tif 000005
【数５】
2010122626.tif 000006
【数６】
2010122626.tif 000007
攻撃者が、時間t以内で、高々、あらかじめ定めた定数εの確率でしか行うことができない電子署名システム。
【発明の効果】
【００１６】
本発明の電子署名システム、鍵合意システム、電子署名方法および鍵合意方法によれば、以下のような効果を得ることができる。
【００１７】
つまり、本発明においては、偽造不可署名であるWaters署名方式と同程度の効率を有する強偽造不可の電子署名方式のスタンダードモデルを実現している。さらに、本発明による三者間ＳＡＫＡＰのスタンダードモデルのプロトコルは、鍵合意方式としての安全性を確保するとともに、Waters署名方式から構成されるＳＡＫＡＰと同程度の効率性を実現している。この結果、本発明の対象とする分野における安全性を満たすプロトコルのスタンダードモデルとして最も効率が良いモデルを実現することができる。
【発明を実施するための最良の形態】
【００１８】
以下、本発明による電子署名システム、鍵合意システム、電子署名方法および鍵合意方法の好適な実施例について説明する。なお、以下の説明においては、本発明による電子署名方法および鍵合意方法の一例について説明するが、該電子署名方法および鍵合意方法を、例えば演算部（ＣＰＵを含む）を備えるコンピュータシステムとして構築した電子署名システムおよび鍵合意システムとして実現することも、或いはその電子署名方法および鍵合意方法を、コンピュータにより実行可能なプログラム（電子署名プログラムおよび鍵合意プログラム）として実現することも、もちろん可能であることは言うまでもない。
【００１９】
（本発明の特徴）
本発明の実施形態の説明に先立って、本発明の特徴についてまず説明する。本発明は、送信者認証機能付き鍵合意方式に利用可能な電子署名方式を実現している。本発明による電子署名方式は、さらに、送信者がlong-termのprivate keyを持っているかどうかを、第三者によって検証することができる認証機能を有する鍵合意方式を構成している。すなわち、本電子署名方式においては、Waters署名（偽造不可安全）と同程度の効率性を持つ強偽造不可(strongly  Existential  Unforgeable  under  an  adaptive  Chosen  Message  Attack:適応的選択文書攻撃に対する強存在的偽造不可)安全な署名方式のスタンダードモデルを実現している。該電子署名方式に基づいて、さらに、三者間で行う送信者認証機能付き鍵合意方式に関するＳＡＫＡＰプロトコルのスタンダードモデルを構成する。該プロトコルは、以下に詳細に説明するように、署名ベースのスタンダードモデルとして、本発明の対象分野において扱う安全性（強偽造不可，Private KeyのKnowledge（プライベートキー知識），Known Key Security（既知キー安全性），Perfect Forward Secrecy（完全フォワード秘匿性），Key Compromise Impersonation Secure（キー漏洩なりすなし安全性））の各要件を満たすプロトコルの中で、最も効率が良い。
【００２０】
つまり、送信者認証機能付き鍵合意プロトコル（ＳＡＫＡＰ：Sender Authenticated Key Agreement Protocols）の最も基本的な性質は、送信者が自分自身のlong-term private keyを知っているという事実を、受信者が、送信文書から検証することができることである。本発明による電子署名方式の安全性（強偽造不可、定理１）は、この基本的な属性を含んでいる。また、本発明による電子署名方式に基づく送信者認証機能付き鍵合意プロトコルＳＡＫＡＰは、いかなる送信者もshort-term secretを漏洩しない（定理２）。加えて、本プロトコルは、ほとんどの鍵合意プロトコルで議論されるKnown Key Security（定理３）、Perfect Forward Secrecy（定理４）、Key Compromise Impersonation Secure（定理５）の属性を満たしている。
【００２１】
以下に、本発明による実施形態の詳細について、次の順番に説明する。第１番目の「準備段階」の項において、本発明による電子署名方式および送信者認証機能付き鍵合意プロトコルＳＡＫＡＰつまり鍵合意方式の構成および安全性証明のための準備として各種の定義を行う。次の第２番目の「本発明による実施形態」の項において、本発明の一例である電子署名方式を説明し、さらに、該電子署名方式をベースにした送信者認証機能付き鍵合意プロトコルＳＡＫＡＰのプロトコル構成つまり鍵合意方式構成の一例を説明する。しかる後、第３番目の「安全性および効率性の証明」の項において、本発明に係わるいくつかの定理を設定して、それらの定理の証明を行った後、既存技術との比較を行うことにより、本発明における電子署名方式、送信者認証機能付き鍵合意プロトコルＳＡＫＡＰ（鍵合意方式）が、強偽造不可安全を満たす安全性および効率性を十分に備えていることを説明し、最後の第４番目の「結論」の項において本発明のまとめを説明する。
【００２２】
１．準備段階
ここでは、本発明による実施形態の説明に用いる一方向性同型写像（One Way Isomorphism）、双線形写像（Bilinear Map）、Computational Diffie-Hellman（ＣＤＨ）問題に関連した２つの仮定、署名方式、強偽造不可、Known Key Security、Perfect Forward SecrecyおよびKey Compromise Impersonation Secureをそれぞれ定義する。
【００２３】
１．１．一方向性同型写像および双線形写像
一方向性同型写像および双線形写像に関する以下の定義は、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）に従っている。
（１）G１,G２,GＴは素数p の位数を持つ乗法巡回群である（一般的に、G１，G２は、加法巡回群として定義されるが、表記の簡略化のため、乗法巡回群とする）;
（２）g２はG２の生成元である;
（３）ｆ：G２→G１は一方向性同型写像であり、次の式（１）を満たす;
【００２４】
【数６７】
2010122626.tif 000008
【００２５】
（４）e : G１×G２→GＴは双線形写像であり、以下の属性（ａ）〜（ｃ）を持つ:
【００２６】
（ａ）双線形性: 任意のu ∈ G１、v ∈ G２と任意のa，b ∈ Zに対し、次の式（２）を満たす。
【００２７】
【数６８】
2010122626.tif 000009
【００２８】
（ｂ）非退化:次の式（３）を満たす。
【００２９】
【数６９】
2010122626.tif 000010
【００３０】
（ｃ）計算可能:任意のu ∈ G１ と任意のv ∈ G２に対し，e(u,v)を計算する効率的な計算アルゴリズムが存在する。
【００３１】
ここで、G１，G２は、一般的に、一方向性同型写像f や双線形写像e 上において加法巡回群として定義されるが、以下の説明においては、表記の簡略化のため、乗法巡回群とする。
【００３２】
１．２．ＣＤＨ問題に関連した２つの仮定
以下の定義は、前記非特許文献９、および、C.Satoらによる“Strongly unforgeable ID-based signatures without random oracles”（Cryptology ePrint Archive，available at http://eprint.iacr.org/2008/095/）に準拠して定めている。
【００３３】
まず、本実施形態における電子署名方式およびＳＡＫＡＰプロトコルのベースとなる、ＣＤＨ問題に関連のある仮定１および仮定２について説明する。
【００３４】
アドバンテージεおよび時間ｔ以内で実行する任意の攻撃者Aに対し、次の式（４）が成り立つならば、G２上の（t,ε）−ＣＤＨ仮定は成り立つという。ここで、式（４）の確率Pｒは、ランダムな生成元ｇ２ ∈Ｒ G２、乱数a,b ∈Ｒ Ｚｐ＊およびAのランダムなビット列から選ばれている。
【００３５】
【数７０】
2010122626.tif 000011
【００３６】
第一の問題は、以下のように与えられる。
つまり、第一の問題は、式（５）に示すようなランダムな生成元g１ ∈Ｒ G１，g２ ∈Ｒ G２および乱数x，r１，r２，…，rｑ ∈Ｒ Zｐ*となる式（６）に示す入力に対し、式（７）に示すようなあるr＊となる式（８）を計算せよというものである。ここで、式（８）に示すように、第２項のｇ２の指数｛x+１/r＊｝は、｛x +(１/r＊)｝を意味していることに注意を要する。
【００３７】
【数７１】
2010122626.tif 000012
【００３８】
【数７２】
2010122626.tif 000013
【００３９】
【数７３】
2010122626.tif 000014
【００４０】
【数７４】
2010122626.tif 000015
【００４１】
もし、式（９）が成り立つならば、アルゴリズムA は、第一の問題を解くためのあらかじめ定めた定数εのアドバンテージを持っているという。ここで、式（９）の確率Pｒは、式（５）、式（７）およびAのランダムなビット列から選ばれている。
【００４２】
【数７５】
2010122626.tif 000016
【００４３】
ここで、仮定１を次のように設定する。
（仮定１）攻撃者A が、時間t以内で、第一の問題を解くアドバンテージを高々あらかじめ定めた確率εしか持たないとき、(q，t，ε)−仮定１は成り立つという。
【００４４】
なお、ランダムな生成元g２ ∈Ｒ G２に対し、一方向性同型写像f: G２→G１をg１ :＝ f(g２) ∈ G１ で定義するとき、生成元g１はランダムではないことに注意することを要する。
【００４５】
次の第二の問題は、以下のように与えられる。
つまり、第二の問題は、式（１０）に示すようなランダムな生成元g１ ∈Ｒ G１，g２ ∈Ｒ G２，乱数rＡ，rＢ，rＣ ∈Ｒ Zｐ*およびR∈GＴとなる式（１１）に示す入力に対し、式（１２）に示すようなR となるならば１を出力し、それ以外のときは０を出力せよというものである。
【００４６】
【数７６】
2010122626.tif 000017
【００４７】
【数７７】
2010122626.tif 000018
【００４８】
【数７８】
2010122626.tif 000019
【００４９】
もし、式（１３）が成り立つならば、アルゴリズムA は、第二の問題を解くためのあらかじめ定めた定数εのアドバンテージを持っているという。ここで、式（１３）の確率Pｒは、式（１０）およびAのランダムなビット列から選ばれている。
【００５０】
【数７９】
2010122626.tif 000020
【００５１】
ここで、仮定２を次のように設定する。
（仮定２）攻撃者A が、時間t以内で、第二の問題を解くアドバンテージを高々あらかじめ定めた確率εしか持たないとき、(t，ε)−仮定２は成り立つという。
【００５２】
なお、前述のように、ランダムな生成元g２ ∈Ｒ G２に対し、一方向性同型写像f : G２→G１をg１ :＝f(g２) ∈ G１ で定義するとき、生成元g１はランダムではないことに注意することを要する。
【００５３】
この仮定２は、R∈ＧＴを除いた式（１１）の成分から、アルゴリズムAが式（１４）に示すについての如何なる部分情報も得ることができないということを意味している。
【００５４】
【数８０】
2010122626.tif 000021
【００５５】
１．３．電子署名方式
ここでの電子署名方式の定義は、前記非特許文献１５および前記非特許文献１９に記載された内容に準拠している。
【００５６】
本電子署名方式は、次の３つのフェーズ(KeyGen，Sign，Verify)から以下のように構成される。
【００５７】
（ａ）キー生成（KeyGen）フェーズ：
ランダムなkeyペア（ＰＫ，ＳＫ）つまりPublic key ＰＫ，Private Key ＳＫのペアを出力する。
【００５８】
（ｂ）サイン（Sign）フェーズ：
Private Key ＳＫおよび（ある集合μ内の）署名文書Mを入力として、署名σを返す。
【００５９】
（ｃ）ベリファイ（Verify）フェーズ：
Public key ＰＫおよび署名文書、署名の組合せ（M、σ）を入力として、valid（正当）またはinvalid（不当）を返す。
【００６０】
つまり、本電子署名方式においては、次の式（１５）を満たすとき、Correct（正常）またはConsistent（一致）と呼ばれる。
【００６１】
【数８１】
2010122626.tif 000022
【００６２】
１．４．強偽造不可
ここでの強偽造不可の定義は、前記非特許文献１５および前記非特許文献１９の記載内容に従っている。
【００６３】
ここで、本発明においては、強偽造不可を定義するために、以下のような挑戦者B と攻撃者A によるゲームを考える。
【００６４】
（１）Setup：
挑戦者B は、KeyGenフェーズを実行する。Public key ＰＫとprivate key ＳＫとを生成し、Public key ＰＫを攻撃者Aへ与える。
【００６５】
（２）Signature Queries：
Signature queries M１，M２，…，Mｑが攻撃者Aから発行される。各query Mｉに対し、挑戦者Bは、Signを実行し、各query Mｉの署名σｉを生成し、σｉを攻撃者Aへ送信する。なお、各query Mｉは、M１，M２，…，Mｉ−１についての返答を受け取った後、適応的に質問して良い。
【００６６】
（３）Output：
最後に、攻撃者Aは組（M＊，σ＊）を出力する。ここで、query M＊の署名σ＊は、Verifyにおける署名文書M＊のvalidな署名であり、（M＊，σ＊）はQueryフェーズにおける（Mｉ，σｉ）ではないとする。このとき、攻撃者Aは強偽造不可ゲームに勝ったという。
【００６７】
ここで、AdvSigAを、挑戦者B と攻撃者A によるコイントスを用いた際に、攻撃者A が該ゲームに勝つ確率とする。
【００６８】
つまり、定義１として次を定義する。
（定義１）攻撃者A が署名方式を(q,t,ε)で破るとは、時間t以内に、攻撃者Aが高々q回のSignature QueriesおよびAdvSig Aが少なくともεであることと定義する。署名方式が、適応的選択文書攻撃に対する(q,t,ε)−強存在的偽造不可(強偽造不可)であるとは、強偽造不可ゲームを(q,t,ε)で破る攻撃者A がいないことと定義する。
【００６９】
１．５．鍵合意の安全性
以下の定義は、前記非特許文献９の記載内容に準拠している。次に定義されるKnown Key Security（ＫＫＳ：既知キー安全性）、Perfect Forward Secrecy（ＰＦＳ：完全フォワード秘匿性）およびKey Compromise Impersonation Secure（ＫＣＩＳ：キー漏洩なりすまし安全性）は、鍵合意についてのほとんどのプロトコルで解析される安全性である。
【００７０】
(１)ＫＫＳ：
たとえ、攻撃者がある以前のsessionにおけるagreement keyが分かっても、その攻撃者は他のsessionにおけるagreement keyを知ることができない。
【００７１】
（２）ＰＦＳ：
たとえ、すべてのprivate keyが漏洩しても、以前のsessionにおけるagreement keyの秘密には影響がない。
【００７２】
（３）ＫＣＩＳ：
あるentityのlong-term private keyが漏洩しても、攻撃者は他のentityになりすますことはできない。
【００７３】
２．本発明による実施形態
次に、本発明による電子署名方式および送信者認証機能付き鍵合意プロトコルＳＡＫＡＰのプロトコル構成（鍵合意方式）の一例について説明する。
【００７４】
２．１．本実施形態における電子署名方式
まず、本実施形態における電子署名方式の一例について説明する。本電子署名方式は、前述に定義したような(KeyGen，Sign，Verify)の３つのフェーズから構成される。
【００７５】
ここで、式（１６）はshared informationである。差し当たり、署名文書Mを式（１７）の要素と仮定するが、式（１８）に示すような衝突耐性を持つハッシュ関数Ｈを使って、領域を式（１９）のように拡張することもできる。
【００７６】
【数８２】
2010122626.tif 000023
【００７７】
【数８３】
2010122626.tif 000024
【００７８】
【数８４】
2010122626.tif 000025
【００７９】
【数８５】
2010122626.tif 000026
【００８０】
（ａ）キー生成（KeyGen）フェーズ：
Public keyは、以下のように生成される。ランダムな生成元g２ ∈Ｒ G２を選び、次の式（２０）とおく。式（２１）のsecret αから、式（２２）に示すprivate key ＳＫを生成し、式（２３）を計算する。
【００８１】
【数８６】
2010122626.tif 000027
【００８２】
【数８７】
2010122626.tif 000028
【００８３】
【数８８】
2010122626.tif 000029
【００８４】
【数８９】
2010122626.tif 000030
【００８５】
つまり、次の式（２４）、式（２５）を計算する。
【００８６】
【数９０】
2010122626.tif 000031
【００８７】
【数９１】
2010122626.tif 000032
【００８８】
加えて、アルゴリズムは、次の式（２６）に示すランダムな値u′およびランダムなn-length vector Uを選択する。ここで生成されるpublic key ＰＫとprivate key ＳＫとは、それぞれ、式（２７）となる。
【００８９】
【数９２】
2010122626.tif 000033
【００９０】
【数９３】
2010122626.tif 000034
【００９１】
（ｂ）サイン（Sign）フェーズ：
M をnビットの署名文書とし、式（２８）に示すmｊを、Mの(左から)ｊ 番目のビットとする。署名文書Mの署名σを、乱数r ∈ Zｐ*を使って、次の式（２９）とする。
【００９２】
【数９４】
2010122626.tif 000035
【００９３】
【数９５】
2010122626.tif 000036
【００９４】
（ｃ）ベリファイ(Verify)フェーズ：
署名はpublic key ＰＫ、署名文書Mおよび署名σ＝（σ１，σ２）を使い、次の式（３０）の等式が成り立つかどうかを検証する。式（３０）の等式が成り立つとき、valid（正当）を出力し、それ以外のときinvalid（不当）を出力する。
【００９５】
【数９６】
2010122626.tif 000037
【００９６】
２．２．本実施形態におけるＳＡＫＡＰ（鍵合意方式）
次に、本実施形態における送信者認証機能付き鍵合意プロトコル（ＳＡＫＡＰ：Sender
Authenticated Key Agreement Protocols）つまり鍵合意方式の一例について説明する。本ＳＡＫＡＰは、前述の２．１項において説明した電子署名方式から構成され、プロトコルは（Key Generation，Message Generation，Verification，Key Agreement）の４つのフェーズから構成される。
【００９７】
ランダムな生成元g２ ∈Ｒ G２を選び、式（３１）とおく。加えて、アルゴリズムは、式（３２）に示すようなランダムな値u′およびランダムなn-length vector Uを選択する。ここで、式（３３）をshared informationとし、A,B,Cをプロトコルのentityとする。
【００９８】
【数９７】
2010122626.tif 000038
【００９９】
【数９８】
2010122626.tif 000039
【０１００】
【数９９】
2010122626.tif 000040
【０１０１】
（ａ）キー生成（Key Generation）フェーズ：
entity A（エンティティA）は、secret ａ∈Ｒ Zｐ＊から式（３４）に示す（long-term）private key ＳＫＡを生成し、（long-term）public keyとして式（３５）に示すＰＫＡを計算する。
【０１０２】
【数１００】
2010122626.tif 000041
【０１０３】
【数１０１】
2010122626.tif 000042
【０１０４】
つまり、次の式（３６）、式（３７）を計算する。
【０１０５】
【数１０２】
2010122626.tif 000043
【０１０６】
【数１０３】
2010122626.tif 000044
【０１０７】
ここで、ＰＫＡは、ある第三者信頼機関（ＴＴＰ：Trusted Third Party）によって認証される。同様に、entity Bおよびentity Cについても、それぞれ、（ＳＫＢ，ＰＫＢ）および（ＳＫＣ，ＰＫＣ）を計算する。entity A，B，Cそれぞれのprivate key ＳＫおよびpublic key ＰＫの生成結果をまとめて表１に示す。
【０１０８】
【表１】
2010122626.tif 000045
【０１０９】
（ｂ）メッセージ生成（Message Generation）フェーズ：
差し当たり、署名文書Mを式（３８）の要素と仮定するが、式（３９）に示すような衝突耐性を持つハッシュ関数Ｈを使って、領域を式（４０）のように拡張することもできる。
【０１１０】
【数１０４】
2010122626.tif 000046
【０１１１】
【数１０５】
2010122626.tif 000047
【０１１２】
【数１０６】
2010122626.tif 000048
【０１１３】
entity
A(エンティティA)について考える。entity Aの文書MＡをｎビット署名文書とし、式（４１）に示すmＡ，ｊをMＡの（左から）ｊ番目のビットとする。Aは、short-term secret rＡ∈Ｒ Zｐ＊から、次の式（４２）のように合意文書を生成する。
【０１１４】
【数１０７】
2010122626.tif 000049
【０１１５】
【数１０８】
2010122626.tif 000050
【０１１６】
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へ送信した合意文書の生成結果をまとめて表２に示す。ここで、各entityの合意文書は、前述の２．１．項において説明した電子署名方式の署名に対応することに注意を要する。
【０１１７】
【表２】
2010122626.tif 000051
【０１１８】
（ｃ）ベリフィケーション（Verification）フェーズ：
entity Aは、entity Bとentity Cとからそれぞれ受け取った合意文書（B１，B２）と合意文書（C１，C２）とを使って、次の式（４３）が成り立つかどうかを検証する。
【０１１９】
【数１０９】
2010122626.tif 000052
【０１２０】
式（４３）に示す２つの等式が成り立つとき、valid（正当）を出力し、それ以外の場合、invalid（不当）を出力する。entity Bおよびentity CにおけるVerificationもentity Aの場合と同様である。各entity A，B，Cそれぞれにおける検証内容をまとめて表３に示す。
【０１２１】
【表３】
2010122626.tif 000053
【０１２２】
（ｄ）キー・アグリーメント（Key Agreement：鍵合意）フェーズ：
entity Aは、rＡ，B１，C１から、次の式（４４）によりagreement key ZＡを計算する。同様に、entity Bおよびentity Cも、それぞれZＢとZＣを計算する。各entity A，B，Cそれぞれにおけるagreement keyをまとめて表４に示す。
【０１２３】
【数１１０】
2010122626.tif 000054
【０１２４】
【表４】
2010122626.tif 000055
【０１２５】
したがって、entity A，B，Cの間の三者間agreement keyは、次の式（４５）となる。
【０１２６】
【数１１１】
2010122626.tif 000056
【０１２７】
３．安全性および効率性の証明
次に、２項にて説明した本実施形態における電子署名方式およびプロトコルＳＡＫＡＰ（鍵合意方式）の安全性および効率性について、さらに説明する。つまり、本実施形態における電子署名方式およびＳＡＫＡＰの安全性（強偽造不可，Private KeyのKnowledge，Known Key Security（ＫＫＳ），Perfect Forward Secrecy（ＰＦＳ）、Key Compromise Impersonation Secure（ＫＣＩＳ））に対する５つの定理、１つの系、および、２つの補題について、それぞれが成立し、さらに、効率性を有することを説明する。
【０１２８】
３．１．強偽造不可
（定理１）g１:＝f(g２)となる条件で、(q１，t１，ε１)−仮定１が成り立つと仮定する。そのとき、前述の本実施形態の電子署名方式は、(q，t，ε)−強偽造不可であり、次の式（４６）を満たす。ここで，T はG２におけるべき剰余計算１回にかかる最大時間とする。
【０１２９】
【数１１２】
2010122626.tif 000057
【０１３０】
（証明）後述する補題１と補題２とから、式（４７）を得ることができる。よって、定理１は証明される。
【０１３１】
【数１１３】
2010122626.tif 000058
【０１３２】
（補題１）g１:＝f(g２)となる条件で、G２上の（t０，ε０）−ＣＤＨ仮定、および、（q１，t１，ε１）−仮定１が成り立つと仮定する。そのとき、本実施形態における電子署名方式は（q，t，ε）−強偽造不可であり、式（４８）を満たす。ここで、TはG２におけるべき剰余計算１回にかかる最大時間とする。
【０１３３】
【数１１４】
2010122626.tif 000059
【０１３４】
次に、以下のアウトラインに沿って、前述した本実施形態の電子署名方式に関する安全性つまり補題１の証明を行う。
【０１３５】
まず、前述した本実施形態の電子署名方式の安全性を破る攻撃者A の存在および仮定１のチャレンジを受け取る挑戦者B の存在を仮定する。攻撃者Aと挑戦者B とは強偽造不可ゲームを実行し、攻撃者Aはvalidとなる(文書，署名)の一組を出力する。次に、挑戦者B は仮定１においてvalidとなるレスポンスを計算する。ここで、攻撃者Aの出力は、ＣＤＨ仮定に矛盾してはならない。
【０１３６】
（安全性の証明）
本実施形態の電子署名方式の安全性を、(q，t，ε)で破る攻撃者Aの存在を仮定する。ここで、仮定１ゲームを行うシミュレータB を構成する。シミュレータB は、式（４９）に示す仮定１ゲームのチャレンジを受け取る。
【０１３７】
【数１１５】
2010122626.tif 000060
【０１３８】
式（４９）において、α，rｉは、次の式（５０）の通りである。また、シミュレータB は、攻撃者Aと以下の手順を実行する。
【０１３９】
【数１１６】
2010122626.tif 000061
【０１４０】
Ａ．Simulator Description（シミュレータの構成）
Setup（セットアップ）：
シミュレータB は、まず、式（５１）の乱数から式（５２）の情報を生成し、Aに対して、(G１, G2, GT, p, e, f)および式（５３）の情報を送信する。
【０１４１】
【数１１７】
2010122626.tif 000062
【０１４２】
【数１１８】
2010122626.tif 000063
【０１４３】
【数１１９】
2010122626.tif 000064
【０１４４】
（１）シグネチャ・クエリ（Signature Queries）：
攻撃者A は、シミュレータBに対し、適応的に、Signature Queries M１,M２，…，Mｑを行う。式（５４）に対し、次の式（５５）と仮定する。
【０１４５】
【数１２０】
2010122626.tif 000065
【０１４６】
【数１２１】
2010122626.tif 000066
【０１４７】
(Ａ−１)：
もし、式（５６）が成立するならば、シミュレータB はこのゲームを中断する。
【０１４８】
【数１２２】
2010122626.tif 000067
【０１４９】
(Ａ−２)：
式（５６）が成立しないその他の場合(すなわち、式（５７）の場合)、シミュレータB はゲームを中断せずに、Mｉに対応するσｉ＝(σｉ,１，σｉ,２)を、次の式（５８）、式（５９）のように、生成し、それをAへ送信する。
【０１５０】
【数１２３】
2010122626.tif 000068
【０１５１】
【数１２４】
2010122626.tif 000069
【０１５２】
【数１２５】
2010122626.tif 000070
【０１５３】
なお、式（５９）において、sｉは、次の式（６０）で与えられる。
【０１５４】
【数１２６】
2010122626.tif 000071
【０１５５】
式（５８）のすべてのr１，r２，…，rｑ ∈Ｒ Zｐ＊を消去することにより、式（５９）のすべてのs１，s２，…，sｑ ∈Ｒ Zｐ＊は乱数と看做すことができることに注意を要する。
【０１５６】
（２）アウトプット（Output）：
攻撃者Aは、(M＊，σ＊)を出力する。ただし、式（６１）に示すσ＊は、M＊に対するvalidな署名であり、次の式（６２）の関係にある。
【０１５７】
【数１２７】
2010122626.tif 000072
【０１５８】
【数１２８】
2010122626.tif 000073
【０１５９】
（３）アーティフィシャル・アボート（Artificial Abort）：
式（６３）に示す文書M＊に対し、式（６４）と仮定する。
【０１６０】
【数１２９】
2010122626.tif 000074
【０１６１】
【数１３０】
2010122626.tif 000075
【０１６２】
ここで、次の式（６５）であり、さらに、式（６６）が成立するならば、シミュレータB はこのゲームを強制的に中断する。
【０１６３】
【数１３１】
2010122626.tif 000076
【０１６４】
【数１３２】
2010122626.tif 000077
【０１６５】
Ｂ．シミュレーション結果の分析
攻撃者A は、式（６７）が成立するときとして、前述の（Ａ−１）に示すような中断があるSimulator Descriptionゲームと、中断のない強偽造不可ゲームとを区別することができない。
【０１６６】
【数１３３】
2010122626.tif 000078
【０１６７】
その理由は、式（６８）の条件を満たす確率Pｒは、式（６９）が成立するとき、negligibleな値となるからである。ゆえに、以降では、Simulator Descriptionゲ−ムのみを考えていけば良い。
【０１６８】
【数１３４】
2010122626.tif 000079
【０１６９】
【数１３５】
2010122626.tif 000080
【０１７０】
Simulator Descriptionゲームの場合、σ＊はvalidなので、式（７０）と仮定する。なお、式（７０）において、s＊ ∈ Zｐ＊である。
【０１７１】
【数１３６】
2010122626.tif 000081
【０１７２】
（Ｂ−１）
もし、式（７１）が成立するならば、式（７２）である。そのとき、B は、式（７３）に示すあるr＊となる組を式（７４）として生成する。式（７４）に示す組は、仮定１チャレンジに対するvalidな出力となる。
【０１７３】
【数１３７】
2010122626.tif 000082
【０１７４】
【数１３８】
2010122626.tif 000083
【０１７５】
【数１３９】
2010122626.tif 000084
【０１７６】
【数１４０】
2010122626.tif 000085
【０１７７】
（Ｂ−２）
次に、式（７１）が成立しないその他の場合（すなわち、式（７５）の場合）について考える。
【０１７８】
【数１４１】
2010122626.tif 000086
【０１７９】
式（７６）の関係にある場合において、Aはεのアドバンテージを持っている。ここで、この問題は、式（７７）、式（５５）におけるH１，H２，…，Hｑ、式（６４）におけるH＊、式（７８）およびAのランダムなビット列から選ばれる。
【０１８０】
【数１４２】
2010122626.tif 000087
【０１８１】
【数１４３】
2010122626.tif 000088
【０１８２】
【数１４４】
2010122626.tif 000089
【０１８３】
また、式（７９）と式（８０）とは、式（８１）および関係式（５５）、（６４）から、Aによって選ばれる。
【０１８４】
【数１４５】
2010122626.tif 000090
【０１８５】
【数１４６】
2010122626.tif 000091
【０１８６】
【数１４７】
2010122626.tif 000092
【０１８７】
また、式（８２）の計算から、Bは、式（８３）を解くためのεのアドバンテージを持つ。ここで、この問題は、式（８４）およびAのランダムなビット列から選ばれる。
【０１８８】
【数１４８】
2010122626.tif 000093
【０１８９】
【数１４９】
2010122626.tif 000094
【０１９０】
【数１５０】
2010122626.tif 000095
【０１９１】
（Ｂ−２．１）
まず、式（８５）と仮定する。
【０１９２】
【数１５１】
2010122626.tif 000096
【０１９３】
（Ｂ−２．１．１）
r＊ ＝ rｋを満たす数k ∈ {1，2，…，q}が存在すると仮定する。式（７６）において、もし、Aが、すべてのsｉ(i＝1，2，…，q)および式（８６）に示すg２αを知っているならば、式（７６）から式（８７）を消去することができる。
【０１９４】
【数１５２】
2010122626.tif 000097
【０１９５】
【数１５３】
2010122626.tif 000098
【０１９６】
また、式（８８）が成立するので、出力の第２成分を式（８９）に置き換え、第３成分を消去する。
【０１９７】
【数１５４】
2010122626.tif 000099
【０１９８】
【数１５５】
2010122626.tif 000100
【０１９９】
ゆえに、A は、式（９０）を解くためのアドバンテージεを持つ。ここで、この問題は、式（９１）、式（５５）におけるH１，H２，…，Hｑ、式（６４）におけるH＊およびA のランダムなビット列から選ばれる。
【０２００】
【数１５６】
2010122626.tif 000101
【０２０１】
【数１５７】
2010122626.tif 000102
【０２０２】
ここで、ｉ=1，2，…，qに対して、式（９２）と置く。
【０２０３】
【数１５８】
2010122626.tif 000103
【０２０４】
また、式（９３）が成立するので、A は式（９４）から式（９５）を計算することができる。
【０２０５】
【数１５９】
2010122626.tif 000104
【０２０６】
【数１６０】
2010122626.tif 000105
【０２０７】
【数１６１】
2010122626.tif 000106
【０２０８】
よって、式（９５）に示す各パラメータを式（９０）から消去する。また、式（９０）において、式(９６)を式（９７）へ置き換えることにより、A は、式（９８）を解くためのアドバンテージεを持つ。
【０２０９】
【数１６２】
2010122626.tif 000107
【０２１０】
【数１６３】
2010122626.tif 000108
【０２１１】
【数１６４】
2010122626.tif 000109
【０２１２】
式（９９）と仮定する。式（１００）に示すｙ′を式（９０）から消去したため，h をZｐ＊の乱数と看做して良い。
【０２１３】
【数１６５】
2010122626.tif 000110
【０２１４】
【数１６６】
2010122626.tif 000111
【０２１５】
アーティフィシャル・アボート（Artificial Abort）から式（１０１）が成り立つことから、前述の問題は、A が、式（１０２）を解くのにεのアドバンテージを持つことに等しい。ここで、この問題は、式（１０３）およびAのランダムなビット列から選ばれる。
【０２１６】
【数１６７】
2010122626.tif 000112
【０２１７】
【数１６８】
2010122626.tif 000113
【０２１８】
【数１６９】
2010122626.tif 000114
【０２１９】
F. Baoらによる“Variations of Diffie-Hellman problem”（Proc. ICICS 2003, Springer-Verlag, 2003）の記載内容から、これは、Aが、式（１０４）を解くのにεのアドバンテージを持つことに等しい。
【０２２０】
【数１７０】
2010122626.tif 000115
【０２２１】
これは、A が、ＣＤＨ問題をnon-negligibleな確率で解くことができることを意味している。
【０２２２】
（Ｂ−２．１．２）
r＊ ＝ rｋを満たす数k ∈ {1，2，…，q}が存在しないその他の場合(すなわち、式（１０５）の場合)、式（１０６）に示す組は、仮定Ｉチャレンジのvalid（正当）な出力である。
【０２２３】
【数１７１】
2010122626.tif 000116
【０２２４】
【数１７２】
2010122626.tif 000117
【０２２５】
（Ｂ−２．２）
式（８５）が成り立たないその他の場合（すなわち、式（１０７）の場合）、式（１０８）を式（１０９）となるすべての添字集合とする。そのとき、式（１１０）から、r＊ は式（１１１）となる。
【０２２６】
【数１７３】
2010122626.tif 000118
【０２２７】
【数１７４】
2010122626.tif 000119
【０２２８】
【数１７５】
2010122626.tif 000120
【０２２９】
【数１７６】
2010122626.tif 000121
【０２３０】
【数１７７】
2010122626.tif 000122
【０２３１】
｛ｊ１，ｊ２，…ｊｑ−ｃ｝を｛1，2，…，q｝における｛i１，i２，…iｃ｝の補集合とする。そのとき、式（１１２）が得られる。
【０２３２】
【数１７８】
2010122626.tif 000123
【０２３３】
（Ｂ−２．２．１）
式（１１３）であり、かつ、r＊=rｋとなる数k∈{ｊ１，j２，…，jｑ−ｃ}が存在すると仮定する。このとき、（Ｂ−２．１．１）項にて説明したように、AはＣＤＨ問題をnon-negligibleな確率で解くことができる。
【０２３４】
【数１７９】
2010122626.tif 000124
【０２３５】
（Ｂ−２．２．２）
式（１１３）ではないか、あるいは、r＊=rｋとなる数k∈{ｊ１，j２，…，jｑ−ｃ}が存在しないその他の場合（すなわち、ｃ＝ｑ、あるいは、式（１１４）の場合）、式（１１５）に示す組は、仮定１チャレンジのvalid(正当)な出力である。
【０２３６】
【数１８０】
2010122626.tif 000125
【０２３７】
【数１８１】
2010122626.tif 000126
【０２３８】
シミュレーション（simulation）において、式（１１６）のいずれも満たさない場合の確率Pｒは、次の式（１１７）で与えられる。
【０２３９】
【数１８２】
2010122626.tif 000127
【０２４０】
【数１８３】
2010122626.tif 000128
【０２４１】
よって、本発明に係わる電子署名方式S においては、式（１１８）が成立する。
【０２４２】
【数１８４】
2010122626.tif 000129
【０２４３】
以上の（Ｂ−１）および（Ｂ−２）の項における説明から、式（１１９）に示す確率Pｒ (≧ε)は、少なくとも、式（１１８）の左辺の確率Pｒより高いということができる。事象A１，A２に対し、式（１２０）であるので、式（１２１）である。
【０２４４】
【数１８５】
2010122626.tif 000130
【０２４５】
【数１８６】
2010122626.tif 000131
【０２４６】
【数１８７】
2010122626.tif 000132
【０２４７】
これは、(t０，ε０)−ＣＤＨ仮定、または、(q１，t１，ε１)−仮定１に矛盾する。よって、本発明に係わる電子署名方式は、(ｑ，t，ε)−強偽造不可安全である。
【０２４８】
もし、A が、前述のSimulator Descriptionゲームにおいて、時間t 内の確率ε で、validな偽造を出力したならば、それは、B が仮定１ゲームについて、または、A がＣＤＨゲームについて、式（１２２）に示す時間以内に、式（１２３）に示す確率で成功することを意味している。
【０２４９】
【数１８８】
2010122626.tif 000133
【０２５０】
【数１８９】
2010122626.tif 000134
【０２５１】
よって、式（１２４）に示す仮定が必要である。これは、式（１２５）であることを意味している。以上より、前述した補題１は証明された。
【０２５２】
【数１９０】
2010122626.tif 000135
【０２５３】
【数１９１】
2010122626.tif 000136
【０２５４】
次に、以下に示す補題２について証明する。
（補題２）（q１，t１，ε１）−仮定１が成り立つと仮定する。そのとき、G２上の（t０，ε０）−ＣＤＨ仮定は成り立つ。ここで、t０≦t１およびε０≧ε１であり、TはG２におけるべき剰余計算１回にかかる最大時間とする。
【０２５５】
（証明）Aを（t０，ε０）−ＣＤＨ仮定を破る攻撃者とする。もし、Aが、式（１２６）に示す情報を受け取ったとき、そのAは、式（１２７）の入力から式（１２８）を計算することができる。
【０２５６】
【数１９２】
2010122626.tif 000137
【０２５７】
【数１９３】
2010122626.tif 000138
【０２５８】
【数１９４】
2010122626.tif 000139
【０２５９】
ここで、sおよびgを式（１２９）とする。Aは式（１３０）から式（１３１）を計算し、式（１３２）に示すあるr＊から式（１３３）を生成する。これは（q１，t１，ε１）−仮定１に矛盾する。
【０２６０】
【数１９５】
2010122626.tif 000140
【０２６１】
【数１９６】
2010122626.tif 000141
【０２６２】
【数１９７】
2010122626.tif 000142
【０２６３】
【数１９８】
2010122626.tif 000143
【０２６４】
【数１９９】
2010122626.tif 000144
【０２６５】
３．２．Private KeyのKnowledge（プライベートキー知識）
（定理２）もし、攻撃者が、あるshort-term secretおよびその合意文書（の第２成分）を持つならば、その攻撃者は、対応するprivate keyを抽出することができる。
【０２６６】
（証明）もし、攻撃者が、Aのshort-term secret ｒ∈Ｚｐ＊と式（１３４）に示すA２を知っているならば、攻撃者は、式（１３５）の計算から、対応するprivate key ｇ２ａを抽出することができる。よって、定理２は成り立つ。
【０２６７】
【数２００】
2010122626.tif 000145
【０２６８】
【数２０１】
2010122626.tif 000146
【０２６９】
(系１)
本実施形態のＳＡＫＡＰプロトコルにおいて、参加者Ｐが式（１３６）の情報をentity Aへ送信すると仮定する。さらに、Aは、（M，A１，A２，０）および自分自身のprivate key ｇ２ａ∈ Ｚｐ＊から生成した式（１３７）の文書を送信すると仮定する。そのとき、参加者ＰがA２を知ることと、参加者ＰがAのprivate keyを得ることとは必要十分の関係にある。
【０２７０】
【数２０２】
2010122626.tif 000147
【０２７１】
【数２０３】
2010122626.tif 000148
【０２７２】
前記非特許文献１５、前記非特許文献１６、前記非特許文献１７において提案された署名方式から構成されたＳＡＫＡＰは、プロトコルの各entityのprivate keyに２つのパラメータを使う。このようなプロトコルは、entityと攻撃者による結託攻撃に対し、脆弱性を持つ。
【０２７３】
例えば、前記非特許文献１５の場合を考えてみる。ここで、GとGＴとを十分大きな素数pの位数を持つ乗法巡回群とする。gをGのランダムな生成元とする。また、式（１３８）を双線形写像とする。ＳＡＫＡＰは三者のentity A，B，C間で合意するものと仮定する。まず、entity Aは次の４つのフェーズを実行する。
【０２７４】
【数２０４】
2010122626.tif 000149
【０２７５】
（ａ）ＡのKey Generationフェーズ：long-term private key（xＡ，yＡ）∈Ｒ（Zｐ＊）２を生成し、対応するpublic key（PＡ，QＡ）：＝（gｘＡ，gｙＡ）∈ G２を計算する。
【０２７６】
（ｂ）AのMessage Generationフェーズ：ある文書MＡ∈Zｐ＊、および、tＡ：＝xＡ+mＡ＋yＡrＡ∈Zｐに対し、式（１３９）を生成する。Aは、BとCとへ（ｒＡ，A１）を送信する。
【０２７７】
【数２０５】
2010122626.tif 000150
【０２７８】
（ｃ）AのVerificationフェーズ：式（１４０）が成り立つかどうかを検証する。
【０２７９】
【数２０６】
2010122626.tif 000151
【０２８０】
（ｄ）AのKey Agreementフェーズ：式（１４１）を計算する。
【０２８１】
【数２０７】
2010122626.tif 000152
【０２８２】
entity Bおよびentity Cについても同様に４つのフェーズを行う。entity A，B，Cのagreement keyは、次の式（１４２）である。
【０２８３】
【数２０８】
2010122626.tif 000153
【０２８４】
本プロトコルにおいて、entity Aと攻撃者とは以下の結託攻撃を成功させることができる。Message Generationにおいて、攻撃者はt′∈ Zｐ＊を生成し、それをentity Aへ送信する。entity Aは、式（１４３）を計算し、計算結果を他のentity B,Cへ送信する。そのとき、entity Bおよびentity C（および外部の参加者）は（r′，A１′）をAのvalidな文書と信じてしまう。しかしながら、式（１４４）に示すagreement keyは、実際には、攻撃者、entity B， Cの三者間で合意されている。
【０２８５】
【数２０９】
2010122626.tif 000154
【０２８６】
【数２１０】
2010122626.tif 000155
【０２８７】
３．３．Known Key Security（ＫＫＳ：既知キー安全性）
本実施形態においては、もし、任意の攻撃者Aが時間t内で、次の式（１４５）を満たすとき、ＳＡＫＡＰは、（q，t，ε）−ＫＫＳを持つという。ここで、この確率Pｒは、式（１４６）、式（５５）における式（１４７）、R ∈Ｒ GＴ，j（1≦j≦q-1）およびAのランダムなビット列から選ばれる。
【０２８８】
【数２１１】
2010122626.tif 000156
【０２８９】
【数２１２】
2010122626.tif 000157
【０２９０】
【数２１３】
2010122626.tif 000158
【０２９１】
（q，t，ε）−ＫＫＳは、Aが、式（１４８）から式（１４９）についての如何なる部分情報も得ることができないことを意味している。
【０２９２】
【数２１４】
2010122626.tif 000159
【０２９３】
【数２１５】
2010122626.tif 000160
【０２９４】
（定理３）g１：＝f（g２）となる条件で、（t０，ε０）−仮定２が成り立つと仮定する。そのとき、本発明に係わるＳＡＫＡＰプロトコルは（q，t，ε）−Known Key Securityを持つ。ここで、t≦t０およびε≧ε０である。
【０２９５】
（証明）Aを（q，t，ε）−ＫＫＳを破る攻撃者とする。証明を簡単にするために、private key g２ａ，g２ｂ，ｇ２ｃは漏洩していると仮定する。また、y′＝y１＝y２＝…＝yｎ＝１と仮定する。ここで、前述の式（１４５）の中から式(１５０)を消去し、式（１５１）に示す成分を式（１５２）に置き換える。
【０２９６】
【数２１６】
2010122626.tif 000161
【０２９７】
【数２１７】
2010122626.tif 000162
【０２９８】
【数２１８】
2010122626.tif 000163
【０２９９】
そのとき、式（１５３）が成立する。ここで、各rＡ，ｉ，rＢ，ｉ，rＣ，ｉ（ｉ=1,2,…，q）はランダムであるから、式（１５３）の不等式は（t０、ε０）−仮定２に矛盾する。よって、定理２は成り立つ。
【０３００】
【数２１９】
2010122626.tif 000164
【０３０１】
３．４．Perfect Forward Secrecy（ＰＦＳ：完全フォワード秘匿性）
本実施形態において、ＳＡＫＡＰプロトコルのprivate keyとは、g２ａ，g２ｂ，g２ｃを意味している。もし、任意の攻撃者Aが、時間t以内で、式（１５４）の条件を満たすとき、ＳＡＫＡＰは、（t，ε）−ＰＦＳを持つという。ここで、この確率Pｒは、式（１５５）、前述の式（５５）における式（１５６）、R ∈Ｒ GＴおよびAのランダムなビット列から選ばれる。
【０３０２】
【数２２０】
2010122626.tif 000165
【０３０３】
【数２２１】
2010122626.tif 000166
【０３０４】
【数２２２】
2010122626.tif 000167
【０３０５】
（t，ε）−ＰＦＳは、Aが、式（１５７）から式（１５８）についての如何なる部分惰報も得ることができないことを意味している。
【０３０６】
【数２２３】
2010122626.tif 000168
【０３０７】
【数２２４】
2010122626.tif 000169
【０３０８】
（定理４）g１:=f(g２)となる条件で、（t０，ε０）−仮定２が成り立つと仮定する。そのとき、本発明に係わるＳＡＫＡＰプロトコルは（t，ε）−Perfect Forward Secrecyを持つ。ここで、t≦t０およびε≧ε０である。
【０３０９】
（証明）Aを（t，ε）−ＰＦＳを破る攻撃者とする。ｙ′＝ｙ１＝ｙ２＝…＝ｙｎ＝１と仮定する。ここで、前述の式（１５４）の中から式(１５９)を消去し、式（１６０）に示す成分を式（１６１）に置き換える。また、式（１６２）に示す組は、式（１６３）に無関係なので、これらの成分を式（１５４）から消去する。これは、（ｔ０，ε０）−仮定２に矛盾する。よって、定理４は成り立つ。
【０３１０】
【数２２５】
2010122626.tif 000170
【０３１１】
【数２２６】
2010122626.tif 000171
【０３１２】
【数２２７】
2010122626.tif 000172
【０３１３】
【数２２８】
2010122626.tif 000173
【０３１４】
【数２２９】
2010122626.tif 000174
【０３１５】
３．５．Key Compromise Impersonation Secure（ＫＣＩＳ：キー漏洩なりすまし安全性）
本実施形態のＳＡＫＡＰプロトコルにおけるＫＣＩＳの失敗は、entity Bのprivate key g２ｂを知ったentity Aが、entity Cの正当な（C１，Ｃ２）を生成することができることを意味している。より正確には、もし、任意の攻撃者Aが、時間ｔ以内に、式（１６４）の条件を満たすとき、プロトコルは（q，t，ε）−ＫＣＩＳであるという。ここで、この確率Pｒは、式（１６５）、前述の式（５５）における式（１６６）、前述の式(６４）におけるHＣ，＊、式（１６７）およびAのランダムなビット列から選ばれる。
【０３１６】
【数２３０】
2010122626.tif 000175
【０３１７】
【数２３１】
2010122626.tif 000176
【０３１８】
【数２３２】
2010122626.tif 000177
【０３１９】
【数２３３】
2010122626.tif 000178
【０３２０】
（定理５）g１：＝f(g２)となる条件で、（q１，t１，ε１）−仮定１が成り立つと仮定する。そのとき、本発明に係わるＳＡＫＡＰプロトコルは、（q，t，ε）−Key Compromise Impersonation Secureである。ここで、式（１６８）の関係にある。また、TはG２におけるべき剰余計算１回にかかる最大時間とする。
【０３２１】
【数２３４】
2010122626.tif 000179
【０３２２】
（証明）Aを（q，t，ε）−ＫＣＩＳを破る攻撃者とする。y′＝y１＝y２＝…＝yｎ＝１と仮定する。そのとき、式（１６９）は、前述の式（１６４）の出力には無関係なので、この問題は、以下のように簡単にすることができる。つまり、Aは、式（１７０）を解くためのアドバンテージεを持つ。
【０３２３】
【数２３５】
2010122626.tif 000180
【０３２４】
【数２３６】
2010122626.tif 000181
【０３２５】
また、式（１７１）が成立するので、値HＣ，ｉ（ｉ＝1，2，…，q）およびHＣ，＊はZｐ＊に属している。また、Aは、これらの値を計算することができるので、式（１７２）を、それぞれ、式（１７３）へ置き換える。MＣ，＊を消去する。これは、（q１，t１，ε１）−仮定１に矛盾する。
【０３２６】
【数２３７】
2010122626.tif 000182
【０３２７】
【数２３８】
2010122626.tif 000183
【０３２８】
【数２３９】
2010122626.tif 000184
【０３２９】
もし、Aが、ＫＣＩＳの（q，t，ε）−攻撃に成功したならば、そのとき、Aは、時間t＋Ｏ（qT）以内に、確率εで、仮定１ゲームにおけるvalidな偽造の出力に成功する。よって、定理５が成り立つ。
【０３３０】
３．６．安全性と効率性
次に、本発明に係わるＳＡＫＡＰの安全性と効率性とについてさらに説明する。ここでは、本発明に係わるＳＡＫＡＰプロトコルを、従来技術として前記非特許文献１２に記載のWaters方式（これは強偽造不可ではない）ベースのプロトコルおよび前記非特許文献１９に記載のＢＳＷ（Ｂｏｎｅｈ−Ｓｈｅｎ−Ｗａｔｅｒｓ）方式ベースのプロトコルと、安全性の面と効率性の面とから比較した結果を説明する。
【０３３１】
３．６．１．安全性
表５は、ＳＡＫＡＰの安全性について、本発明に係わるＳＡＫＡＰプロトコルを、従来技術のWaters方式ベースのモデルとＢＳＷ方式ベースのモデルと比較した結果を示すものである。ここで、従来技術のWatersベースモデル、ＢＳＷベースモデルに記述している“Ｙｅｓ＊”は、それぞれの定理がある仮定の下では成り立つようであるが、フォーマルな証明がまだ与えられていないことを意味している。この表５から、本発明に係わるプロトコルの安全性は、少なくともＢＳＷベースモデルのＳＡＫＡＰと同等であり、Watersベースモデルのものよりも高いことが分かる。
【表５】
2010122626.tif 000185
【０３３２】
つまり、本発明に係わるＳＡＫＡＰプロトコルは、前記非特許文献９の中で説明されているＳＡＫＡＰプロトコルの（一般的に必要とされる）安全性を満たしている。特に、前述の定理１は、前記非特許文献９におけるNew-Legitimate-Message（新適合メッセージ）のresilience（レジリエンス）についての結果（該非特許文献９における定理１）をも包含していることに注意を要する。また、前記非特許文献９におけるSato-Okamoto-Okamoto ＳＡＫＡＰは、署名方式をベースとしていないので、Replay攻撃に対する耐性を持たない。そこでは、攻撃者は、プロトコルのあるSessionでの情報を記録しておき、後のSessionにおいて同一のあるいは異なるentityへその情報を送信する。これに対して、本発明に係わるプロトコルは、ある信頼できる第三者機関により発行されたtime stampを署名文書に含めることにより、このReplay攻撃に対する耐性を持つことが可能である。
【０３３３】
３．６．２．効率性
表６は、ＳＡＫＡＰの効率性について、ＳＡＫＡＰの各entityによって実行される計算数を、本発明に係わるＳＡＫＡＰプロトコルと、従来技術のWaters方式ベースのモデルとＢＳＷ方式ベースのモデルとで比較した結果を示している。ここで、括弧の中の和は、ＳＡＫＡＰプロトコルの各フェーズ(Message Generation，Verification，Key Agreement)それぞれにおける計算数の和を表している。
【０３３４】
例えば、一方向性同型写像ｆ：G２→G１の効率について説明する。前述したT. Saitoらによる“Candidate one-way functions on non-supersingular elliptic curves”（IEICE Trans. Fundamentals,vol.E89, pp.144-150, 2006）の文献に記載されたプロトコルの場合、E[p]は、２次元Z／ｐZ−線形空間、φはE[p]のFrobenius自己準同型写像、P，Qはφの固有ベクトルである。よって、E[p]は、式（１７４）と表すことができる。２つの群G１，G２はE[p]の部分集合である。G１は式（１７５）であり、G２はこれらのどちらでもない。同型写像ｆは、式(１７６)に示すように、E[p]から第１成分または第２成分への射影である。
【０３３５】
【数２４０】
2010122626.tif 000186
【０３３６】
【数２４１】
2010122626.tif 000187
【０３３７】
【数２４２】
2010122626.tif 000188
【０３３８】
ゆえに、一方向性同型写像ｆは、表６の他の演算に比べ著しく効率的である。以上より、本発明に係わるＳＡＫＡＰプロトコルの効率は、Watersベースモデルの場合と同程度であり、ＢＳＷベースモデルの場合よりも高いということができる。
【表６】
2010122626.tif 000189
【０３３９】
４．結論
以上に詳細に説明したように、本発明においては、ＳＡＫＡＰに利用可能な電子署名として、Waters署名（偽造不可安全）と同程度の効率性を持つ強偽造不可安全な電子署名方式のスタンダードモデルを提供している。本電子署名方式に基づいて、鍵合意方式であるＳＡＫＡＰプロトコルとして三者間ＳＡＫＡＰのスタンダードモデルを構成することができ、本プロトコルは、本発明の対象分野である署名ベースのスタンダードモデルとして安全性を満たすプロトコルの中で最も効率が良い仕組みを提供している。
【０３４０】
以上、本発明の好適実施例の構成を説明した。しかし、斯かる実施例は、本発明の単なる例示に過ぎず、何ら本発明を限定するものではないことに留意されたい。本発明の要旨を逸脱することなく、特定用途に応じて種々の変形変更が可能であることが、当業者には容易に理解できよう。例えば、本発明の実施態様は、課題を解決するための手段における構成（１）に加えて、次のような構成として表現できる。
（２）前記キー生成フェーズにおいて、ランダムな生成元g２ ∈Ｒ G２を選び、式（Ａ７）と置き、式（Ａ８）のsecret αから、式（Ａ９）に示す前記プライベートキーＳＫを生成して、式（Ａ１０）を計算することにより、Ｐ1を生成し、
【数７】
2010122626.tif 000190
【数８】
2010122626.tif 000191
【数９】
2010122626.tif 000192
【数１０】
2010122626.tif 000193
式（Ａ１１）に示すランダムな値u′およびランダムなn-length vector Uを選択した場合、生成される前記パブリックキーＰＫと前記プライベートキーＳＫとは、それぞれ、式（Ａ１２）の関係になる
【数１１】
2010122626.tif 000194
【数１２】
2010122626.tif 000195
上記（１）の電子署名システム。
（３）前記サインフェーズにおいて、前記署名文書Mをnビットとし、式（Ａ１３）に示すmｊを、前記署名文書M のｊ 番目のビットとする場合、前記署名文書Mの前記署名σを、乱数r ∈ Zｐ*を使って、式（Ａ１４）とする
【数１３】
2010122626.tif 000196
【数１４】
2010122626.tif 000197
上記（２）の電子署名システム。
（４）前記ベリファイフェーズにおいて、前記パブリックキーＰＫ、前記署名文書Mおよび前記署名σとしてσ＝（σ１，σ２）を用い、次の式（Ａ１５）の等式が成り立つかどうかを検証し、式（Ａ１５）の等式が成り立つとき、valid（正当）を出力し、成り立たないとき、invalid（不当）を出力する
【数１５】
2010122626.tif 000198
上記（３）の電子署名システム。
（５）送信者の認証機能付き鍵合意プロトコル（ＳＡＫＡＰ：Sender Authenticated Key Agreement Protocols）として、あるエンティティ（entity）Ｘ（Ｘ＝Ａ，Ｂ，Ｃ）のパブリックキーＰＫＸとプライベートキーＳＫＸとを生成するキー生成（Key Generation）フェーズと、前記エンティティＸの署名σＸを生成し、生成した前記署名σＸを付した署名文書を他のエンティティへ送信するメッセージ生成（Message Generation）フェーズと、他のエンティティから受信した前記署名文書を検証するベリフィケーション（Verification）フェーズと、他のエンティティとの合意鍵（agreement key）を算出するキー・アグリーメント（Key Agreement）フェーズとの各フェーズの演算部を備えた鍵合意システムにおいて、
G１,G２,GＴが素数p の位数を持つ乗法巡回群であり、g２はG２の生成元であり、ｆ：G２→G１が、次の式（Ａ１６）を満たす一方向性同型写像であり、e: G１×G２→GＴが、次の式（Ａ１７）を満たす双線形写像とした場合、
【数１６】
2010122626.tif 000199
【数１７】
2010122626.tif 000200
式（Ａ１８）に示す生成元g１，g２および乱数x，rｉ（i＝1,2,…,q）となる式（Ａ１９）に示す入力に対し、式（Ａ２０）に示すようなあるr＊となる式（Ａ２１）の計算、
【数１８】
2010122626.tif 000201
【数１９】
2010122626.tif 000202
【数２０】
2010122626.tif 000203
【数２１】
2010122626.tif 000204
および、エンティティX（X＝A,B,C）について、式（Ａ２２）に示す生成元g１，g２，乱数rｘおよびR∈GＴとなる式（Ａ２３）に示す入力に対し、式（Ａ２４）に示すR となるならば１を出力し、それ以外のときは０を出力する計算、
【数２２】
2010122626.tif 000205
【数２３】
2010122626.tif 000206
【数２４】
2010122626.tif 000207
のそれぞれの計算を、攻撃者が、時間t以内で、高々、あらかじめ定めた定数εの確率でしか行うことができない鍵合意システム。
（６）前記キー生成フェーズにおいて、あるエンティティAについて、secretａ∈Ｒ Zｐ＊から式（Ａ２５）に示すプライベートキーＳＫＡを生成し、パブリックキーＰＫＡとして式（Ａ２６）に示すキーを計算し、他のエンティティであるエンティティBおよびエンティティCについても、それぞれ、プライベートキーＳＫＢおよびＳＫＣ、パブリックキーＰＫＢおよびＰＫＣを、前記エンティティAと同様にして計算し、計算した前記パブリックキーＰＫＡ，ＰＫＢ，ＰＫＣそれぞれを、あらかじめ定めた第三者信頼機関によって認証する
【数２５】
2010122626.tif 000208
【数２６】
2010122626.tif 000209
上記（５）の鍵合意システム。
（７）前記メッセージ生成フェーズにおいて、ランダムな生成元g２ について、式（Ａ２７）と置き、式（Ａ２８）に示すランダムな値u′およびランダムなn-lengthのベクトルUを選択した場合であって、
【数２７】
2010122626.tif 000210
【数２８】
2010122626.tif 000211
あるエンティティAの文書MＡをｎビット署名文書とし、式（Ａ２９）に示すmＡ，ｊを該署名文書MＡのｊ番目のビットとする場合、short-term secret rＡ∈Ｒ Zｐ＊から、式（Ａ３０）のように合意文書（A１，A２）を生成し、生成した該合意文書（A１，A２）を、他のエンティティであるエンティティBおよびエンティティCに送信し、
【数２９】
2010122626.tif 000212
【数３０】
2010122626.tif 000213
かつ、エンティティBは、前記エンティティAと同様にして生成した合意文書（B１，B２）を他のエンティティであるエンティティCおよびエンティティAへ送信し、また、エンティティCは、前記エンティティAと同様にして生成した合意文書（C１，C２）を他のエンティティであるエンティティAおよびエンティティBへ送信する上記（６）の鍵合意システム。
（８）前記ベリフィケーションフェーズにおいて、あるエンティティAは、他のエンティティであるエンティティBとエンティティCとからそれぞれ受け取った前記合意文書（B１，B２）と前記合意文書（C１，C２）とを使って、次の式（Ａ３１）が成り立つかどうかを検証し、
【数３１】
2010122626.tif 000214
検証結果として、式（Ａ３１）に示す２つの等式が成り立つとき、valid（正当）を出力し、成り立たない場合、invalid（不当）を出力し、かつ、エンティティBは、前記エンティティAと同様にして、他のエンティティであるエンティティCとエンティティAとからそれぞれ受け取った合意文書（C１，C２）と合意文書（A１，A２）の検証結果を出力し、また、エンティティCは、前記エンティティAと同様にして、他のエンティティであるエンティティAとエンティティBとからそれぞれ受け取った合意文書（A１，A２）と合意文書（B１，B２）の検証結果を出力する上記（７）の鍵合意システム。
（９）前記キー・アグリーメントフェーズにおいて、あるエンティティAは、前記short-term secret rＡ，受け取った前記合意文書（B１，B２）のB１，前記合意文書（C１，C２）のC１から、次の式（Ａ３２）により、該エンティティAの合意鍵ZＡを計算し、
【数３２】
2010122626.tif 000215
かつ、他のエンティティであるエンティティB，エンティティCにおいても、前記エンティティAと同様にして、エンティティBの合意鍵ZB、エンティティCの合意鍵ZCをそれぞれ計算し、エンティティA，B，Cの間の三者間の合意鍵を、式（Ａ３３）とする
【数３３】
2010122626.tif 000216
上記（８）の鍵合意システム。
（１０）パブリックキー（Public Key）ＰＫとプライベートキー（Private Key）ＳＫとのペアを出力するキー生成（KeyGen）フェーズと、該キー生成フェーズが出力する前記プライベートキーＳＫおよび署名文書Mを入力として、署名σを返すサイン（Ｓｉｇｎ）フェーズと、前記キー生成フェーズが出力する前記パブリックキーＰＫおよび前記署名文書Mと前記サインフェーズが出力する前記署名σとの組合せ（M、σ）を入力として、valid（正当）またはinvalid（不当）を返すベリファイ（Ｖｅｒｉｆｙ）フェーズとの各フェーズを有する電子署名方法において、
G１,G２,GＴが素数p の位数を持つ乗法巡回群であり、g２はG２のランダムな生成元であり、ｆ：G２→G１が、次の式（Ａ３４）を満たす一方向性同型写像であり、e: G１×G２→GＴが、次の式（Ａ３５）を満たす双線形写像とした場合、
【数３４】
2010122626.tif 000217
【数３５】
2010122626.tif 000218
式（Ａ３６）に示す生成元g１，g２および乱数x，rｉ（i＝1,2,…,q）となる式（Ａ３７）に示す入力に対し、式（Ａ３８）に示すようなあるr＊となる式（Ａ３９）の計算を、
【数３６】
2010122626.tif 000219
【数３７】
2010122626.tif 000220
【数３８】
2010122626.tif 000221
【数３９】
2010122626.tif 000222
攻撃者が、時間t以内で、高々、あらかじめ定めた定数εの確率でしか行うことができない電子署名方法。
（１１）前記キー生成フェーズにおいて、ランダムな生成元g２ ∈Ｒ G２を選び、式（Ａ４０）と置き、式（Ａ４１）のsecret αから、式（Ａ４２）に示す前記プライベートキーＳＫを生成して、式（Ａ４３）を計算することにより、Ｐ1を生成し、
【数４０】
2010122626.tif 000223
【数４１】
2010122626.tif 000224
【数４２】
2010122626.tif 000225
【数４３】
2010122626.tif 000226
式（Ａ４４）に示すランダムな値u′およびランダムなn-length vector Uを選択した場合、生成される前記パブリックキーＰＫと前記プライベートキーＳＫとは、それぞれ、式（Ａ４５）の関係になる
【数４４】
2010122626.tif 000227
【数４５】
2010122626.tif 000228
上記（１０）の電子署名方法。
（１２）前記サインフェーズにおいて、前記署名文書Mをnビットとし、式（Ａ４６）に示すmｊを、前記署名文書M のｊ 番目のビットとする場合、前記署名文書Mの前記署名σを、乱数r ∈ Zｐ*を使って、式（Ａ４７）とする
【数４６】
2010122626.tif 000229
【数４７】
2010122626.tif 000230
上記（１１）の電子署名方法。
（１３）前記ベリファイフェーズにおいて、前記パブリックキーＰＫ、前記署名文書Mおよび前記署名σとしてσ＝（σ１，σ２）を用い、次の式（Ａ４８）の等式が成り立つかどうかを検証し、式（Ａ４８）の等式が成り立つとき、valid（正当）を出力し、成り立たないとき、invalid（不当）を出力する
【数４８】
2010122626.tif 000231
上記（１２）の電子署名方法。
（１４）送信者の認証機能付き鍵合意プロトコル（ＳＡＫＡＰ：Sender Authenticated Key Agreement Protocols）として、あるエンティティ（entity）Ｘ（Ｘ＝Ａ，Ｂ，Ｃ）のパブリックキーＰＫＸとプライベートキーＳＫＸとを生成するキー生成（Key Generation）フェーズと、前記エンティティＸの署名σＸを生成し、生成した前記署名σＸを付した署名文書を他のエンティティへ送信するメッセージ生成（Message Generation）フェーズと、他のエンティティから受信した前記署名文書を検証するベリフィケーション（Verification）フェーズと、他のエンティティとの合意鍵（agreement key）を算出するキー・アグリーメント（Key Agreement）フェーズとの各フェーズを有する鍵合意方法において、
G１,G２,GＴが素数p の位数を持つ乗法巡回群であり、g２はG２のランダムな生成元であり、ｆ：G２→G１が、次の式（Ａ４９）を満たす一方向性同型写像であり、e: G１×G２→GＴが、次の式（Ａ５０）を満たす双線形写像とした場合、
【数４９】
2010122626.tif 000232
【数５０】
2010122626.tif 000233
式（Ａ５１）に示す生成元g１，g２および乱数x，rｉ（i＝1,2,…,q）となる式（Ａ５２）に示す入力に対し、式（Ａ５３）に示すようなあるr＊となる式（Ａ５４）の計算、
【数５１】
2010122626.tif 000234
【数５２】
2010122626.tif 000235
【数５３】
2010122626.tif 000236
【数５４】
2010122626.tif 000237
および、エンティティX（X＝A,B,C）について、式（Ａ５５）に示す生成元g１，g２，乱数rｘおよびR∈GＴとなる式（Ａ５６）に示す入力に対し、式（Ａ５７）に示すR となるならば１を出力し、それ以外のときは０を出力する計算、
【数５５】
2010122626.tif 000238
【数５６】
2010122626.tif 000239
【数５７】
2010122626.tif 000240
のそれぞれの計算を、攻撃者が、時間t以内で、高々、あらかじめ定めた定数εの確率でしか行うことができない鍵合意方法。
（１５）前記キー生成フェーズにおいて、あるエンティティAについて、secretａ∈Ｒ Zｐ＊から式（Ａ５８）に示すプライベートキーＳＫＡを生成し、パブリックキーＰＫＡとして式（Ａ５９）に示すキーを計算し、他のエンティティであるエンティティBおよびエンティティCについても、それぞれ、プライベートキーＳＫＢおよびＳＫＣ、パブリックキーＰＫＢおよびＰＫＣを、前記エンティティAと同様にして計算し、計算した前記パブリックキーＰＫＡ，ＰＫＢ，ＰＫＣそれぞれを、あらかじめ定めた第三者信頼機関によって認証する
【数５８】
2010122626.tif 000241
【数５９】
2010122626.tif 000242
上記（１４）の鍵合意方法。
（１６）前記メッセージ生成フェーズにおいて、ランダムな生成元g２ について、式（Ａ６０）と置き、式（Ａ６１）に示すランダムな値u′およびランダムなn-lengthのベクトルUを選択した場合であって、
【数６０】
2010122626.tif 000243
【数６１】
2010122626.tif 000244
あるエンティティAの文書MＡをｎビット署名文書とし、式（Ａ６２）に示すmＡ，ｊを該署名文書MＡのｊ番目のビットとする場合、short-term secret rＡ∈Ｒ Zｐ＊から、式（Ａ６３）のように合意文書（A１，A２）を生成し、生成した該合意文書（A１，A２）を、他のエンティティであるエンティティBおよびエンティティCに送信し、
【数６２】
2010122626.tif 000245
【数６３】
2010122626.tif 000246
かつ、エンティティBは、前記エンティティAと同様にして生成した合意文書（B１，B２）を他のエンティティであるエンティティCおよびエンティティAへ送信し、また、エンティティCは、前記エンティティAと同様にして生成した合意文書（C１，C２）を他のエンティティであるエンティティAおよびエンティティBへ送信する上記（１５）の鍵合意方法。
（１７）前記ベリフィケーションフェーズにおいて、あるエンティティAは、他のエンティティであるエンティティBとエンティティCとからそれぞれ受け取った前記合意文書（B１，B２）と前記合意文書（C１，C２）とを使って、次の式（Ａ６４）が成り立つかどうかを検証し、
【数６４】
2010122626.tif 000247
検証結果として、式（Ａ６４）に示す２つの等式が成り立つとき、valid（正当）を出力し、成り立たない場合、invalid（不当）を出力し、かつ、エンティティBは、前記エンティティAと同様にして、他のエンティティであるエンティティCとエンティティAとからそれぞれ受け取った合意文書（C１，C２）と合意文書（A１，A２）の検証結果を出力し、また、エンティティCは、前記エンティティAと同様にして、他のエンティティであるエンティティAとエンティティBとからそれぞれ受け取った合意文書（A１，A２）と合意文書（B１，B２）の検証結果を出力する上記（１６）の鍵合意方法。
（１８）前記キー・アグリーメントフェーズにおいて、あるエンティティAは、前記short-term secret rＡ，受け取った前記合意文書（B１，B２）のB１，前記合意文書（C１，C２）のC１から、次の式（Ａ６５）により、該エンティティAの合意鍵ZＡを計算し、
【数６５】
2010122626.tif 000248
かつ、他のエンティティであるエンティティB，エンティティCにおいても、前記エンティティAと同様にして、エンティティBの合意鍵ZB、エンティティCの合意鍵ZCをそれぞれ計算し、エンティティA，B，Cの間の三者間の合意鍵を、式（Ａ６６）とする
【数６６】
2010122626.tif 000249
上記（１７）の鍵合意方法。
（１９）前記課題を解決する手段における（１）及び前記（２）乃至（４）に記載の電子署名システムをコンピュータシステムとして構築したことを特徴とする電子署名システム。
（２０）前記（５）乃至（９）に記載の鍵合意システムをコンピュータシステムとして構築したことを特徴とする鍵合意システム。
（２１）前記（１０）乃至（１３）に記載の電子署名方法を、コンピュータにより実行可能なプログラムとして実施することを特徴とする電子署名プログラム。
（２２）前記（１４）乃至（１８）に記載の鍵合意方法を、コンピュータにより実行可能なプログラムとして実施することを特徴とする鍵合意プログラム。
（２３）前記（２１）に記載の電子署名プログラムをコンピュータにより読取可能な記録媒体に記録することを特徴とするプログラム記録媒体。
（２４）前記（２２）に記載の鍵合意プログラムをコンピュータにより読取可能な記録媒体に記録することを特徴とするプログラム記録媒体。