(57)【要約】【課題】ランダムオラクルを仮定しない“強” 偽造不可安全なＩＤベース署名方式を提供する。【解決手段】セキュリティパラメータを入力しシステムパラメータ、マスターキーを返すセットアップフェーズと、前記システムパラメータおよび前記マスターキーおよび任意のＩＤを入力しプライベートキーを返すエクストラクトフェーズと、文書、前記プライベートキーおよび前記システムパラメータを入力し署名を出力するサインフェーズ、および、前記文書、前記ＩＤ、前記署名および前記システムパラメータを入力し正常または異常を返すベリファイフェーズとの各フェーズを有する構成で、攻撃者によりパブリックキーとして発行されるID＊、文書M＊について作成された署名σ＊の組（ID＊,M＊,σ＊）に関し、エクストラクト・クエリにおけるすべてのIDiに対しID＊≠IDiとし、シグネチャ・クエリにおけるすべての（IDi,Mi,σi）に対し（ID＊,M＊,σ＊）≠（IDi,Mi,σi）となる仕組みを実現する。【選択図】なし【特許請求の範囲】
【請求項１】
セキュリティパラメータを入力としてシステムパラメータおよびマスターキーを返すセットアップ（Ｓｅｔｕｐ）フェーズと、該セットアップフェーズが出力する前記システムパラメータおよび前記マスターキーおよび任意のＩＤを入力としてプライベートキーを返すエクストラクト（Ｅｘｔｒａｃｔ）フェーズと、文書、前記エクストラクトフェーズが出力する前記プライベートキーおよび前記セットアップフェーズが出力する前記システムパラメータを入力として、署名を出力するサイン（Ｓｉｇｎ）フェーズ、および、前記文書、前記ＩＤ、前記サインフェーズが出力する前記署名および前記セットアップフェーズが出力する前記システムパラメータを入力として、正常（ｖａｌｉｄ）または異常（ｉｎｖａｌｉｄ）のいずれかを返すベリファイ（Ｖｅｒｉｆｙ）フェーズとの各フェーズの演算部を備えたＩＤベース署名システムにおいて、
G１,G２,GＴが素数p の位数を持つ乗法巡回群であり、g２はG２の生成元であり、ｆ：G２→G１が、次の式（Ａ１）を満たす一方向性同型写像であり、e: G１×G２→GＴが、次の式（Ａ２）を満たす双線形写像とした場合、
【数１】
2010060716.tif 000209
【数２】
2010060716.tif 000210
ランダムな生成元g１ ∈R G１， g２ ∈R G２およびランダムなx, y ∈R Zｐ＊に対する入力として、次の式（Ａ３）に示すg１ｘｙの計算、
【数３】
2010060716.tif 000211
ランダムな生成元g１∈R G１，g２∈R G２および乱数x，r１，r２，…，rｑ∈R Zｐ*となる次の式（Ａ４）に示す入力に対し、式（Ａ５）に示すあるr＊となる式（Ａ６）の計算、
【数４】
2010060716.tif 000212
【数５】
2010060716.tif 000213
【数６】
2010060716.tif 000214
および、ランダムな生成元g１∈R G１，g２∈R G２および乱数x，r１，r２，…，rｑ∈R Zｐ*となる次の式（Ａ７）に示す入力に対し、式（Ａ８）に示すあるr＊となる式（Ａ９）の計算、
【数７】
2010060716.tif 000215
【数８】
2010060716.tif 000216
【数９】
2010060716.tif 000217
のそれぞれの計算を、攻撃者が、時間t以内で、高々、あらかじめ定めた定数εの確率でしか行うことができないことを特徴とするＩＤベース署名システム。
【請求項２】
前記セットアップフェーズにおいて、十分大きな素数の位数p を持つ乗法巡回群G１，G２，GＴ，一方向性同型写像f : G２→ G１ (g１：＝ f(g２))および双線形写像e： G１ ×G２→ GＴ を選び、式（Ａ１０）の乱数αから式（Ａ１１）のMKとして示す前記マスターキーを生成し、式（Ａ１２）を計算する
【数１０】
2010060716.tif 000218
【数１１】
2010060716.tif 000219
【数１２】
2010060716.tif 000220
ことを特徴とする請求項１に記載のＩＤベース署名システム。
【請求項３】
前記セットアップフェーズにおいて、さらに、式（Ａ１３）に示す乱数の入力に対して式（Ａ１４）に示す出力を生成し、
【数１３】
2010060716.tif 000221
【数１４】
2010060716.tif 000222
前記システムパラメータを、次の式（Ａ１５）のparamsとする
【数１５】
2010060716.tif 000223
ことを特徴とする請求項２に記載のＩＤベース署名システム。
【請求項４】
前記エクストラクトフェーズにおいて、前記ＩＤをn１ビットのＩＤ情報とし、式（Ａ１６）に示すidkを前記ＩＤのk番目のビットとした場合、式（Ａ１７）に示す乱数sを選び、
【数１６】
2010060716.tif 000224
【数１７】
2010060716.tif 000225
式（Ａ１８）に示すＩＤに対応するプライベートキーを次の式（Ａ１９）に示すdＩＤとして計算する
【数１８】
2010060716.tif 000226
【数１９】
2010060716.tif 000227
ことを特徴とする請求項３に記載のＩＤベース署名システム。
【請求項５】
前記サインフェーズにおいて、前記文書のMをn２ビットの署名文書とし、パブリックキーをIDとし、式（Ａ２０）に示すmkを、前記文書Mのk 番目のビットとした場合、(ID,M)の組に関する署名σを、式（Ａ２１）により生成する
【数２０】
2010060716.tif 000228
【数２１】
2010060716.tif 000229
ことを特徴とする請求項４に記載のＩＤベース署名システム。
【請求項６】
前記ベリファイフェーズにおいて、前記システムパラメータparams、前記パブリックキー、前記文書の組(ID,M)および前記署名σを用いて、式（Ａ２２）を検証し、
【数２２】
2010060716.tif 000230
式（Ａ２２）のすべての等式が成り立つとき、検証結果として正常（valid）を出力し、それ以外のとき、異常（invalid）を出力することを特徴とする請求項５に記載のＩＤベース署名システム。
【請求項７】
セキュリティパラメータを入力としてシステムパラメータおよびマスターキーを返すセットアップ（Ｓｅｔｕｐ）フェーズと、該セットアップフェーズが出力する前記システムパラメータおよび前記マスターキーおよび任意のＩＤを入力としてプライベートキーを返すエクストラクト（Ｅｘｔｒａｃｔ）フェーズと、文書、前記エクストラクトフェーズが出力する前記プライベートキーおよび前記セットアップフェーズが出力する前記システムパラメータを入力として、署名を出力するサイン（Ｓｉｇｎ）フェーズ、および、前記文書、前記ＩＤ、前記サインフェーズが出力する前記署名および前記セットアップフェーズが出力する前記システムパラメータを入力として、正常（ｖａｌｉｄ）または異常（ｉｎｖａｌｉｄ）のいずれかを返すベリファイ（Ｖｅｒｉｆｙ）フェーズとの各フェーズを有するＩＤベース署名方法において、
G１,G２,GＴが素数p の位数を持つ乗法巡回群であり、g２はG２の生成元であり、ｆ：G２→G１が、次の式（Ａ２３）を満たす一方向性同型写像であり、e: G１×G２→GＴが、次の式（Ａ２４）を満たす双線形写像とした場合、
【数２３】
2010060716.tif 000231
【数２４】
2010060716.tif 000232
ランダムな生成元g１ ∈R G１， g２ ∈R G２およびランダムなx, y ∈R Zｐ＊に対する入力として、次の式（Ａ２５）に示すg１ｘｙの計算、
【数２５】
2010060716.tif 000233
ランダムな生成元g１∈R G１，g２∈R G２および乱数x，r１，r２，…，rｑ∈R Zｐ*となる次の式（Ａ２６）に示す入力に対し、式（Ａ２７）に示すあるr＊となる式（Ａ２８）の計算、
【数２６】
2010060716.tif 000234
【数２７】
2010060716.tif 000235
【数２８】
2010060716.tif 000236
および、ランダムな生成元g１∈R G１，g２∈R G２および乱数x，r１，r２，…，rｑ∈R Zｐ*となる次の式（Ａ２９）に示す入力に対し、式（Ａ３０）に示すあるr＊となる式（Ａ３１）の計算、
【数２９】
2010060716.tif 000237
【数３０】
2010060716.tif 000238
【数３１】
2010060716.tif 000239
のそれぞれの計算を、攻撃者が、時間t以内で、高々、あらかじめ定めた定数εの確率でしか行うことができないことを特徴とするＩＤベース署名方法。
【請求項８】
前記セットアップフェーズにおいて、十分大きな素数の位数p を持つ乗法巡回群G１，G２，GＴ，一方向性同型写像f : G２→ G１ (g１：＝ f(g２))および双線形写像e： G１ ×G２→ GＴ を選び、式（Ａ３２）の乱数αから式（Ａ３３）のMKとして示す前記マスターキーを生成し、式（Ａ３４）を計算する
【数３２】
2010060716.tif 000240
【数３３】
2010060716.tif 000241
【数３４】
2010060716.tif 000242
ことを特徴とする請求項７に記載のＩＤベース署名方法。
【請求項９】
前記セットアップフェーズにおいて、さらに、式（Ａ３５）に示す乱数の入力に対して式（Ａ３６）に示す出力を生成し、
【数３５】
2010060716.tif 000243
【数３６】
2010060716.tif 000244
前記システムパラメータを、次の式（Ａ３７）のparamsとする
【数３７】
2010060716.tif 000245
ことを特徴とする請求項８に記載のＩＤベース署名方法。
【請求項１０】
前記エクストラクトフェーズにおいて、前記ＩＤをn１ビットのＩＤ情報とし、式（Ａ３８）に示すidkを前記ＩＤのk番目のビットとした場合、式（Ａ３９）に示す乱数sを選び、
【数３８】
2010060716.tif 000246
【数３９】
2010060716.tif 000247
式（Ａ４０）に示すＩＤに対応するプライベートキーを次の式（Ａ４１）に示すdＩＤとして計算する
【数４０】
2010060716.tif 000248
【数４１】
2010060716.tif 000249
ことを特徴とする請求項９に記載のＩＤベース署名方法。
【請求項１１】
前記サインフェーズにおいて、前記文書のMをn２ビットの署名文書とし、パブリックキーをIDとし、式（Ａ４２）に示すmkを、前記文書Mのk 番目のビットとした場合、(ID,M)の組に関する署名σを、式（Ａ４３）により生成する
【数４２】
2010060716.tif 000250
【数４３】
2010060716.tif 000251
ことを特徴とする請求項１０に記載のＩＤベース署名方法。
【請求項１２】
前記ベリファイフェーズにおいて、前記システムパラメータparams、前記パブリックキー、前記文書の組(ID,M)および前記署名σを用いて、式（Ａ４４）を検証し、
【数４４】
2010060716.tif 000252
式（Ａ４４）のすべての等式が成り立つとき、検証結果として正常（valid）を出力し、それ以外のとき、異常（invalid）を出力することを特徴とする請求項１１に記載のＩＤベース署名方法。
【請求項１３】
請求項１乃至６に記載のＩＤベース署名システムをコンピュータシステムとして構築したことを特徴とするＩＤベース署名システム。
【請求項１４】
請求項７乃至１２に記載のＩＤベース署名方法を、コンピュータにより実行可能なプログラムとして実施することを特徴とするＩＤベース署名プログラム。
【請求項１５】
請求項１４に記載のＩＤベース署名プログラムをコンピュータにより読取可能な記録媒体に記録していることを特徴とするプログラム記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＩＤベース署名システムおよびＩＤベース署名方法に関する。
【背景技術】
【０００２】
以下では、括弧[]で括って示す数字は、下記非特許文献の番号を表す。通常の明細書では、例えば非特許文献１と表記される非特許文献を、本明細書では単に[1]と表記する。本明細書では、全部で２５件の非特許文献が引用されており、これら２５件の非特許文献は、《非特許文献一覧》として、番号１から２５を付して、後に表記される。これら番号が非特許文献の番号である。
【０００３】
１９８４年、非特許文献のA. Shamirによる“Identity-based cryptosystems and signature schemes” [23]において、ＩＤベース暗号システム(cryptosystem)の概念が提唱された本システムは，entityの秘密鍵private key を、自身のＩＤ情報(例：Ｅメールアドレス、電話番号など)および鍵生成局(ＰＫＧ: Private Key Generator と呼ばれる第三者信頼機関)のmaster key から生成する方式である。ＩＤベース暗号システムの利点は、従来の伝統的な公開鍵基盤で行われる認証を省略することができるところにある。
【０００４】
ランダムオラクル（random oracles）を仮定せずに証明可能な安全性を持つ方式の構成は、（IDベース）署名[14, 9, 4, 7, 25, 24, 6, 19]またはIDベース暗号[3, 24]の分野において、重要な研究テーマの一つである。なぜならば、ＭＤ５（Message Digest Algorithm 5）やＳＨＡ−１（Secure Hash Algorithm-1）のような一般的に利用されているハッシュ関数は、ランダムオラクルではないからである。
【０００５】
強偽造不可ＩＤベース署名方式は、（ＰＫＩとは異なる）公開鍵証明を（ＩＤベースではない）強偽造不可署名方式に付加することにより、構成できる。この構成法は[11, 2, 13]らのいくつかの論文において取りあげられている。それゆえ、ランダムオラクル仮定を用いない（「スタンダードモデル」ともよばれる）強偽造不可IDベース署名（IBS）方式を，Boneh−Boyen [4]、Zhang−Chen−Susilo−Mu [25]、Camenisch−Lysyanskaya
[7]、Okamoto [17]、Boneh−Shen−Waters [6] のような強偽造不可署名のスタンダードモデルに（PKIとは異なる）公開鍵証明書を付加することにより構成できる。しかしながら、これらの構成は、少なくとも６個の署名パラメータ（（署名者の）１つの公開鍵と（署名者およびPKGからの）２つの署名を含んでいる）が必要である。
【０００６】
また、Huang−Wong−Zhao[16]は、強ワンタイム署名を付加することにより、（弱）偽造不可IBS方式を強偽造不可IBS方式へ変換する一般的な方法を提案した。それゆえ、Paterson−Schuldt [19]の偽造不可IBS方式スタンダードモデルを適用することにより、強偽造不可IBS方式のスタンダードモデルを構成することができる。
【０００７】
《非特許文献一覧》
【非特許文献１】[1]  F. Bao, R. H. Deng, and H. Zhu.Variations of Diffie−Hellman problem. In ICICS 2003, LNCS 2836, pages 30−1312. Springer, 2003.
【非特許文献２】[2]  M. Bellare, C. Namprempre, and G.Neven. Security proofs for identity−based identification and signature schemes.In EUROCRYPT 2004,LNCS 3027, pages 268−286.Springer, 2004.
【非特許文献３】[3]  D. Boneh and X. Boyen. Efficientselective−ID secure identity−based encryption without random oracles. In EUROCRYPT 2004, LNCS 3027, pages 223−238. Springer, 2004.
【非特許文献４】[4]  D. Boneh and X. Boyen. Short signatureswithout random oracles. In EUROCRYPT2004, LNCS 3027,pages 56−73. Springer, 2004.
【非特許文献５】[5]  D. Boneh and M. K. Franklin. Identity−basedencryption from the Weil pairing. In CRYPTO 2001, LNCS 2139, pages 213−229. Springer, 2001.
【非特許文献６】[6]  D. Boneh, E. Shen, and B. Waters.Strongly unforgeable signatures based on computational Diffie−Hellman. In Public Key Cryptography 2006,LNCS 3958, pages 229−240. Springer,2006.
【非特許文献７】[7]  J. Camenisch and A. Lysyanskaya.Signature schemes and anonymous credentials from bilinear maps. In CRYPTO 2004, LNCS 3152, pages 5−672. Springer, 2004.
【非特許文献８】[8]  J. C. Cha and J. H. Cheon. An identity−basedsignature from gap Diffie−Hellman groups. In Public Key Cryptography 2003, LNCS 2567, pages 18−30. Springer, 2003.
【非特許文献９】[9]  R. Cramer and V. Shoup. Signatureschemes based on the strong RSA assumption. In ACM Conference on Computer and Communications Security, pages 46−51, 1999.
【非特許文献１０】[10]  W. Diffie and M. E. Hellman. Newdirections in cryptography. IEEETrans. Inf. Theory,22(6):644−654,1976.
【非特許文献１１】[11]  Y. Dodis, J. Katz, S. Xu, and M. Yung.Strong key−insulated signature schemes. In Public Key Cryptography 2002, LNCS 2567, pages 130−144. Springer, 2003.
【非特許文献１２】[12]  R. Dutta, R. Barua, and P. Sarkar.Pairing−based cryptographic protocols : A survey. Cryptology ePrint Archive,Report 2004/064, 2004. http://eprint.iacr.org/.
【非特許文献１３】[13]  D. Galindo, J. Herranz, and E. Kiltz.On the generic construction of identity−based signatures with additionalproperties. In ASIACRYPT 2006,LNCS 4284, pages 178−193. Springer,2006.
【非特許文献１４】[14]  R. Gennaro, S. Halevi, and T. Rabin.Secure hash−and−sign signatures without the random oracle. In EUROCRYPT 1999, LNCS 1592, pages 123−139. Springer, 1999.
【非特許文献１５】[15]  F. Hess. Efficient identity basedsignature schemes based on pairings. In Selected Areas in Cryptography (SAC 2002),LNCS 2595, pages 310−324. Springer,2002.
【非特許文献１６】[16]  Q. Huang, D. S. Wong, and Y. Zhao.Generic transformation to strongly unforgeable signatures. In ACNS 2007, LNCS 4521, pages 1−17. Springer, 2007.
【非特許文献１７】[17]  T. Okamoto. Efficient blind andpartially blind signatures without random oracles. In TCC 2006, LNCS 3876, pages 80−99. Springer, 2006.
【非特許文献１８】[18]  K. G. Paterson. ID−based signaturesfrom pairings on elliptic curves. Cryptology ePrint Archive, Report 2002/004,2002. http://eprint.iacr.org/.
【非特許文献１９】[19]  K. G. Paterson and J. C. N. Schuldt.Efficient identity−based signatures secure in the standard model. In ACISP 2006, LNCS 4058, pages 207−222. Springer, 2006.
【非特許文献２０】[20]  T. Saito, F. Hoshino, S. Uchiyama, andT. Kobayashi. Candidate one−way functions on non−supersingular elliptic curves.IEICE Transactions, 89−A(1):144−150, 2006.
【非特許文献２１】[21]  R. Sakai, K. Ohgishi, and M. Kasahara.Cryptosystems based on pairing. In SCIS2000, Okinawa, Japan, 2000.
【非特許文献２２】[22]  C. Sato, T. Okamoto, and E. Okamoto.Sender authenticated key agreements without random oracles. In ICCIT 2007,pages 2156−2162.IEEE Computer Society, 2007.
【非特許文献２３】[23]  A. Shamir. Identity−based cryptosystemsand signature schemes. In CRYPTO’ 84, LNCS 196, pages 47−53. Springer, 1984.
【非特許文献２４】[24]  B. Waters. Efficient identity−basedencryption without random oracles. In EUROCRYPT 2005, LNCS 3027, pages 114−127. Springer, 2005.
【非特許文献２５】[25]  F. Zhang, X. Chen, W. Susilo, and Y.Mu. A new signature scheme without random oracles from bilinear pairings. In VIETCRYPT 2006, LNCS 4341, pages 67−80. Springer, 2006.
【発明の開示】
【発明が解決しようとする課題】
【０００８】
上述のように、Paterson−Schuldt [19]の偽造不可IBS方式スタンダ−ドモデルを適用することにより、強偽造不可IBS方式のスタンダードモデルを構成することができる。しかしながら、これらの構成法でも、少なくとも６個の署名パラメ−タが必要である。そこで、本願発明は、５個の署名パラメータからなる強偽造不可IBSスタンダードモデルの提供を目的とする。
【課題を解決するための手段】
【０００９】
前述の課題を解決するため、本発明によるＩＤベース署名システムおよびＩＤベース署名方法は、次のような特徴的な構成を採用している。
【００１０】
（１）セキュリティパラメータを入力としてシステムパラメータおよびマスターキーを返すセットアップ（Ｓｅｔｕｐ）フェーズと、該セットアップフェーズが出力する前記システムパラメータおよび前記マスターキーおよび任意のＩＤを入力としてプライベートキーを返すエクストラクト（Ｅｘｔｒａｃｔ）フェーズと、文書、前記エクストラクトフェーズが出力する前記プライベートキーおよび前記セットアップフェーズが出力する前記システムパラメータを入力として、署名を出力するサイン（Ｓｉｇｎ）フェーズ、および、前記文書、前記ＩＤ、前記サインフェーズが出力する前記署名および前記セットアップフェーズが出力する前記システムパラメータを入力として、正常（ｖａｌｉｄ）または異常（ｉｎｖａｌｉｄ）のいずれかを返すベリファイ（Ｖｅｒｉｆｙ）フェーズとの各フェーズの演算部を備えたＩＤベース署名システムにおいて、
G１,G２,GＴが素数p の位数を持つ乗法巡回群であり（一般的に、G１，G２は、加法巡回群として定義されるが、表記の簡略化のため、乗法巡回群とする）、g２はG２の生成元であり、ｆ：G２→G１が、次の式（Ａ１）を満たす一方向性同型写像であり、e: G１×G２→GＴが、次の式（Ａ２）を満たす双線形写像とした場合、
【数１】
2010060716.tif 000002
【数２】
2010060716.tif 000003
ランダムな生成元g１ ∈R G１， g２ ∈R G２およびランダムなx, y ∈R Zｐ＊に対する入力として、次の式（Ａ３）に示すg１ｘｙの計算、
【数３】
2010060716.tif 000004
ランダムな生成元g１∈R G１，g２∈R G２および乱数x，r１，r２，…，rｑ∈R Zｐ*となる次の式（Ａ４）に示す入力に対し、式（Ａ５）に示すあるr＊となる式（Ａ６）の計算、
【数４】
2010060716.tif 000005
【数５】
2010060716.tif 000006
【数６】
2010060716.tif 000007
および、ランダムな生成元g１∈R G１，g２∈R G２および乱数x，r１，r２，…，rｑ∈R Zｐ*となる次の式（Ａ７）に示す入力に対し、式（Ａ８）に示すあるr＊となる式（Ａ９）の計算、
【数７】
2010060716.tif 000008
【数８】
2010060716.tif 000009
【数９】
2010060716.tif 000010
のそれぞれの計算を、攻撃者が、時間t以内で、高々、あらかじめ定めた定数εの確率でしか行うことができないＩＤベース署名システム。
【発明の効果】
【００１１】
本発明のＩＤベース署名システムおよびＩＤベース署名方法によれば、以下のような効果を得ることができる。
【００１２】
つまり、本発明においては、強偽造不可(strongly  Existential  Unforgeable  under  an  adaptive  Chosen  Message  Attack:適応的選択文書攻撃に対する強存在的偽造不可)安全な方式のスタンダードモデルを構成するという問題を解決する仕組みを実現することができる。なぜならば、本発明によるＩＤベース署名方式の安全性は、Diffie-Hellman問題と一方向性同型写像に関連した３つの問題を解くことの困難性に基づいているからである。
【発明を実施するための最良の形態】
【００１３】
以下、本発明によるＩＤベース署名システムおよびＩＤベース署名方法の好適な実施例について説明する。なお、以下の説明においては、本発明によるＩＤベース署名方法の一例について説明するが、該ＩＤベース署名方法を、例えばＣＰＵを含む演算部を備えたコンピュータシステムとして構築したＩＤベース署名システムとして実現することも、或いはそのＩＤベース署名方法を、コンピュータにより実行可能なプログラム（ＩＤベース署名プログラム）として実現することも、もちろん可能であることは言うまでもない。
【００１４】
以下に、本発明による実施形態の詳細について、次の順番に説明する。第１番目の「準備段階」の項において、本発明による署名方式の構成および安全性証明のための準備として各種の定義を行う。次の第２番目の「本発明による実施形態」の項において、ＤＨ問題に関連した２つの新しい仮定を与えた後、本発明の一例であるＩＤベース署名方式を説明する。しかる後、第３番目の「安全性証明」の項において、本発明におけるＩＤベース署名方式が、強偽造不可安全を満たすことを証明し、最後の第４番目の「結論」の項に本発明のまとめを説明する。
【００１５】
１．準備段階
ここでは、本発明による実施形態の説明に用いる一方向性同型写像、双線形写像、Diffie-Hellman（ＤＨ）問題、ＩＤベース署名および強偽造不可を定義する。
【００１６】
１．１．一方向性同型写像および双線形写像
一方向性同型写像および双線形写像に関する以下の定義は、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１は一方向性同型写像であり、次の式（１）を満たす;
【００１７】
【数４５】
2010060716.tif 000011
【００１８】
（４）e : G１×G２→GＴは双線形写像であり、以下の属性（ａ）〜（ｃ）を持つ:
【００１９】
（ａ）双線形性: 任意のu ∈G１、v ∈G２と任意のa，b ∈Zに対し、次の式（２）を満たす。
【００２０】
【数４６】
2010060716.tif 000012
【００２１】
（ｂ）非退化:次の式（３）を満たす。
【００２２】
【数４７】
2010060716.tif 000013
【００２３】
（ｃ）計算可能:任意のu ∈G１と任意のv ∈G２に対し，e(u,v)を計算する効率的な計算アルゴリズムが存在する。
【００２４】
ここで、G１，G２は、一般的に、一方向性同型写像f や双線形写像e 上において加法巡回群として定義されるが、以下の説明においては、表記の簡略化のため、乗法巡回群とする。
【００２５】
１．２．co-Diffie-Hellman（co-ＤＨ）問題
(G２，G１)上のco-ＤＨ問題を、以下のように与える。次の式（４）に示すように、ランダムな生成元g１ ∈R G１， g２ ∈R G２およびランダムなx, y ∈R Zｐ＊に対する入力として、（g１，g２，g２ｘ，g２ｙ）を与えたとき、g１ｘｙ ∈ G１を計算せよ。
【００２６】
【数４８】
2010060716.tif 000014
【００２７】
もし、次の式（５）が成り立つならば、アルゴリズムA は、(G２，G１)上のco-ＤＨ問題を解くε のアドバンテージを持っているという。ここで、この確率Pｒは、
g１ ∈R G１， g２ ∈R G２,x, y ∈R Zｐ＊およびA のランダムなビット列から選ばれている。
【００２８】
【数４９】
2010060716.tif 000015
【００２９】
つまり、次の仮定１を設定する。
（仮定１）攻撃者A が、時間t以内で、(G２，G１)上のco-Diffie-Hellman(co-ＤＨ)問題を解くアドバンテージを高々あらかじめ定めた確率εしか持たないとき、(G２，G１)上のco-Diffie-Hellman (co-ＤＨ)仮定は成り立つという。
【００３０】
ここで、もし、一方向性同型写像f : G２→G１およびランダムな生成元g２ ∈R G２ とするg１ :＝ f(g２) ∈ G１ と定めると、そのとき、生成元g１はランダムではないことに注意することを要する。
【００３１】
１．３．ＩＤベース署名方式（ＩＢＳ方式）
ここでのＩＢＳ方式の定義は、D. Bonehらによる“Identity-based encryption from the Weil pairing”（Proc.Crypto 2001, LNCS 2139, pp.213-229, 2001）[5]およびK. G. Patersonらによる“Efficient identity-based signatures secure in the standard model”[19]に記載された内容に準拠している。
【００３２】
本ＩＢＳ方式は、次の４つのフェーズ(Setup，Extract，Sign，Verify)から以下のように構成される。
【００３３】
（ａ）Setup：
セキュリティパラメータを入力として、params(システムパラメータ)およびmaster-keyを返す。システムパラメータは、有限の文書空間μおよび有限の署名空間S の定義も含んでいる。直観的には、システムパラメータは公開であるが、master-keyは鍵生成局(ＰＫＧ)のみが知っている非公開な値である。
【００３４】
（ｂ）Extract：
Setupの出力(params,master-key)および任意のID ∈{0,1}＊を入力として，private keyとしてd を返す．ここで、ID は、任意のストリングであり、public keyとして利用する。また、dは、対応するプライベート署名キーである。つまり、Extractは、public keyからprivate keyを抽出する(extract)フェーズである。このフェーズはＰＫＧにより行われる。
【００３５】
（ｃ）Sign：
文書M ∈μ，private key d およびparamsを入力とし、出力として署名σ ∈ S を返す。
【００３６】
（ｄ）Verify：
文書M ∈μ，署名σ ∈S，IDおよびparamsを入力とし、出力として正常（valid）または異常（invalid）を返す。
【００３７】
SignおよびVerifyにおけるパラメータは，あとで異なる順序で利用される。前述のこれら４つのフェーズは、標準的で一貫性のある制限事項でなければならない。すなわち、Extractフェーズにおいて生成されるID をpublic keyとし、対応するprivate keyをd とするとき、次の式（６）が成立しなければならない。
【００３８】
【数５０】
2010060716.tif 000016
【００３９】
１．４．強偽造不可
ここでの強偽造不可の定義は、前述のD. Bonehらによる“Identity-based encryption from the Weil pairing”（Proc.Crypto 2001, LNCS 2139, pp.213-229, 2001）、D. Bonehらによる“Strongly unforgeable signatures based on computational Diffie-Hellman”（Proc. PKC 2006, LNCS 3958,pp.229-240, 2006）および前記非特許文献１９の記載内容に従っている。特に、Paterson-Schuldtは、前記非特許文献１９において偽造不可および強偽造不可を定義している。しかしながら、Paterson-SchuldtのＩＢＳ方式の構成は、前述したように、偽造不可のみを満たしている。
【００４０】
ここで、本発明においては、強偽造不可を定義するために、以下のような挑戦者B と攻撃者A によるゲームを考える。
【００４１】
Setup：
挑戦者B は、セキュリティパラメータkを用い、ＩＢＳ方式のSetupフェーズを実行する。出力されたシステムパラメータparamsを攻撃者Aへ与える。なお、master-keyは挑戦者B が保持したままである。
【００４２】
Queries：
攻撃者Aは、挑戦者B へ多くの異なるQueryを適応的に行う。各Queryは以下のうちの一つである。
（１）エクストラクト・クエリExtract Queries(IDi)：攻撃者Aにより発行されたpublic key IDiに対して、挑戦者B は、Extractフェーズからprivate key dｉを生成し、攻撃者Aへ送信する。
（２）シグネチャ・クエリSignature Queries(IDi,Mi,j)：攻撃者A により発行された各Query(IDi,Mi,j)に対して、挑戦者Bは、Extractフェーズを行い、IDiに対応するprivate key dｉを生成し、Signフェーズから(IDi,Mi,j)に対する署名σi,jを作成し、攻撃者Aへσi,j を送信する。
【００４３】
Output：
最後に、攻撃者A は組(ID＊,M＊,σ＊)を出力する。ここで，σ＊はVerifyにおいてvalidとなる(ID＊,M＊)の署名である．ただし、条件として、エクストラクト・クエリにおけるすべてのIDiに対しID＊≠IDiとし、シグネチャ・クエリにおけるすべての（IDi,Mi,σi）に対し（ID＊,M＊,σ＊）≠（IDi,Mi,σi）とする。このとき、攻撃者A は強偽造不可ゲームに勝ったという。
【００４４】
ここで、AdvSigAを、挑戦者B と攻撃者A によるコイントスを用いた際に、攻撃者A が該ゲームに勝つ確率とする。
【００４５】
つまり、定義１として次を定義する。
（定義１）攻撃者A がＩＤベース署名を(qｅ,qｓ,t,ε)で破るとは、時間t以内に、攻撃者A が高々qｅ回のExtract Queries、高々qｓ回のSignature QueriesおよびAdvSig Aが少なくともεであることと定義する。ＩＢＳ方式が、適応的選択文書攻撃に対する (qｅ,qｓ,t,ε)−強存在的偽造不可(強偽造不可)であるとは、強偽造不可ゲームを(qｅ,qｓ, t,ε)で破る攻撃者A がいないことと定義する。
【００４６】
２．本発明による実施形態
次に、本発明によるＩＤベース署名方式（ＩＢＳ方式）の一例について、２つの新しい仮定の設定および該仮定に基づくＩＢＳ方式について説明する。
【００４７】
２．１．ベースとなる仮定の設定
まず、本実施形態におけるＩＤベース署名方式（ＩＢＳ方式）のベースとなる、ＤＨ問題に関連する仮定２および仮定３について説明する。
【００４８】
第一の問題は、以下のように与えられる。
つまり、第一の問題は、式（７）に示すようなランダムな生成元g１∈R G１，g２∈R
G２および乱数x，r１，r２，…，rｑ∈R Zｐ*となる式（８）に示す入力に対し、式（９）に示すようなあるr＊となる式（１０）を計算せよというものである。
【００４９】
【数５１】
2010060716.tif 000017
【００５０】
【数５２】
2010060716.tif 000018
【００５１】
【数５３】
2010060716.tif 000019
【００５２】
【数５４】
2010060716.tif 000020
【００５３】
もし、式（１１）が成り立つならば、アルゴリズムA は、第一の問題を解くεのアドバンテージを持っているという。ここで、式（１１）の確率Pｒは、式（７）、式（９）およびAのランダムなビット列から選ばれている。
【００５４】
【数５５】
2010060716.tif 000021
【００５５】
ここで、次の仮定２を次のように設定する。
（仮定２）攻撃者A が、時間t以内で、第一の問題を解くアドバンテージを高々あらかじめ定めた確率εしか持たないとき、(q，t，ε)−仮定［２］は成り立つという。
【００５６】
次の第二の問題は以下のように与えられる．
つまり、第二の問題は、式（１２）に示すようなランダムな生成元g１∈R G１，g２∈R
G２および乱数x，r１，r２，…，rｑ∈R Zｐ*となる式（１３）に示す入力に対し、式（１４）に示すようなあるr＊となる式（１５）を計算せよというものである。
【００５７】
【数５６】
2010060716.tif 000022
【００５８】
【数５７】
2010060716.tif 000023
【００５９】
【数５８】
2010060716.tif 000024
【００６０】
【数５９】
2010060716.tif 000025
【００６１】
もし、式（１６）が成り立つならば、アルゴリズムA は、第二の問題を解くεのアドバンテージを持っているという。ここで、式（１６）の確率Pｒは、式（１２）、式（１４）およびAのランダムなビット列から選ばれている。
【００６２】
【数６０】
2010060716.tif 000026
【００６３】
ここで、次の仮定３を次のように設定する。
（仮定３）攻撃者A が、時間t以内で、第二の問題を解くアドバンテージを高々あらかじめ定めた確率εしか持たないとき、(q，t，ε)−仮定［３］は成り立つという。
【００６４】
ランダムな生成元g２ ∈R G２に対し、一方向性同型写像f ： G２→G１を、g１：＝f(g２) ∈ G１で定義する。このとき、生成元g１ はランダムではないことに注意を要する。なお、fの存在は、T.Saitoらによる“Candidate one-way functions on non-supersingular elliptic curves”（IEICE Trans. Fundamentals, vol.E89, pp.144-150, 2006）において、non-supersingularな楕円曲線上で構成された加法巡回群上で定義される場合、証明されている。本発明によるＩＤベース署名方式の安全性は、本質的に、前述したco-ＤＨ仮定（仮定１）とここで説明した２つの仮定（仮定２、仮定３）および一方向性同型写像fを基礎として成り立っている。特に、ここで設定した２つの仮定（仮定２、仮定３）は、厳密な数学的様式に従って定義されていて、詳細は後述するが、本発明によるＩＤベース署名方式の強偽造不可安全の証明に大きく貢献する。
【００６５】
２．２．本実施形態におけるＩＤベース署名方式
次に、本実施形態におけるＩＤベース署名方式についてその一例を説明する。本ＩＤベース署名方式は、前述に定義したような(Setup，Extract，Sign，Verify)の４つのフェーズから構成される。差し当たり、ＩＤを式（１７）の要素と仮定するが、式（１８）に示すような衝突耐性を持つハッシュ関数を使って、領域を式（１９）のように拡張することもできる。
【００６６】
【数６１】
2010060716.tif 000027
【００６７】
【数６２】
2010060716.tif 000028
【００６８】
【数６３】
2010060716.tif 000029
【００６９】
同様に、署名文書Ｍについても式（２０）の要素と仮定する。
【００７０】
【数６４】
2010060716.tif 000030
【００７１】
（ａ）セットアップ（Setup）フェーズ：
鍵生成局ＰＫＧは、十分大きな素数の位数p を持つ乗法巡回群G１，G２，GＴ，一方向性同型写像f : G２→ G１ (g１：＝ f(g２))および双線形写像e： G１ ×G２→ GＴ を選ぶ。ＰＫＧは、式（２１）の乱数αからマスターキーとして式（２２）を生成し、式（２３）を計算する。
【００７２】
【数６５】
2010060716.tif 000031
【００７３】
【数６６】
2010060716.tif 000032
【００７４】
【数６７】
2010060716.tif 000033
【００７５】
つまり、次の式（２４）、式（２５）を計算する。
【００７６】
【数６８】
2010060716.tif 000034
【００７７】
【数６９】
2010060716.tif 000035
【００７８】
また、鍵生成局ＰＫＧは、式（２６）に示す乱数の入力に対して式（２７）に示す出力を生成する。
【００７９】
【数７０】
2010060716.tif 000036
【００８０】
【数７１】
2010060716.tif 000037
【００８１】
ここで、マスターシークレットmaster-keyをMKとし、公開パラメータparamsを、次の式（２８）とする。
【００８２】
【数７２】
2010060716.tif 000038
【００８３】
（ｂ）エクストラクト（Extract）フェーズ：
IDをn１ビットのID情報とし、式（２９）に示すidkをIDの(左から)k番目のビットとする。
【００８４】
【数７３】
2010060716.tif 000039
【００８５】
鍵生成局ＰＫＧは、式（３０）に示す乱数sを選び、式（３１）に示すＩＤに対応するprivate key dIDを次の式（３２）に示すように計算する。
【００８６】
【数７４】
2010060716.tif 000040
【００８７】
【数７５】
2010060716.tif 000041
【００８８】
【数７６】
2010060716.tif 000042
【００８９】
（ｃ）サイン（Sign）フェーズ：
M をn２ビットの署名文書とし、式（３３）に示すmkを、Mの(左から)k 番目のビットとする。 (ID,M)の署名σ（式（３４）に示す）は、次の式（３５）のように生成される。ここで、r ∈ Zｐ*は乱数である。
【００９０】
【数７７】
2010060716.tif 000043
【００９１】
【数７８】
2010060716.tif 000044
【００９２】
【数７９】
2010060716.tif 000045
【００９３】
（ｄ）ベリファイ（Verify）フェーズ：
params,(ID,M)および次の式（３６）に示すσを使い、式（３７）を検証する。
【００９４】
【数８０】
2010060716.tif 000046
【００９５】
【数８１】
2010060716.tif 000047
【００９６】
式（３７）のすべての等式が成り立つとき、検証結果として正常（valid）を出力し、それ以外のとき、異常（invalid）を出力する。
【００９７】
もし、あるＩＤのentityが、文書Mの署名σ（式（３８）に示す）をSignフェーズにおいて生成したならば、次の式（３９）の計算により、署名σは検証者に受理されることがわかる。よって、この方式は正当である。
【００９８】
【数８２】
2010060716.tif 000048
【００９９】
【数８３】
2010060716.tif 000049
【０１００】
３．安全性証明
次に、２項にて説明した本実施形態におけるＩＤベース署名方式の安全性つまり次の（定理１）が成立することを証明する。
（定理１）g１:＝f(g２)となる条件で、(G２，G１)上の(t０，ε０)−ＤＨ仮定、(q１，t１，ε１)−仮定［２］および(q２，t２，ε２)−仮定［３］が成り立つと仮定する。そのとき、前述の本実施形態のＩＤベース署名方式は、(qｅ，qｓ，t，ε)−強偽造不可であり、次の式（４０）を満たす。ここで，TはG２におけるべき剰余計算１回にかかる最大時間とする。
【０１０１】
【数８４】
2010060716.tif 000050
【０１０２】
次に、以下のアウトラインに沿って、安全性の証明を行う。
【０１０３】
まず、前述した本実施形態のＩＢＳ方式（ＩＤベース署名方式）の安全性を破る攻撃者A の存在および仮定［２］のチャレンジを受け取る挑戦者B の存在を仮定する。攻撃者A
と挑戦者B とは強偽造不可ゲームを実行し、攻撃者Aはvalidとなる(ID，文書，署名)の一組を出力する。次に、挑戦者B は仮定［２］においてvalidとなるレスポンスを計算する。ここで、攻撃者Aの出力は、co-ＤＨ仮定と仮定［３］とに矛盾してはならない。
【０１０４】
（安全性の証明）
本実施形態のＩＢＳ方式の安全性を、(qｅ，qｓ，t，ε)で破る攻撃者Aの存在を仮定する。ここで、仮定［２］ゲームを行うシミュレータBを構成する。シミュレータB は、式（４１）に示す仮定［２］ゲームのチャレンジを受け取る。
【０１０５】
【数８５】
2010060716.tif 000051
【０１０６】
式（４１）において、α，sｉは、次の式（４２）の通りである。また、シミュレータB は、攻撃者Aと以下の手順を実行する。
【０１０７】
【数８６】
2010060716.tif 000052
【０１０８】
Ａ．Simulator Description（シミュレータの構成）
Setup：
シミュレータB は、式（４３）の乱数から式（４４）の情報を生成し、Aに対して、式（４５）の情報を送信する。
【０１０９】
【数８７】
2010060716.tif 000053
【０１１０】
【数８８】
2010060716.tif 000054
【０１１１】
【数８９】
2010060716.tif 000055
【０１１２】
（Ａ．１）クエリ（Queries）：
攻撃者A は、シミュレータつまり挑戦者Bへ多くの異なるQueryを適応的に行う。
【０１１３】
UｅをExtract QueriesにおけるID情報の添え字集合、UｓをSignature QueriesにおけるID情報の添え字集合とし、式（４６）と置く。また、μｓｉ（つまり式（４７）に示す）を、Signature
QueriesにおけるIDｉ（式（４８）に示す）の文書の添え字集合とする。
【０１１４】
【数９０】
2010060716.tif 000056
【０１１５】
【数９１】
2010060716.tif 000057
【０１１６】
【数９２】
2010060716.tif 000058
【０１１７】
ここで、各Queryは以下の中の一つである。
【０１１８】
（Ａ−Ｅ）Extract Queries：
攻撃者Aは、シミュレータBに対し、適応的に、Extract Queries IDｉ(i ∈Uｅ)を行う。式（４９）に示すIDｉに対し、次の式（５０）と仮定する。
【０１１９】
【数９３】
2010060716.tif 000059
【０１２０】
【数９４】
2010060716.tif 000060
【０１２１】
(Ａ−Ｅ１)：
もし、式（５１）が成立するならば、シミュレータB はこのゲームを中断する。
【０１２２】
【数９５】
2010060716.tif 000061
【０１２３】
(Ａ−Ｅ２)：
式（５１）が成立しないその他の場合(すなわち、式（５２）の場合)、シミュレータB はゲームを中断せずに、IDｉに対応するdｉ＝(dｉ,１，dｉ,２)を、次の式（５３）、式（５４）のように、生成し、それをAへ送信する。
【０１２４】
【数９６】
2010060716.tif 000062
【０１２５】
【数９７】
2010060716.tif 000063
【０１２６】
【数９８】
2010060716.tif 000064
【０１２７】
なお、式（５４）において、上線付きのsｉは、次の式（５５）で与えられる。
【０１２８】
【数９９】
2010060716.tif 000065
【０１２９】
式（５３）のすべてのsｉ ∈Ｒ Zｐ＊を消去することにより、式（５４）のすべての上線付きのsｉ（式（５６）に示す）は乱数と看做すことができることに注意を要する。
【０１３０】
【数１００】
2010060716.tif 000066
【０１３１】
（Ａ−Ｓ）Signature Queries：
攻撃者A は、シミュレータBに対し、適応的に、次の式（５７）に示すSignature Queries(IDｉ，Mｉ,ｊ)を行う。
【０１３２】
【数１０１】
2010060716.tif 000067
【０１３３】
ｉ ∈ Uｓのとき、Xｉを式（５０）のように仮定し、式（５８）に対し、次の式（５９）と仮定する。
【０１３４】
【数１０２】
2010060716.tif 000068
【０１３５】
【数１０３】
2010060716.tif 000069
【０１３６】
(Ａ−Ｓ１)：
もし、式（６０）が成立するならば、シミュレータB はこのゲームを中断する。
【０１３７】
【数１０４】
2010060716.tif 000070
【０１３８】
(Ａ−Ｓ２)：
式（６０）が成立しないその他の場合(すなわち、式（６１）の場合)、シミュレータB は、このゲームを中断せずに、(IDｉ，Mｉ,ｊ)に対応する式（６２）のそれぞれを、式（６３）のように生成し、それをAへ送信する。
【０１３９】
【数１０５】
2010060716.tif 000071
【０１４０】
【数１０６】
2010060716.tif 000072
【０１４１】
【数１０７】
2010060716.tif 000073
【０１４２】
なお、式（６３）において、上線付きのsｉおよびrｉ,ｊは、次の式（６４）で与えられる。
【０１４３】
【数１０８】
2010060716.tif 000074
【０１４４】
式（６３）のすべてのsｉおよびrｉ,ｊ（式（６５）に示す）を消去することにより、式（５４）のすべての上線付きのsｉおよびrｉ,ｊ（式（６６）に示す）は乱数と看做すことができることに注意を要する。
【０１４５】
【数１０９】
2010060716.tif 000075
【０１４６】
【数１１０】
2010060716.tif 000076
【０１４７】
（Ａ．２）アウトプット（Output）：
攻撃者Aは、(ID＊，M＊，σ＊)を出力する。ただし、式（６７）に示すσ＊は、(ID＊，M＊)に対するvalidな署名であり、エクストラクト・クエリにおけるすべてのIDiに対しID＊≠IDiとし、シグネチャ・クエリにおけるすべての（IDi,Mi,σi）に対し（ID＊,M＊,σ＊）≠（IDi,Mi,σi）とする。
【０１４８】
【数１１１】
2010060716.tif 000077
【０１４９】
（Ａ．３）アーティフィシャル・アボート（Artificial Abort）：
式（６８）に示すＩＤ情報ID＊および文書M＊に対し、式（６９）と仮定する。
【０１５０】
【数１１２】
2010060716.tif 000078
【０１５１】
【数１１３】
2010060716.tif 000079
【０１５２】
ここで、次の式（７０）または式（７１）が成立するならば、シミュレータB はこのゲームを強制的に中断する。
【０１５３】
【数１１４】
2010060716.tif 000080
【０１５４】
【数１１５】
2010060716.tif 000081
【０１５５】
Ｂ．シミュレーション結果の分析
攻撃者A は、式（７２）が成立するときとして、前述の（Ａ−Ｅ１）、（Ａ−Ｓ１）に示すような中断があるSimulator Descriptionゲームと、中断のない強偽造不可ゲームとを区別することができない。
【０１５６】
【数１１６】
2010060716.tif 000082
【０１５７】
その理由は、式（７３）の条件を満たす確率Pｒは、式（７４）が成立するとき、negligibleな値となるからである。ゆえに、以降では、Simulator Descriptionゲ−ムのみを考えていけば良い。
【０１５８】
【数１１７】
2010060716.tif 000083
【０１５９】
【数１１８】
2010060716.tif 000084
【０１６０】
Simulator Descriptionゲームの場合、σ＊はvalidなので、式（７５）と仮定する。なお、式（７５）において、上線付きのs＊，r＊は、式（７６）である。
【０１６１】
【数１１９】
2010060716.tif 000085
【０１６２】
【数１２０】
2010060716.tif 000086
【０１６３】
（Ｂ−１）
もし、式（７７）が成立するならば、式（７８）である。そのとき、B は、式（７９）に示すあるs＊となる組を式（８０）として生成する。式（８０）に示す組は、仮定［２］チャレンジに対するvalidな出力となる。
【０１６４】
【数１２１】
2010060716.tif 000087
【０１６５】
【数１２２】
2010060716.tif 000088
【０１６６】
【数１２３】
2010060716.tif 000089
【０１６７】
【数１２４】
2010060716.tif 000090
【０１６８】
（Ｂ−２）
次に、式（７７）が成立しないその他の場合（すなわち、式（８１）の場合）について考える。
【０１６９】
【数１２５】
2010060716.tif 000091
【０１７０】
（Ｂ−２．１）
式（８２）と仮定し(これは強偽造不可安全の定義による)、また、式（８３）と仮定する。
【０１７１】
【数１２６】
2010060716.tif 000092
【０１７２】
【数１２７】
2010060716.tif 000093
【０１７３】
式（８２）、式（８３）を仮定したとき、式（８４）を考えれば十分である。これは、A が、式（８５）のすべてを知っている場合(つまり、式（８６）の場合)を意味している。あるε’≦εに対し、式（８４）≧ε’と仮定する。
【０１７４】
【数１２８】
2010060716.tif 000094
【０１７５】
【数１２９】
2010060716.tif 000095
【０１７６】
【数１３０】
2010060716.tif 000096
【０１７７】
（Ｂ−２．１．１）
s＊ ＝ sｌを満たす数l ∈ U が存在すると仮定する。式（８４）において、もし、A が、式（８７）に示す上線付きのsｉ，rｉ，ｊのすべておよび式（８８）に示すg２αを知ったとき、式（８４）から式（８９）を消去することができる。
【０１７８】
【数１３１】
2010060716.tif 000097
【０１７９】
【数１３２】
2010060716.tif 000098
【０１８０】
【数１３３】
2010060716.tif 000099
【０１８１】
また、式（９０）が成立するので、出力の第３成分を式（９１）に置き換え、残りの成分を消去する。
【０１８２】
【数１３４】
2010060716.tif 000100
【０１８３】
【数１３５】
2010060716.tif 000101
【０１８４】
ゆえに、A は、式（９２）を解くためのアドバンテージε′を持つ。ここで、この問題は、式（９３）、式（５０）におけるXｉ(ｉ ∈ U)、式（５９）における式（９４）、式（６９）におけるX＊，Y＊およびA のランダムなビット列から選ばれる。
【０１８５】
【数１３６】
2010060716.tif 000102
【０１８６】
【数１３７】
2010060716.tif 000103
【０１８７】
【数１３８】
2010060716.tif 000104
【０１８８】
ここで、ｉ ∈ Uについて、式（９５）と置く。
【０１８９】
【数１３９】
2010060716.tif 000105
【０１９０】
また、式（９６）が成立するので、A は式（９７）から式（９８）を計算することができる。
【０１９１】
【数１４０】
2010060716.tif 000106
【０１９２】
【数１４１】
2010060716.tif 000107
【０１９３】
【数１４２】
2010060716.tif 000108
【０１９４】
よって、式（９８）に示す各パラメータを式（９２）から消去する。また、式（９９）は、式（１００）に示す式（９２）の出力とは関連性がないので、式（９９）に示すこれらの入力パラメータも式（９２）から消去することができる。
【０１９５】
【数１４３】
2010060716.tif 000109
【０１９６】
【数１４４】
2010060716.tif 000110
【０１９７】
式（９２）において、式(１０１)を式（１０２）へ置き換えることにより、Aは、式（１０３）を解くためのアドバンテージε′を持つ。
【０１９８】
【数１４５】
2010060716.tif 000111
【０１９９】
【数１４６】
2010060716.tif 000112
【０２００】
【数１４７】
2010060716.tif 000113
【０２０１】
ここで、（式（１０４）のときでさえ、)式（１０５）が成立するので、式（１０６）が成立することに注意を要する。
【０２０２】
【数１４８】
2010060716.tif 000114
【０２０３】
【数１４９】
2010060716.tif 000115
【０２０４】
【数１５０】
2010060716.tif 000116
【０２０５】
式（１０７）と仮定する。式（１０８）に示すx′を式（９２）から消去したため，h をZｐ＊の乱数として良い。
【０２０６】
【数１５１】
2010060716.tif 000117
【０２０７】
【数１５２】
2010060716.tif 000118
【０２０８】
これは、A が、式（１０９）を解くのにアドバンテージε′を持つことに等しい。ここで、この問題は、式（１１０）およびA のランダムなビット列から選ばれる。
【０２０９】
【数１５３】
2010060716.tif 000119
【０２１０】
【数１５４】
2010060716.tif 000120
【０２１１】
F. Baoらによる“Variations of Diffie-Hellman problem”（Proc.ICICS2003, Springer-Verlag, 2003）の記載内容から、これは、式（１１１）を解くのにアドバンテージε′をA が持つことに等しい。
【０２１２】
【数１５５】
2010060716.tif 000121
【０２１３】
ここで、この問題は式（１１２）およびA のランダムなビット列から選ばれる。これは、A が(G２,G１)上のco-ＤＨ問題をnon-negligibleな確率で解くことができることを意味している。
【０２１４】
【数１５６】
2010060716.tif 000122
【０２１５】
（Ｂ−２．１．２）
s＊ ＝ sｉを満たす数i ∈ U が存在しないその他の場合(すなわち、式（１１３）の場合)、Aは、x′，x１,x２，…，xｎ１，ｙ′，ｙ１,ｙ２，…，ｙｎ２の値を知っているものと仮定する。
【０２１６】
【数１５７】
2010060716.tif 000123
【０２１７】
そのとき、式（８４）から式（１１４）を消去することができる。また、式（１１５）に示す組を仮定［２］チャレンジの出力と考えると、式（８４）から式（１１６）を消去することができる。
【０２１８】
【数１５８】
2010060716.tif 000124
【０２１９】
【数１５９】
2010060716.tif 000125
【０２２０】
【数１６０】
2010060716.tif 000126
【０２２１】
これらは、式（８４）の確率Pｒが、仮定［２］の矛盾となるように変形することができることを意味している。
【０２２２】
（Ｂ−２．２）
式（８２）、式（８３）が成立しないその他の場合(すなわち、式（１１７）の場合であり、また、式（１１８）である場合)、X＊ ＝ Xｌである。この場合、Aが、式（１１９）の数値を知っている場合の式（１２０）に示す確率Pｒを考えれば十分である。ε’＋ε”＝εとなるあるε”に対し、式（１２０）≧ε”と仮定する。
【０２２３】
【数１６１】
2010060716.tif 000127
【０２２４】
【数１６２】
2010060716.tif 000128
【０２２５】
【数１６３】
2010060716.tif 000129
【０２２６】
【数１６４】
2010060716.tif 000130
【０２２７】
（Ｂ−２．２．１）
まず、式（１２１）と仮定する。
【０２２８】
【数１６５】
2010060716.tif 000131
【０２２９】
（Ｂ−２．２．１．１）
r＊＝rｌ,ｋとなるような式（１２２）に示す数kが存在すると仮定する。式（１２０）において、もし、Aが、式（１２３）に示す上線付きのrｌ、ｊとsｌとのすべてを知っているならば、式（１２０）から式（１２４）を消去することができる。
【０２３０】
【数１６６】
2010060716.tif 000132
【０２３１】
【数１６７】
2010060716.tif 000133
【０２３２】
【数１６８】
2010060716.tif 000134
【０２３３】
また、式（１２５）が成立するので、出力の第２成分を式（１２６）に置き換え、第３成分と第４成分とを消去する。
【０２３４】
【数１６９】
2010060716.tif 000135
【０２３５】
【数１７０】
2010060716.tif 000136
【０２３６】
ゆえに、A は、式（１２７）を解くためのアドバンテージε”を持つ。ここで、この問題は、式（１２８）、式（５９）における式（１２９）、式（６９）におけるY＊およびA
のランダムなビット列から選ばれる。
【０２３７】
【数１７１】
2010060716.tif 000137
【０２３８】
【数１７２】
2010060716.tif 000138
【０２３９】
【数１７３】
2010060716.tif 000139
【０２４０】
ここで、式（１３０）に示す数jに対し、式（１３１）と置く。
【０２４１】
【数１７４】
2010060716.tif 000140
【０２４２】
【数１７５】
2010060716.tif 000141
【０２４３】
式（１３２）が成立するので，A は、式（１３３）から式（１３４）を計算することができる。
【０２４４】
【数１７６】
2010060716.tif 000142
【０２４５】
【数１７７】
2010060716.tif 000143
【０２４６】
【数１７８】
2010060716.tif 000144
【０２４７】
よって、式（１３４）に示す各パラメータを式（１２７）から消去する。また、式（１２７)において、式（１３５）を式（１３６）へ置き換えると、A は、式（１３７）を解くためのアドバンテージε”を持つ。前述の(Ｂ−２．１．１)にて説明した場合と同様に、これは、A が、(G２，G１)上のco-ＤＨ問題をnon-negligibleな確率で解くことができることを意味している。
【０２４８】
【数１７９】
2010060716.tif 000145
【０２４９】
【数１８０】
2010060716.tif 000146
【０２５０】
【数１８１】
2010060716.tif 000147
【０２５１】
（Ｂ−２．２．１．２）
r＊＝rｌ,ｋとなるような式（１２２）に示す数kが存在しないその他の場合(すなわち、式（１３８）となる場合)、A は、x′，x１，x２，…，xｎ１と同様に、y′，y１，y２，…，yｎ２も知っていると仮定する。そのとき、式（１３９）の等式から、式（１２０）の確率Pｒの変形は、仮定［３］に矛盾する。
【０２５２】
【数１８２】
2010060716.tif 000148
【０２５３】
【数１８３】
2010060716.tif 000149
【０２５４】
（Ｂ−２．２．２）
次に、式（１２１）を仮定しないその他の場合(すなわち、式（１４０）が成立する場合)、式（１４１）が示す数を次の式（１４２）が成立するすべての数とする。
【０２５５】
【数１８４】
2010060716.tif 000150
【０２５６】
【数１８５】
2010060716.tif 000151
【０２５７】
【数１８６】
2010060716.tif 000152
【０２５８】
そのとき、式（１４３）から式（１４４）となる。また、式（１４５）を式（１４６）とする。これは式（１４７）を意味している。
【０２５９】
【数１８７】
2010060716.tif 000153
【０２６０】
【数１８８】
2010060716.tif 000154
【０２６１】
【数１８９】
2010060716.tif 000155
【０２６２】
【数１９０】
2010060716.tif 000156
【０２６３】
【数１９１】
2010060716.tif 000157
【０２６４】
（Ｂ−２．２．２．１）
式（１４８）が成立するときであり、かつ、r＊ = rｋとなる式（１４９）の数ｋが存在すると仮定する。
【０２６５】
【数１９２】
2010060716.tif 000158
【０２６６】
【数１９３】
2010060716.tif 000159
【０２６７】
このとき、前述の(Ｂ−２．２．１．１)の場合のように、Aは、(G２，G１)上のco-ＤＨ問題をnon-negligibleな確率で解くことができる。
【０２６８】
（Ｂ−２．２．２．２）
式（１４８）が成立しない場合あるいはr＊ = rｋとなる式（１４９）の数ｋが存在しないその他の場合(すなわち、式（１５０）が成立する場合あるいは式（１５１）が成立する場合)、式（１５２）に示す組は、仮定［３］チャレンジのvalid出力である。
【０２６９】
【数１９４】
2010060716.tif 000160
【０２７０】
【数１９５】
2010060716.tif 000161
【０２７１】
【数１９６】
2010060716.tif 000162
【０２７２】
シミュレーションにおいて、式（１５３）のいずれも満たさない場合の確率は、次の式（１５４）で与えられる。
【０２７３】
【数１９７】
2010060716.tif 000163
【０２７４】
【数１９８】
2010060716.tif 000164
【０２７５】
よって、本発明に係わるＩＤベース署名方式S においては、式（１５５）が成立する。
【０２７６】
【数１９９】
2010060716.tif 000165
【０２７７】
以上の（Ｂ−１）および（Ｂ−２）から、式（１５６）に示す確率Pｒ（≧ε＝ε´＋ε”）は、少なくとも、式（１５５）の左辺の確率Pｒより高い。事象A１，A２に対し、式（１５７）、式（１５８）であるので、式（１５９）である。
【０２７８】
【数２００】
2010060716.tif 000166
【０２７９】
【数２０１】
2010060716.tif 000167
【０２８０】
【数２０２】
2010060716.tif 000168
【０２８１】
【数２０３】
2010060716.tif 000169
【０２８２】
これは、(t０，ε０)−co-ＤＨ仮定、(q１，t１，ε１)−仮定［２］または(q２，t２，ε２)−仮定［３］に矛盾する。よって、本発明に係わるＩＤベース署名方式は、(qｅ，qｓ，t，ε)−強偽造不可安全である。
【０２８３】
もし、A が、前述の「Ａ．Simulator Description（シミュレータの構成）」に記載のゲームについて、時間t 内の確率ε で、validな偽造を出力したならば、それは、Bが仮定［２］ゲームについて、または、A がco-ＤＨゲームあるいは仮定［３］ゲームについて、式（１６０）に示す時間以内に、式（１６１）に示す確率で成功することを意味している。
【０２８４】
【数２０４】
2010060716.tif 000170
【０２８５】
【数２０５】
2010060716.tif 000171
【０２８６】
よって、式（１６２）に示す仮定が必要である。これは、式（１６３）であることを意味している。以上より、前述した定理１は証明された。
【０２８７】
【数２０６】
2010060716.tif 000172
【０２８８】
【数２０７】
2010060716.tif 000173
【０２８９】
本発明に係わるＩＢＳ方式は、前述のように、強偽造不可の安全性を満たすことができた。その理由の一つは、３つの数学的仮定と１つの一方向性同型写像f とを使い、安全性証明を直接的に行うことができるからということができる。
【０２９０】
４．結論
以上に詳細に説明したように、本発明においては、５個の署名パラメータからなる、強偽造不可ＩＢＳ方式のスタンダードモデルを提供している。本発明によるＩＢＳ方式の署名長は、Diffie−Hellman問題あるいは離散対数問題に関連した問題をベースにした他のＩＢＳ方式と比較して短い。なお、本発明に係わるＩＢＳ方式の安全性は、前述したように、Diffie−Hellman問題と一方向性同型写像に関連した３つの問題を解くことの困難性に基づいている。
【０２９１】
以上、本発明の好適実施例の構成を説明した。しかし、斯かる実施例は、本発明の単なる例示に過ぎず、何ら本発明を限定するものではないことに留意されたい。本発明の要旨を逸脱することなく、特定用途に応じて種々の変形変更が可能であることが、当業者には容易に理解できよう。例えば、本発明の実施態様は、課題を解決するための手段における構成（１）に加えて、次のような構成として表現できる。
（２）前記セットアップフェーズにおいて、十分大きな素数の位数p を持つ乗法巡回群G１，G２，GＴ，一方向性同型写像f : G２→ G１ (g１：＝ f(g２))および双線形写像e： G１ ×G２→ GＴ を選び、式（Ａ１０）の乱数αから式（Ａ１１）のMKとして示す前記マスターキーを生成し、式（Ａ１２）を計算する
【数１０】
2010060716.tif 000174
【数１１】
2010060716.tif 000175
【数１２】
2010060716.tif 000176
上記（１）のＩＤベース署名システム。
（３）前記セットアップフェーズにおいて、さらに、式（Ａ１３）に示す乱数の入力に対して式（Ａ１４）に示す出力を生成し、
【数１３】
2010060716.tif 000177
【数１４】
2010060716.tif 000178
前記システムパラメータを、次の式（Ａ１５）のparamsとする
【数１５】
2010060716.tif 000179
上記（２）のＩＤベース署名システム。
（４）前記エクストラクトフェーズにおいて、前記ＩＤをn１ビットのＩＤ情報とし、式（Ａ１６）に示すidkを前記ＩＤのk番目のビットとした場合、式（Ａ１７）に示す乱数sを選び、
【数１６】
2010060716.tif 000180
【数１７】
2010060716.tif 000181
式（Ａ１８）に示すＩＤに対応するプライベートキーを次の式（Ａ１９）に示すdＩＤとして計算する
【数１８】
2010060716.tif 000182
【数１９】
2010060716.tif 000183
上記（３）のＩＤベース署名システム。
（５）前記サインフェーズにおいて、前記文書のMをn２ビットの署名文書とし、パブリックキーをIDとし、式（Ａ２０）に示すmkを、前記文書Mのk 番目のビットとした場合、(ID,M)の組に関する署名σを、式（Ａ２１）により生成する
【数２０】
2010060716.tif 000184
【数２１】
2010060716.tif 000185
上記（４）のＩＤベース署名システム。
（６）前記ベリファイフェーズにおいて、前記システムパラメータparams、前記パブリックキー、前記文書の組(ID,M)および前記署名σを用いて、式（Ａ２２）を検証し、
【数２２】
2010060716.tif 000186
式（Ａ２２）のすべての等式が成り立つとき、検証結果として正常（valid）を出力し、それ以外のとき、異常（invalid）を出力する上記（５）のＩＤベース署名システム。
（７）セキュリティパラメータを入力としてシステムパラメータおよびマスターキーを返すセットアップ（Ｓｅｔｕｐ）フェーズと、該セットアップフェーズが出力する前記システムパラメータおよび前記マスターキーおよび任意のＩＤを入力としてプライベートキーを返すエクストラクト（Ｅｘｔｒａｃｔ）フェーズと、文書、前記エクストラクトフェーズが出力する前記プライベートキーおよび前記セットアップフェーズが出力する前記システムパラメータを入力として、署名を出力するサイン（Ｓｉｇｎ）フェーズ、および、前記文書、前記ＩＤ、前記サインフェーズが出力する前記署名および前記セットアップフェーズが出力する前記システムパラメータを入力として、正常（ｖａｌｉｄ）または異常（ｉｎｖａｌｉｄ）のいずれかを返すベリファイ（Ｖｅｒｉｆｙ）フェーズとの各フェーズを有するＩＤベース署名方法において、
G１,G２,GＴが素数p の位数を持つ乗法巡回群であり、g２はG２の生成元であり、ｆ：G２→G１が、次の式（Ａ２３）を満たす一方向性同型写像であり、e: G１×G２→GＴが、次の式（Ａ２４）を満たす双線形写像とした場合、
【数２３】
2010060716.tif 000187
【数２４】
2010060716.tif 000188
ランダムな生成元g１ ∈R G１， g２ ∈R G２およびランダムなx, y ∈R Zｐ＊に対する入力として、次の式（Ａ２５）に示すg１ｘｙの計算、
【数２５】
2010060716.tif 000189
ランダムな生成元g１∈R G１，g２∈R G２および乱数x，r１，r２，…，rｑ∈R Zｐ*となる次の式（Ａ２６）に示す入力に対し、式（Ａ２７）に示すあるr＊となる式（Ａ２８）の計算、
【数２６】
2010060716.tif 000190
【数２７】
2010060716.tif 000191
【数２８】
2010060716.tif 000192
および、ランダムな生成元g１∈R G１，g２∈R G２および乱数x，r１，r２，…，rｑ∈R Zｐ*となる次の式（Ａ２９）に示す入力に対し、式（Ａ３０）に示すあるr＊となる式（Ａ３１）の計算、
【数２９】
2010060716.tif 000193
【数３０】
2010060716.tif 000194
【数３１】
2010060716.tif 000195
のそれぞれの計算を、攻撃者が、時間t以内で、高々、あらかじめ定めた定数εの確率でしか行うことができないＩＤベース署名方法。
（８）前記セットアップフェーズにおいて、十分大きな素数の位数p を持つ乗法巡回群G１，G２，GＴ，一方向性同型写像f : G２→ G１ (g１：＝ f(g２))および双線形写像e： G１ ×G２→ GＴ を選び、式（Ａ３２）の乱数αから式（Ａ３３）のMKとして示す前記マスターキーを生成し、式（Ａ３４）を計算する
【数３２】
2010060716.tif 000196
【数３３】
2010060716.tif 000197
【数３４】
2010060716.tif 000198
上記（７）のＩＤベース署名方法。
（９）前記セットアップフェーズにおいて、さらに、式（Ａ３５）に示す乱数の入力に対して式（Ａ３６）に示す出力を生成し、
【数３５】
2010060716.tif 000199
【数３６】
2010060716.tif 000200
前記システムパラメータを、次の式（Ａ３７）のparamsとする
【数３７】
2010060716.tif 000201
上記（８）のＩＤベース署名方法。
（１０）前記エクストラクトフェーズにおいて、前記ＩＤをn１ビットのＩＤ情報とし、式（Ａ３８）に示すidkを前記ＩＤのk番目のビットとした場合、式（Ａ３９）に示す乱数sを選び、
【数３８】
2010060716.tif 000202
【数３９】
2010060716.tif 000203
式（Ａ４０）に示すＩＤに対応するプライベートキーを次の式（Ａ４１）に示すdＩＤとして計算する
【数４０】
2010060716.tif 000204
【数４１】
2010060716.tif 000205
上記（９）のＩＤベース署名方法。
（１１）前記サインフェーズにおいて、前記文書のMをn２ビットの署名文書とし、パブリックキーをIDとし、式（Ａ４２）に示すmkを、前記文書Mのk 番目のビットとした場合、(ID,M)の組に関する署名σを、式（Ａ４３）により生成する
【数４２】
2010060716.tif 000206
【数４３】
2010060716.tif 000207
上記（１０）のＩＤベース署名方法。
（１２）前記ベリファイフェーズにおいて、前記システムパラメータparams、前記パブリックキー、前記文書の組(ID,M)および前記署名σを用いて、式（Ａ４４）を検証し、
【数４４】
2010060716.tif 000208
式（Ａ４４）のすべての等式が成り立つとき、検証結果として正常（valid）を出力し、それ以外のとき、異常（invalid）を出力する上記（１１）のＩＤベース署名方法。
（１３）前記課題を解決する手段における（１）又は前記（２）乃至（６）の何れかに記載のＩＤベース署名システムをコンピュータシステムとして構築したＩＤベース署名システム。
（１４）前記（７）乃至（１２）の何れかに記載のＩＤベース署名方法を、コンピュータにより実行可能なプログラムとして実施するＩＤベース署名プログラム。
（１５）前記（１４）に記載のＩＤベース署名プログラムをコンピュータにより読取可能な記録媒体に記録しているプログラム記録媒体。