ＩＤベース署名システムおよびＩＤベース署名方法
【課題】ランダムオラクルを仮定しない“強” 偽造不可安全なＩＤベース署名方式を提供する。
【解決手段】セキュリティパラメータを入力しシステムパラメータ、マスターキーを返すセットアップフェーズと、前記システムパラメータおよび前記マスターキーおよび任意のＩＤを入力しプライベートキーを返すエクストラクトフェーズと、文書、前記プライベートキーおよび前記システムパラメータを入力し署名を出力するサインフェーズ、および、前記文書、前記ＩＤ、前記署名および前記システムパラメータを入力し正常または異常を返すベリファイフェーズとの各フェーズを有する構成で、攻撃者によりパブリックキーとして発行されるID＊、文書M＊について作成された署名σ＊の組（ID＊,M＊,σ＊）に関し、エクストラクト・クエリにおけるすべてのIDiに対しID＊≠IDiとし、シグネチャ・クエリにおけるすべての（IDi,Mi,σi）に対し（ID＊,M＊,σ＊）≠（IDi,Mi,σi）となる仕組みを実現する。
【解決手段】セキュリティパラメータを入力しシステムパラメータ、マスターキーを返すセットアップフェーズと、前記システムパラメータおよび前記マスターキーおよび任意のＩＤを入力しプライベートキーを返すエクストラクトフェーズと、文書、前記プライベートキーおよび前記システムパラメータを入力し署名を出力するサインフェーズ、および、前記文書、前記ＩＤ、前記署名および前記システムパラメータを入力し正常または異常を返すベリファイフェーズとの各フェーズを有する構成で、攻撃者によりパブリックキーとして発行されるID＊、文書M＊について作成された署名σ＊の組（ID＊,M＊,σ＊）に関し、エクストラクト・クエリにおけるすべてのIDiに対しID＊≠IDiとし、シグネチャ・クエリにおけるすべての（IDi,Mi,σi）に対し（ID＊,M＊,σ＊）≠（IDi,Mi,σi）となる仕組みを実現する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＩＤベース署名システムおよびＩＤベース署名方法に関する。
【背景技術】
【０００２】
以下では、括弧[]で括って示す数字は、下記非特許文献の番号を表す。通常の明細書では、例えば非特許文献１と表記される非特許文献を、本明細書では単に[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Ｔが、次の式（Ａ２）を満たす双線形写像とした場合、
【数１】
【数２】
ランダムな生成元g１ ∈R G１， g２ ∈R G２およびランダムなx, y ∈R Zｐ＊に対する入力として、次の式（Ａ３）に示すg１ｘｙの計算、
【数３】
ランダムな生成元g１∈R G１，g２∈R G２および乱数x，r１，r２，…，rｑ∈R Zｐ*となる次の式（Ａ４）に示す入力に対し、式（Ａ５）に示すあるr＊となる式（Ａ６）の計算、
【数４】
【数５】
【数６】
および、ランダムな生成元g１∈R G１，g２∈R G２および乱数x，r１，r２，…，rｑ∈R Zｐ*となる次の式（Ａ７）に示す入力に対し、式（Ａ８）に示すあるr＊となる式（Ａ９）の計算、
【数７】
【数８】
【数９】
のそれぞれの計算を、攻撃者が、時間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１は一方向性同型写像であり、次の式（１）を満たす;
【００１７】
【数４５】
【００１８】
（４）e : G１×G２→GＴは双線形写像であり、以下の属性（ａ）〜（ｃ）を持つ:
【００１９】
（ａ）双線形性: 任意のu ∈G１、v ∈G２と任意のa，b ∈Zに対し、次の式（２）を満たす。
【００２０】
【数４６】
【００２１】
（ｂ）非退化:次の式（３）を満たす。
【００２２】
【数４７】
【００２３】
（ｃ）計算可能:任意の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１を計算せよ。
【００２６】
【数４８】
【００２７】
もし、次の式（５）が成り立つならば、アルゴリズムA は、(G２，G１)上のco-ＤＨ問題を解くε のアドバンテージを持っているという。ここで、この確率Pｒは、
g１ ∈R G１， g２ ∈R G２,x, y ∈R Zｐ＊およびA のランダムなビット列から選ばれている。
【００２８】
【数４９】
【００２９】
つまり、次の仮定１を設定する。
（仮定１）攻撃者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 とするとき、次の式（６）が成立しなければならない。
【００３８】
【数５０】
【００３９】
１．４．強偽造不可
ここでの強偽造不可の定義は、前述の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＊となる式（１０）を計算せよというものである。
【００４９】
【数５１】
【００５０】
【数５２】
【００５１】
【数５３】
【００５２】
【数５４】
【００５３】
もし、式（１１）が成り立つならば、アルゴリズムA は、第一の問題を解くεのアドバンテージを持っているという。ここで、式（１１）の確率Pｒは、式（７）、式（９）およびAのランダムなビット列から選ばれている。
【００５４】
【数５５】
【００５５】
ここで、次の仮定２を次のように設定する。
（仮定２）攻撃者A が、時間t以内で、第一の問題を解くアドバンテージを高々あらかじめ定めた確率εしか持たないとき、(q，t，ε)−仮定［２］は成り立つという。
【００５６】
次の第二の問題は以下のように与えられる．
つまり、第二の問題は、式（１２）に示すようなランダムな生成元g１∈R G１，g２∈R
G２および乱数x，r１，r２，…，rｑ∈R Zｐ*となる式（１３）に示す入力に対し、式（１４）に示すようなあるr＊となる式（１５）を計算せよというものである。
【００５７】
【数５６】
【００５８】
【数５７】
【００５９】
【数５８】
【００６０】
【数５９】
【００６１】
もし、式（１６）が成り立つならば、アルゴリズムA は、第二の問題を解くεのアドバンテージを持っているという。ここで、式（１６）の確率Pｒは、式（１２）、式（１４）およびAのランダムなビット列から選ばれている。
【００６２】
【数６０】
【００６３】
ここで、次の仮定３を次のように設定する。
（仮定３）攻撃者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)の４つのフェーズから構成される。差し当たり、ＩＤを式（１７）の要素と仮定するが、式（１８）に示すような衝突耐性を持つハッシュ関数を使って、領域を式（１９）のように拡張することもできる。
【００６６】
【数６１】
【００６７】
【数６２】
【００６８】
【数６３】
【００６９】
同様に、署名文書Ｍについても式（２０）の要素と仮定する。
【００７０】
【数６４】
【００７１】
（ａ）セットアップ（Setup）フェーズ：
鍵生成局ＰＫＧは、十分大きな素数の位数p を持つ乗法巡回群G１，G２，GＴ，一方向性同型写像f : G２→ G１ (g１：＝ f(g２))および双線形写像e： G１ ×G２→ GＴ を選ぶ。ＰＫＧは、式（２１）の乱数αからマスターキーとして式（２２）を生成し、式（２３）を計算する。
【００７２】
【数６５】
【００７３】
【数６６】
【００７４】
【数６７】
【００７５】
つまり、次の式（２４）、式（２５）を計算する。
【００７６】
【数６８】
【００７７】
【数６９】
【００７８】
また、鍵生成局ＰＫＧは、式（２６）に示す乱数の入力に対して式（２７）に示す出力を生成する。
【００７９】
【数７０】
【００８０】
【数７１】
【００８１】
ここで、マスターシークレットmaster-keyをMKとし、公開パラメータparamsを、次の式（２８）とする。
【００８２】
【数７２】
【００８３】
（ｂ）エクストラクト（Extract）フェーズ：
IDをn１ビットのID情報とし、式（２９）に示すidkをIDの(左から)k番目のビットとする。
【００８４】
【数７３】
【００８５】
鍵生成局ＰＫＧは、式（３０）に示す乱数sを選び、式（３１）に示すＩＤに対応するprivate key dIDを次の式（３２）に示すように計算する。
【００８６】
【数７４】
【００８７】
【数７５】
【００８８】
【数７６】
【００８９】
（ｃ）サイン（Sign）フェーズ：
M をn２ビットの署名文書とし、式（３３）に示すmkを、Mの(左から)k 番目のビットとする。 (ID,M)の署名σ（式（３４）に示す）は、次の式（３５）のように生成される。ここで、r ∈ Zｐ*は乱数である。
【００９０】
【数７７】
【００９１】
【数７８】
【００９２】
【数７９】
【００９３】
（ｄ）ベリファイ（Verify）フェーズ：
params,(ID,M)および次の式（３６）に示すσを使い、式（３７）を検証する。
【００９４】
【数８０】
【００９５】
【数８１】
【００９６】
式（３７）のすべての等式が成り立つとき、検証結果として正常（valid）を出力し、それ以外のとき、異常（invalid）を出力する。
【００９７】
もし、あるＩＤのentityが、文書Mの署名σ（式（３８）に示す）をSignフェーズにおいて生成したならば、次の式（３９）の計算により、署名σは検証者に受理されることがわかる。よって、この方式は正当である。
【００９８】
【数８２】
【００９９】
【数８３】
【０１００】
３．安全性証明
次に、２項にて説明した本実施形態におけるＩＤベース署名方式の安全性つまり次の（定理１）が成立することを証明する。
（定理１）g１:＝f(g２)となる条件で、(G２，G１)上の(t０，ε０)−ＤＨ仮定、(q１，t１，ε１)−仮定［２］および(q２，t２，ε２)−仮定［３］が成り立つと仮定する。そのとき、前述の本実施形態のＩＤベース署名方式は、(qｅ，qｓ，t，ε)−強偽造不可であり、次の式（４０）を満たす。ここで，TはG２におけるべき剰余計算１回にかかる最大時間とする。
【０１０１】
【数８４】
【０１０２】
次に、以下のアウトラインに沿って、安全性の証明を行う。
【０１０３】
まず、前述した本実施形態のＩＢＳ方式（ＩＤベース署名方式）の安全性を破る攻撃者A の存在および仮定［２］のチャレンジを受け取る挑戦者B の存在を仮定する。攻撃者A
と挑戦者B とは強偽造不可ゲームを実行し、攻撃者Aはvalidとなる(ID，文書，署名)の一組を出力する。次に、挑戦者B は仮定［２］においてvalidとなるレスポンスを計算する。ここで、攻撃者Aの出力は、co-ＤＨ仮定と仮定［３］とに矛盾してはならない。
【０１０４】
（安全性の証明）
本実施形態のＩＢＳ方式の安全性を、(qｅ，qｓ，t，ε)で破る攻撃者Aの存在を仮定する。ここで、仮定［２］ゲームを行うシミュレータBを構成する。シミュレータB は、式（４１）に示す仮定［２］ゲームのチャレンジを受け取る。
【０１０５】
【数８５】
【０１０６】
式（４１）において、α，sｉは、次の式（４２）の通りである。また、シミュレータB は、攻撃者Aと以下の手順を実行する。
【０１０７】
【数８６】
【０１０８】
Ａ．Simulator Description（シミュレータの構成）
Setup：
シミュレータB は、式（４３）の乱数から式（４４）の情報を生成し、Aに対して、式（４５）の情報を送信する。
【０１０９】
【数８７】
【０１１０】
【数８８】
【０１１１】
【数８９】
【０１１２】
（Ａ．１）クエリ（Queries）：
攻撃者A は、シミュレータつまり挑戦者Bへ多くの異なるQueryを適応的に行う。
【０１１３】
UｅをExtract QueriesにおけるID情報の添え字集合、UｓをSignature QueriesにおけるID情報の添え字集合とし、式（４６）と置く。また、μｓｉ（つまり式（４７）に示す）を、Signature
QueriesにおけるIDｉ（式（４８）に示す）の文書の添え字集合とする。
【０１１４】
【数９０】
【０１１５】
【数９１】
【０１１６】
【数９２】
【０１１７】
ここで、各Queryは以下の中の一つである。
【０１１８】
（Ａ−Ｅ）Extract Queries：
攻撃者Aは、シミュレータBに対し、適応的に、Extract Queries IDｉ(i ∈Uｅ)を行う。式（４９）に示すIDｉに対し、次の式（５０）と仮定する。
【０１１９】
【数９３】
【０１２０】
【数９４】
【０１２１】
(Ａ−Ｅ１)：
もし、式（５１）が成立するならば、シミュレータB はこのゲームを中断する。
【０１２２】
【数９５】
【０１２３】
(Ａ−Ｅ２)：
式（５１）が成立しないその他の場合(すなわち、式（５２）の場合)、シミュレータB はゲームを中断せずに、IDｉに対応するdｉ＝(dｉ,１，dｉ,２)を、次の式（５３）、式（５４）のように、生成し、それをAへ送信する。
【０１２４】
【数９６】
【０１２５】
【数９７】
【０１２６】
【数９８】
【０１２７】
なお、式（５４）において、上線付きのsｉは、次の式（５５）で与えられる。
【０１２８】
【数９９】
【０１２９】
式（５３）のすべてのsｉ ∈Ｒ Zｐ＊を消去することにより、式（５４）のすべての上線付きのsｉ（式（５６）に示す）は乱数と看做すことができることに注意を要する。
【０１３０】
【数１００】
【０１３１】
（Ａ−Ｓ）Signature Queries：
攻撃者A は、シミュレータBに対し、適応的に、次の式（５７）に示すSignature Queries(IDｉ，Mｉ,ｊ)を行う。
【０１３２】
【数１０１】
【０１３３】
ｉ ∈ Uｓのとき、Xｉを式（５０）のように仮定し、式（５８）に対し、次の式（５９）と仮定する。
【０１３４】
【数１０２】
【０１３５】
【数１０３】
【０１３６】
(Ａ−Ｓ１)：
もし、式（６０）が成立するならば、シミュレータB はこのゲームを中断する。
【０１３７】
【数１０４】
【０１３８】
(Ａ−Ｓ２)：
式（６０）が成立しないその他の場合(すなわち、式（６１）の場合)、シミュレータB は、このゲームを中断せずに、(IDｉ，Mｉ,ｊ)に対応する式（６２）のそれぞれを、式（６３）のように生成し、それをAへ送信する。
【０１３９】
【数１０５】
【０１４０】
【数１０６】
【０１４１】
【数１０７】
【０１４２】
なお、式（６３）において、上線付きのsｉおよびrｉ,ｊは、次の式（６４）で与えられる。
【０１４３】
【数１０８】
【０１４４】
式（６３）のすべてのsｉおよびrｉ,ｊ（式（６５）に示す）を消去することにより、式（５４）のすべての上線付きのsｉおよびrｉ,ｊ（式（６６）に示す）は乱数と看做すことができることに注意を要する。
【０１４５】
【数１０９】
【０１４６】
【数１１０】
【０１４７】
（Ａ．２）アウトプット（Output）：
攻撃者Aは、(ID＊，M＊，σ＊)を出力する。ただし、式（６７）に示すσ＊は、(ID＊，M＊)に対するvalidな署名であり、エクストラクト・クエリにおけるすべてのIDiに対しID＊≠IDiとし、シグネチャ・クエリにおけるすべての（IDi,Mi,σi）に対し（ID＊,M＊,σ＊）≠（IDi,Mi,σi）とする。
【０１４８】
【数１１１】
【０１４９】
（Ａ．３）アーティフィシャル・アボート（Artificial Abort）：
式（６８）に示すＩＤ情報ID＊および文書M＊に対し、式（６９）と仮定する。
【０１５０】
【数１１２】
【０１５１】
【数１１３】
【０１５２】
ここで、次の式（７０）または式（７１）が成立するならば、シミュレータB はこのゲームを強制的に中断する。
【０１５３】
【数１１４】
【０１５４】
【数１１５】
【０１５５】
Ｂ．シミュレーション結果の分析
攻撃者A は、式（７２）が成立するときとして、前述の（Ａ−Ｅ１）、（Ａ−Ｓ１）に示すような中断があるSimulator Descriptionゲームと、中断のない強偽造不可ゲームとを区別することができない。
【０１５６】
【数１１６】
【０１５７】
その理由は、式（７３）の条件を満たす確率Pｒは、式（７４）が成立するとき、negligibleな値となるからである。ゆえに、以降では、Simulator Descriptionゲ−ムのみを考えていけば良い。
【０１５８】
【数１１７】
【０１５９】
【数１１８】
【０１６０】
Simulator Descriptionゲームの場合、σ＊はvalidなので、式（７５）と仮定する。なお、式（７５）において、上線付きのs＊，r＊は、式（７６）である。
【０１６１】
【数１１９】
【０１６２】
【数１２０】
【０１６３】
（Ｂ−１）
もし、式（７７）が成立するならば、式（７８）である。そのとき、B は、式（７９）に示すあるs＊となる組を式（８０）として生成する。式（８０）に示す組は、仮定［２］チャレンジに対するvalidな出力となる。
【０１６４】
【数１２１】
【０１６５】
【数１２２】
【０１６６】
【数１２３】
【０１６７】
【数１２４】
【０１６８】
（Ｂ−２）
次に、式（７７）が成立しないその他の場合（すなわち、式（８１）の場合）について考える。
【０１６９】
【数１２５】
【０１７０】
（Ｂ−２．１）
式（８２）と仮定し(これは強偽造不可安全の定義による)、また、式（８３）と仮定する。
【０１７１】
【数１２６】
【０１７２】
【数１２７】
【０１７３】
式（８２）、式（８３）を仮定したとき、式（８４）を考えれば十分である。これは、A が、式（８５）のすべてを知っている場合(つまり、式（８６）の場合)を意味している。あるε’≦εに対し、式（８４）≧ε’と仮定する。
【０１７４】
【数１２８】
【０１７５】
【数１２９】
【０１７６】
【数１３０】
【０１７７】
（Ｂ−２．１．１）
s＊ ＝ sｌを満たす数l ∈ U が存在すると仮定する。式（８４）において、もし、A が、式（８７）に示す上線付きのsｉ，rｉ，ｊのすべておよび式（８８）に示すg２αを知ったとき、式（８４）から式（８９）を消去することができる。
【０１７８】
【数１３１】
【０１７９】
【数１３２】
【０１８０】
【数１３３】
【０１８１】
また、式（９０）が成立するので、出力の第３成分を式（９１）に置き換え、残りの成分を消去する。
【０１８２】
【数１３４】
【０１８３】
【数１３５】
【０１８４】
ゆえに、A は、式（９２）を解くためのアドバンテージε′を持つ。ここで、この問題は、式（９３）、式（５０）におけるXｉ(ｉ ∈ U)、式（５９）における式（９４）、式（６９）におけるX＊，Y＊およびA のランダムなビット列から選ばれる。
【０１８５】
【数１３６】
【０１８６】
【数１３７】
【０１８７】
【数１３８】
【０１８８】
ここで、ｉ ∈ Uについて、式（９５）と置く。
【０１８９】
【数１３９】
【０１９０】
また、式（９６）が成立するので、A は式（９７）から式（９８）を計算することができる。
【０１９１】
【数１４０】
【０１９２】
【数１４１】
【０１９３】
【数１４２】
【０１９４】
よって、式（９８）に示す各パラメータを式（９２）から消去する。また、式（９９）は、式（１００）に示す式（９２）の出力とは関連性がないので、式（９９）に示すこれらの入力パラメータも式（９２）から消去することができる。
【０１９５】
【数１４３】
【０１９６】
【数１４４】
【０１９７】
式（９２）において、式(１０１)を式（１０２）へ置き換えることにより、Aは、式（１０３）を解くためのアドバンテージε′を持つ。
【０１９８】
【数１４５】
【０１９９】
【数１４６】
【０２００】
【数１４７】
【０２０１】
ここで、（式（１０４）のときでさえ、)式（１０５）が成立するので、式（１０６）が成立することに注意を要する。
【０２０２】
【数１４８】
【０２０３】
【数１４９】
【０２０４】
【数１５０】
【０２０５】
式（１０７）と仮定する。式（１０８）に示すx′を式（９２）から消去したため，h をZｐ＊の乱数として良い。
【０２０６】
【数１５１】
【０２０７】
【数１５２】
【０２０８】
これは、A が、式（１０９）を解くのにアドバンテージε′を持つことに等しい。ここで、この問題は、式（１１０）およびA のランダムなビット列から選ばれる。
【０２０９】
【数１５３】
【０２１０】
【数１５４】
【０２１１】
F. Baoらによる“Variations of Diffie-Hellman problem”（Proc.ICICS2003, Springer-Verlag, 2003）の記載内容から、これは、式（１１１）を解くのにアドバンテージε′をA が持つことに等しい。
【０２１２】
【数１５５】
【０２１３】
ここで、この問題は式（１１２）およびA のランダムなビット列から選ばれる。これは、A が(G２,G１)上のco-ＤＨ問題をnon-negligibleな確率で解くことができることを意味している。
【０２１４】
【数１５６】
【０２１５】
（Ｂ−２．１．２）
s＊ ＝ sｉを満たす数i ∈ U が存在しないその他の場合(すなわち、式（１１３）の場合)、Aは、x′，x１,x２，…，xｎ１，ｙ′，ｙ１,ｙ２，…，ｙｎ２の値を知っているものと仮定する。
【０２１６】
【数１５７】
【０２１７】
そのとき、式（８４）から式（１１４）を消去することができる。また、式（１１５）に示す組を仮定［２］チャレンジの出力と考えると、式（８４）から式（１１６）を消去することができる。
【０２１８】
【数１５８】
【０２１９】
【数１５９】
【０２２０】
【数１６０】
【０２２１】
これらは、式（８４）の確率Pｒが、仮定［２］の矛盾となるように変形することができることを意味している。
【０２２２】
（Ｂ−２．２）
式（８２）、式（８３）が成立しないその他の場合(すなわち、式（１１７）の場合であり、また、式（１１８）である場合)、X＊ ＝ Xｌである。この場合、Aが、式（１１９）の数値を知っている場合の式（１２０）に示す確率Pｒを考えれば十分である。ε’＋ε”＝εとなるあるε”に対し、式（１２０）≧ε”と仮定する。
【０２２３】
【数１６１】
【０２２４】
【数１６２】
【０２２５】
【数１６３】
【０２２６】
【数１６４】
【０２２７】
（Ｂ−２．２．１）
まず、式（１２１）と仮定する。
【０２２８】
【数１６５】
【０２２９】
（Ｂ−２．２．１．１）
r＊＝rｌ,ｋとなるような式（１２２）に示す数kが存在すると仮定する。式（１２０）において、もし、Aが、式（１２３）に示す上線付きのrｌ、ｊとsｌとのすべてを知っているならば、式（１２０）から式（１２４）を消去することができる。
【０２３０】
【数１６６】
【０２３１】
【数１６７】
【０２３２】
【数１６８】
【０２３３】
また、式（１２５）が成立するので、出力の第２成分を式（１２６）に置き換え、第３成分と第４成分とを消去する。
【０２３４】
【数１６９】
【０２３５】
【数１７０】
【０２３６】
ゆえに、A は、式（１２７）を解くためのアドバンテージε”を持つ。ここで、この問題は、式（１２８）、式（５９）における式（１２９）、式（６９）におけるY＊およびA
のランダムなビット列から選ばれる。
【０２３７】
【数１７１】
【０２３８】
【数１７２】
【０２３９】
【数１７３】
【０２４０】
ここで、式（１３０）に示す数jに対し、式（１３１）と置く。
【０２４１】
【数１７４】
【０２４２】
【数１７５】
【０２４３】
式（１３２）が成立するので，A は、式（１３３）から式（１３４）を計算することができる。
【０２４４】
【数１７６】
【０２４５】
【数１７７】
【０２４６】
【数１７８】
【０２４７】
よって、式（１３４）に示す各パラメータを式（１２７）から消去する。また、式（１２７)において、式（１３５）を式（１３６）へ置き換えると、A は、式（１３７）を解くためのアドバンテージε”を持つ。前述の(Ｂ−２．１．１)にて説明した場合と同様に、これは、A が、(G２，G１)上のco-ＤＨ問題をnon-negligibleな確率で解くことができることを意味している。
【０２４８】
【数１７９】
【０２４９】
【数１８０】
【０２５０】
【数１８１】
【０２５１】
（Ｂ−２．２．１．２）
r＊＝rｌ,ｋとなるような式（１２２）に示す数kが存在しないその他の場合(すなわち、式（１３８）となる場合)、A は、x′，x１，x２，…，xｎ１と同様に、y′，y１，y２，…，yｎ２も知っていると仮定する。そのとき、式（１３９）の等式から、式（１２０）の確率Pｒの変形は、仮定［３］に矛盾する。
【０２５２】
【数１８２】
【０２５３】
【数１８３】
【０２５４】
（Ｂ−２．２．２）
次に、式（１２１）を仮定しないその他の場合(すなわち、式（１４０）が成立する場合)、式（１４１）が示す数を次の式（１４２）が成立するすべての数とする。
【０２５５】
【数１８４】
【０２５６】
【数１８５】
【０２５７】
【数１８６】
【０２５８】
そのとき、式（１４３）から式（１４４）となる。また、式（１４５）を式（１４６）とする。これは式（１４７）を意味している。
【０２５９】
【数１８７】
【０２６０】
【数１８８】
【０２６１】
【数１８９】
【０２６２】
【数１９０】
【０２６３】
【数１９１】
【０２６４】
（Ｂ−２．２．２．１）
式（１４８）が成立するときであり、かつ、r＊ = rｋとなる式（１４９）の数ｋが存在すると仮定する。
【０２６５】
【数１９２】
【０２６６】
【数１９３】
【０２６７】
このとき、前述の(Ｂ−２．２．１．１)の場合のように、Aは、(G２，G１)上のco-ＤＨ問題をnon-negligibleな確率で解くことができる。
【０２６８】
（Ｂ−２．２．２．２）
式（１４８）が成立しない場合あるいはr＊ = rｋとなる式（１４９）の数ｋが存在しないその他の場合(すなわち、式（１５０）が成立する場合あるいは式（１５１）が成立する場合)、式（１５２）に示す組は、仮定［３］チャレンジのvalid出力である。
【０２６９】
【数１９４】
【０２７０】
【数１９５】
【０２７１】
【数１９６】
【０２７２】
シミュレーションにおいて、式（１５３）のいずれも満たさない場合の確率は、次の式（１５４）で与えられる。
【０２７３】
【数１９７】
【０２７４】
【数１９８】
【０２７５】
よって、本発明に係わるＩＤベース署名方式S においては、式（１５５）が成立する。
【０２７６】
【数１９９】
【０２７７】
以上の（Ｂ−１）および（Ｂ−２）から、式（１５６）に示す確率Pｒ（≧ε＝ε´＋ε”）は、少なくとも、式（１５５）の左辺の確率Pｒより高い。事象A１，A２に対し、式（１５７）、式（１５８）であるので、式（１５９）である。
【０２７８】
【数２００】
【０２７９】
【数２０１】
【０２８０】
【数２０２】
【０２８１】
【数２０３】
【０２８２】
これは、(t０，ε０)−co-ＤＨ仮定、(q１，t１，ε１)−仮定［２］または(q２，t２，ε２)−仮定［３］に矛盾する。よって、本発明に係わるＩＤベース署名方式は、(qｅ，qｓ，t，ε)−強偽造不可安全である。
【０２８３】
もし、A が、前述の「Ａ．Simulator Description（シミュレータの構成）」に記載のゲームについて、時間t 内の確率ε で、validな偽造を出力したならば、それは、Bが仮定［２］ゲームについて、または、A がco-ＤＨゲームあるいは仮定［３］ゲームについて、式（１６０）に示す時間以内に、式（１６１）に示す確率で成功することを意味している。
【０２８４】
【数２０４】
【０２８５】
【数２０５】
【０２８６】
よって、式（１６２）に示す仮定が必要である。これは、式（１６３）であることを意味している。以上より、前述した定理１は証明された。
【０２８７】
【数２０６】
【０２８８】
【数２０７】
【０２８９】
本発明に係わるＩＢＳ方式は、前述のように、強偽造不可の安全性を満たすことができた。その理由の一つは、３つの数学的仮定と１つの一方向性同型写像f とを使い、安全性証明を直接的に行うことができるからということができる。
【０２９０】
４．結論
以上に詳細に説明したように、本発明においては、５個の署名パラメータからなる、強偽造不可ＩＢＳ方式のスタンダードモデルを提供している。本発明によるＩＢＳ方式の署名長は、Diffie−Hellman問題あるいは離散対数問題に関連した問題をベースにした他のＩＢＳ方式と比較して短い。なお、本発明に係わるＩＢＳ方式の安全性は、前述したように、Diffie−Hellman問題と一方向性同型写像に関連した３つの問題を解くことの困難性に基づいている。
【０２９１】
以上、本発明の好適実施例の構成を説明した。しかし、斯かる実施例は、本発明の単なる例示に過ぎず、何ら本発明を限定するものではないことに留意されたい。本発明の要旨を逸脱することなく、特定用途に応じて種々の変形変更が可能であることが、当業者には容易に理解できよう。例えば、本発明の実施態様は、課題を解決するための手段における構成（１）に加えて、次のような構成として表現できる。
（２）前記セットアップフェーズにおいて、十分大きな素数の位数p を持つ乗法巡回群G１，G２，GＴ，一方向性同型写像f : G２→ G１ (g１：＝ f(g２))および双線形写像e： G１ ×G２→ GＴ を選び、式（Ａ１０）の乱数αから式（Ａ１１）のMKとして示す前記マスターキーを生成し、式（Ａ１２）を計算する
【数１０】
【数１１】
【数１２】
上記（１）のＩＤベース署名システム。
（３）前記セットアップフェーズにおいて、さらに、式（Ａ１３）に示す乱数の入力に対して式（Ａ１４）に示す出力を生成し、
【数１３】
【数１４】
前記システムパラメータを、次の式（Ａ１５）のparamsとする
【数１５】
上記（２）のＩＤベース署名システム。
（４）前記エクストラクトフェーズにおいて、前記ＩＤをn１ビットのＩＤ情報とし、式（Ａ１６）に示すidkを前記ＩＤのk番目のビットとした場合、式（Ａ１７）に示す乱数sを選び、
【数１６】
【数１７】
式（Ａ１８）に示すＩＤに対応するプライベートキーを次の式（Ａ１９）に示すdＩＤとして計算する
【数１８】
【数１９】
上記（３）のＩＤベース署名システム。
（５）前記サインフェーズにおいて、前記文書のMをn２ビットの署名文書とし、パブリックキーをIDとし、式（Ａ２０）に示すmkを、前記文書Mのk 番目のビットとした場合、(ID,M)の組に関する署名σを、式（Ａ２１）により生成する
【数２０】
【数２１】
上記（４）のＩＤベース署名システム。
（６）前記ベリファイフェーズにおいて、前記システムパラメータparams、前記パブリックキー、前記文書の組(ID,M)および前記署名σを用いて、式（Ａ２２）を検証し、
【数２２】
式（Ａ２２）のすべての等式が成り立つとき、検証結果として正常（valid）を出力し、それ以外のとき、異常（invalid）を出力する上記（５）のＩＤベース署名システム。
（７）セキュリティパラメータを入力としてシステムパラメータおよびマスターキーを返すセットアップ（Ｓｅｔｕｐ）フェーズと、該セットアップフェーズが出力する前記システムパラメータおよび前記マスターキーおよび任意のＩＤを入力としてプライベートキーを返すエクストラクト（Ｅｘｔｒａｃｔ）フェーズと、文書、前記エクストラクトフェーズが出力する前記プライベートキーおよび前記セットアップフェーズが出力する前記システムパラメータを入力として、署名を出力するサイン（Ｓｉｇｎ）フェーズ、および、前記文書、前記ＩＤ、前記サインフェーズが出力する前記署名および前記セットアップフェーズが出力する前記システムパラメータを入力として、正常（ｖａｌｉｄ）または異常（ｉｎｖａｌｉｄ）のいずれかを返すベリファイ（Ｖｅｒｉｆｙ）フェーズとの各フェーズを有するＩＤベース署名方法において、
G１,G２,GＴが素数p の位数を持つ乗法巡回群であり、g２はG２の生成元であり、ｆ：G２→G１が、次の式（Ａ２３）を満たす一方向性同型写像であり、e: G１×G２→GＴが、次の式（Ａ２４）を満たす双線形写像とした場合、
【数２３】
【数２４】
ランダムな生成元g１ ∈R G１， g２ ∈R G２およびランダムなx, y ∈R Zｐ＊に対する入力として、次の式（Ａ２５）に示すg１ｘｙの計算、
【数２５】
ランダムな生成元g１∈R G１，g２∈R G２および乱数x，r１，r２，…，rｑ∈R Zｐ*となる次の式（Ａ２６）に示す入力に対し、式（Ａ２７）に示すあるr＊となる式（Ａ２８）の計算、
【数２６】
【数２７】
【数２８】
および、ランダムな生成元g１∈R G１，g２∈R G２および乱数x，r１，r２，…，rｑ∈R Zｐ*となる次の式（Ａ２９）に示す入力に対し、式（Ａ３０）に示すあるr＊となる式（Ａ３１）の計算、
【数２９】
【数３０】
【数３１】
のそれぞれの計算を、攻撃者が、時間t以内で、高々、あらかじめ定めた定数εの確率でしか行うことができないＩＤベース署名方法。
（８）前記セットアップフェーズにおいて、十分大きな素数の位数p を持つ乗法巡回群G１，G２，GＴ，一方向性同型写像f : G２→ G１ (g１：＝ f(g２))および双線形写像e： G１ ×G２→ GＴ を選び、式（Ａ３２）の乱数αから式（Ａ３３）のMKとして示す前記マスターキーを生成し、式（Ａ３４）を計算する
【数３２】
【数３３】
【数３４】
上記（７）のＩＤベース署名方法。
（９）前記セットアップフェーズにおいて、さらに、式（Ａ３５）に示す乱数の入力に対して式（Ａ３６）に示す出力を生成し、
【数３５】
【数３６】
前記システムパラメータを、次の式（Ａ３７）のparamsとする
【数３７】
上記（８）のＩＤベース署名方法。
（１０）前記エクストラクトフェーズにおいて、前記ＩＤをn１ビットのＩＤ情報とし、式（Ａ３８）に示すidkを前記ＩＤのk番目のビットとした場合、式（Ａ３９）に示す乱数sを選び、
【数３８】
【数３９】
式（Ａ４０）に示すＩＤに対応するプライベートキーを次の式（Ａ４１）に示すdＩＤとして計算する
【数４０】
【数４１】
上記（９）のＩＤベース署名方法。
（１１）前記サインフェーズにおいて、前記文書のMをn２ビットの署名文書とし、パブリックキーをIDとし、式（Ａ４２）に示すmkを、前記文書Mのk 番目のビットとした場合、(ID,M)の組に関する署名σを、式（Ａ４３）により生成する
【数４２】
【数４３】
上記（１０）のＩＤベース署名方法。
（１２）前記ベリファイフェーズにおいて、前記システムパラメータparams、前記パブリックキー、前記文書の組(ID,M)および前記署名σを用いて、式（Ａ４４）を検証し、
【数４４】
式（Ａ４４）のすべての等式が成り立つとき、検証結果として正常（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Ｔが、次の式（Ａ２）を満たす双線形写像とした場合、
【数１】
【数２】
ランダムな生成元g１ ∈R G１， g２ ∈R G２およびランダムなx, y ∈R Zｐ＊に対する入力として、次の式（Ａ３）に示すg１ｘｙの計算、
【数３】
ランダムな生成元g１∈R G１，g２∈R G２および乱数x，r１，r２，…，rｑ∈R Zｐ*となる次の式（Ａ４）に示す入力に対し、式（Ａ５）に示すあるr＊となる式（Ａ６）の計算、
【数４】
【数５】
【数６】
および、ランダムな生成元g１∈R G１，g２∈R G２および乱数x，r１，r２，…，rｑ∈R Zｐ*となる次の式（Ａ７）に示す入力に対し、式（Ａ８）に示すあるr＊となる式（Ａ９）の計算、
【数７】
【数８】
【数９】
のそれぞれの計算を、攻撃者が、時間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１は一方向性同型写像であり、次の式（１）を満たす;
【００１７】
【数４５】
【００１８】
（４）e : G１×G２→GＴは双線形写像であり、以下の属性（ａ）〜（ｃ）を持つ:
【００１９】
（ａ）双線形性: 任意のu ∈G１、v ∈G２と任意のa，b ∈Zに対し、次の式（２）を満たす。
【００２０】
【数４６】
【００２１】
（ｂ）非退化:次の式（３）を満たす。
【００２２】
【数４７】
【００２３】
（ｃ）計算可能:任意の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１を計算せよ。
【００２６】
【数４８】
【００２７】
もし、次の式（５）が成り立つならば、アルゴリズムA は、(G２，G１)上のco-ＤＨ問題を解くε のアドバンテージを持っているという。ここで、この確率Pｒは、
g１ ∈R G１， g２ ∈R G２,x, y ∈R Zｐ＊およびA のランダムなビット列から選ばれている。
【００２８】
【数４９】
【００２９】
つまり、次の仮定１を設定する。
（仮定１）攻撃者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 とするとき、次の式（６）が成立しなければならない。
【００３８】
【数５０】
【００３９】
１．４．強偽造不可
ここでの強偽造不可の定義は、前述の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＊となる式（１０）を計算せよというものである。
【００４９】
【数５１】
【００５０】
【数５２】
【００５１】
【数５３】
【００５２】
【数５４】
【００５３】
もし、式（１１）が成り立つならば、アルゴリズムA は、第一の問題を解くεのアドバンテージを持っているという。ここで、式（１１）の確率Pｒは、式（７）、式（９）およびAのランダムなビット列から選ばれている。
【００５４】
【数５５】
【００５５】
ここで、次の仮定２を次のように設定する。
（仮定２）攻撃者A が、時間t以内で、第一の問題を解くアドバンテージを高々あらかじめ定めた確率εしか持たないとき、(q，t，ε)−仮定［２］は成り立つという。
【００５６】
次の第二の問題は以下のように与えられる．
つまり、第二の問題は、式（１２）に示すようなランダムな生成元g１∈R G１，g２∈R
G２および乱数x，r１，r２，…，rｑ∈R Zｐ*となる式（１３）に示す入力に対し、式（１４）に示すようなあるr＊となる式（１５）を計算せよというものである。
【００５７】
【数５６】
【００５８】
【数５７】
【００５９】
【数５８】
【００６０】
【数５９】
【００６１】
もし、式（１６）が成り立つならば、アルゴリズムA は、第二の問題を解くεのアドバンテージを持っているという。ここで、式（１６）の確率Pｒは、式（１２）、式（１４）およびAのランダムなビット列から選ばれている。
【００６２】
【数６０】
【００６３】
ここで、次の仮定３を次のように設定する。
（仮定３）攻撃者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)の４つのフェーズから構成される。差し当たり、ＩＤを式（１７）の要素と仮定するが、式（１８）に示すような衝突耐性を持つハッシュ関数を使って、領域を式（１９）のように拡張することもできる。
【００６６】
【数６１】
【００６７】
【数６２】
【００６８】
【数６３】
【００６９】
同様に、署名文書Ｍについても式（２０）の要素と仮定する。
【００７０】
【数６４】
【００７１】
（ａ）セットアップ（Setup）フェーズ：
鍵生成局ＰＫＧは、十分大きな素数の位数p を持つ乗法巡回群G１，G２，GＴ，一方向性同型写像f : G２→ G１ (g１：＝ f(g２))および双線形写像e： G１ ×G２→ GＴ を選ぶ。ＰＫＧは、式（２１）の乱数αからマスターキーとして式（２２）を生成し、式（２３）を計算する。
【００７２】
【数６５】
【００７３】
【数６６】
【００７４】
【数６７】
【００７５】
つまり、次の式（２４）、式（２５）を計算する。
【００７６】
【数６８】
【００７７】
【数６９】
【００７８】
また、鍵生成局ＰＫＧは、式（２６）に示す乱数の入力に対して式（２７）に示す出力を生成する。
【００７９】
【数７０】
【００８０】
【数７１】
【００８１】
ここで、マスターシークレットmaster-keyをMKとし、公開パラメータparamsを、次の式（２８）とする。
【００８２】
【数７２】
【００８３】
（ｂ）エクストラクト（Extract）フェーズ：
IDをn１ビットのID情報とし、式（２９）に示すidkをIDの(左から)k番目のビットとする。
【００８４】
【数７３】
【００８５】
鍵生成局ＰＫＧは、式（３０）に示す乱数sを選び、式（３１）に示すＩＤに対応するprivate key dIDを次の式（３２）に示すように計算する。
【００８６】
【数７４】
【００８７】
【数７５】
【００８８】
【数７６】
【００８９】
（ｃ）サイン（Sign）フェーズ：
M をn２ビットの署名文書とし、式（３３）に示すmkを、Mの(左から)k 番目のビットとする。 (ID,M)の署名σ（式（３４）に示す）は、次の式（３５）のように生成される。ここで、r ∈ Zｐ*は乱数である。
【００９０】
【数７７】
【００９１】
【数７８】
【００９２】
【数７９】
【００９３】
（ｄ）ベリファイ（Verify）フェーズ：
params,(ID,M)および次の式（３６）に示すσを使い、式（３７）を検証する。
【００９４】
【数８０】
【００９５】
【数８１】
【００９６】
式（３７）のすべての等式が成り立つとき、検証結果として正常（valid）を出力し、それ以外のとき、異常（invalid）を出力する。
【００９７】
もし、あるＩＤのentityが、文書Mの署名σ（式（３８）に示す）をSignフェーズにおいて生成したならば、次の式（３９）の計算により、署名σは検証者に受理されることがわかる。よって、この方式は正当である。
【００９８】
【数８２】
【００９９】
【数８３】
【０１００】
３．安全性証明
次に、２項にて説明した本実施形態におけるＩＤベース署名方式の安全性つまり次の（定理１）が成立することを証明する。
（定理１）g１:＝f(g２)となる条件で、(G２，G１)上の(t０，ε０)−ＤＨ仮定、(q１，t１，ε１)−仮定［２］および(q２，t２，ε２)−仮定［３］が成り立つと仮定する。そのとき、前述の本実施形態のＩＤベース署名方式は、(qｅ，qｓ，t，ε)−強偽造不可であり、次の式（４０）を満たす。ここで，TはG２におけるべき剰余計算１回にかかる最大時間とする。
【０１０１】
【数８４】
【０１０２】
次に、以下のアウトラインに沿って、安全性の証明を行う。
【０１０３】
まず、前述した本実施形態のＩＢＳ方式（ＩＤベース署名方式）の安全性を破る攻撃者A の存在および仮定［２］のチャレンジを受け取る挑戦者B の存在を仮定する。攻撃者A
と挑戦者B とは強偽造不可ゲームを実行し、攻撃者Aはvalidとなる(ID，文書，署名)の一組を出力する。次に、挑戦者B は仮定［２］においてvalidとなるレスポンスを計算する。ここで、攻撃者Aの出力は、co-ＤＨ仮定と仮定［３］とに矛盾してはならない。
【０１０４】
（安全性の証明）
本実施形態のＩＢＳ方式の安全性を、(qｅ，qｓ，t，ε)で破る攻撃者Aの存在を仮定する。ここで、仮定［２］ゲームを行うシミュレータBを構成する。シミュレータB は、式（４１）に示す仮定［２］ゲームのチャレンジを受け取る。
【０１０５】
【数８５】
【０１０６】
式（４１）において、α，sｉは、次の式（４２）の通りである。また、シミュレータB は、攻撃者Aと以下の手順を実行する。
【０１０７】
【数８６】
【０１０８】
Ａ．Simulator Description（シミュレータの構成）
Setup：
シミュレータB は、式（４３）の乱数から式（４４）の情報を生成し、Aに対して、式（４５）の情報を送信する。
【０１０９】
【数８７】
【０１１０】
【数８８】
【０１１１】
【数８９】
【０１１２】
（Ａ．１）クエリ（Queries）：
攻撃者A は、シミュレータつまり挑戦者Bへ多くの異なるQueryを適応的に行う。
【０１１３】
UｅをExtract QueriesにおけるID情報の添え字集合、UｓをSignature QueriesにおけるID情報の添え字集合とし、式（４６）と置く。また、μｓｉ（つまり式（４７）に示す）を、Signature
QueriesにおけるIDｉ（式（４８）に示す）の文書の添え字集合とする。
【０１１４】
【数９０】
【０１１５】
【数９１】
【０１１６】
【数９２】
【０１１７】
ここで、各Queryは以下の中の一つである。
【０１１８】
（Ａ−Ｅ）Extract Queries：
攻撃者Aは、シミュレータBに対し、適応的に、Extract Queries IDｉ(i ∈Uｅ)を行う。式（４９）に示すIDｉに対し、次の式（５０）と仮定する。
【０１１９】
【数９３】
【０１２０】
【数９４】
【０１２１】
(Ａ−Ｅ１)：
もし、式（５１）が成立するならば、シミュレータB はこのゲームを中断する。
【０１２２】
【数９５】
【０１２３】
(Ａ−Ｅ２)：
式（５１）が成立しないその他の場合(すなわち、式（５２）の場合)、シミュレータB はゲームを中断せずに、IDｉに対応するdｉ＝(dｉ,１，dｉ,２)を、次の式（５３）、式（５４）のように、生成し、それをAへ送信する。
【０１２４】
【数９６】
【０１２５】
【数９７】
【０１２６】
【数９８】
【０１２７】
なお、式（５４）において、上線付きのsｉは、次の式（５５）で与えられる。
【０１２８】
【数９９】
【０１２９】
式（５３）のすべてのsｉ ∈Ｒ Zｐ＊を消去することにより、式（５４）のすべての上線付きのsｉ（式（５６）に示す）は乱数と看做すことができることに注意を要する。
【０１３０】
【数１００】
【０１３１】
（Ａ−Ｓ）Signature Queries：
攻撃者A は、シミュレータBに対し、適応的に、次の式（５７）に示すSignature Queries(IDｉ，Mｉ,ｊ)を行う。
【０１３２】
【数１０１】
【０１３３】
ｉ ∈ Uｓのとき、Xｉを式（５０）のように仮定し、式（５８）に対し、次の式（５９）と仮定する。
【０１３４】
【数１０２】
【０１３５】
【数１０３】
【０１３６】
(Ａ−Ｓ１)：
もし、式（６０）が成立するならば、シミュレータB はこのゲームを中断する。
【０１３７】
【数１０４】
【０１３８】
(Ａ−Ｓ２)：
式（６０）が成立しないその他の場合(すなわち、式（６１）の場合)、シミュレータB は、このゲームを中断せずに、(IDｉ，Mｉ,ｊ)に対応する式（６２）のそれぞれを、式（６３）のように生成し、それをAへ送信する。
【０１３９】
【数１０５】
【０１４０】
【数１０６】
【０１４１】
【数１０７】
【０１４２】
なお、式（６３）において、上線付きのsｉおよびrｉ,ｊは、次の式（６４）で与えられる。
【０１４３】
【数１０８】
【０１４４】
式（６３）のすべてのsｉおよびrｉ,ｊ（式（６５）に示す）を消去することにより、式（５４）のすべての上線付きのsｉおよびrｉ,ｊ（式（６６）に示す）は乱数と看做すことができることに注意を要する。
【０１４５】
【数１０９】
【０１４６】
【数１１０】
【０１４７】
（Ａ．２）アウトプット（Output）：
攻撃者Aは、(ID＊，M＊，σ＊)を出力する。ただし、式（６７）に示すσ＊は、(ID＊，M＊)に対するvalidな署名であり、エクストラクト・クエリにおけるすべてのIDiに対しID＊≠IDiとし、シグネチャ・クエリにおけるすべての（IDi,Mi,σi）に対し（ID＊,M＊,σ＊）≠（IDi,Mi,σi）とする。
【０１４８】
【数１１１】
【０１４９】
（Ａ．３）アーティフィシャル・アボート（Artificial Abort）：
式（６８）に示すＩＤ情報ID＊および文書M＊に対し、式（６９）と仮定する。
【０１５０】
【数１１２】
【０１５１】
【数１１３】
【０１５２】
ここで、次の式（７０）または式（７１）が成立するならば、シミュレータB はこのゲームを強制的に中断する。
【０１５３】
【数１１４】
【０１５４】
【数１１５】
【０１５５】
Ｂ．シミュレーション結果の分析
攻撃者A は、式（７２）が成立するときとして、前述の（Ａ−Ｅ１）、（Ａ−Ｓ１）に示すような中断があるSimulator Descriptionゲームと、中断のない強偽造不可ゲームとを区別することができない。
【０１５６】
【数１１６】
【０１５７】
その理由は、式（７３）の条件を満たす確率Pｒは、式（７４）が成立するとき、negligibleな値となるからである。ゆえに、以降では、Simulator Descriptionゲ−ムのみを考えていけば良い。
【０１５８】
【数１１７】
【０１５９】
【数１１８】
【０１６０】
Simulator Descriptionゲームの場合、σ＊はvalidなので、式（７５）と仮定する。なお、式（７５）において、上線付きのs＊，r＊は、式（７６）である。
【０１６１】
【数１１９】
【０１６２】
【数１２０】
【０１６３】
（Ｂ−１）
もし、式（７７）が成立するならば、式（７８）である。そのとき、B は、式（７９）に示すあるs＊となる組を式（８０）として生成する。式（８０）に示す組は、仮定［２］チャレンジに対するvalidな出力となる。
【０１６４】
【数１２１】
【０１６５】
【数１２２】
【０１６６】
【数１２３】
【０１６７】
【数１２４】
【０１６８】
（Ｂ−２）
次に、式（７７）が成立しないその他の場合（すなわち、式（８１）の場合）について考える。
【０１６９】
【数１２５】
【０１７０】
（Ｂ−２．１）
式（８２）と仮定し(これは強偽造不可安全の定義による)、また、式（８３）と仮定する。
【０１７１】
【数１２６】
【０１７２】
【数１２７】
【０１７３】
式（８２）、式（８３）を仮定したとき、式（８４）を考えれば十分である。これは、A が、式（８５）のすべてを知っている場合(つまり、式（８６）の場合)を意味している。あるε’≦εに対し、式（８４）≧ε’と仮定する。
【０１７４】
【数１２８】
【０１７５】
【数１２９】
【０１７６】
【数１３０】
【０１７７】
（Ｂ−２．１．１）
s＊ ＝ sｌを満たす数l ∈ U が存在すると仮定する。式（８４）において、もし、A が、式（８７）に示す上線付きのsｉ，rｉ，ｊのすべておよび式（８８）に示すg２αを知ったとき、式（８４）から式（８９）を消去することができる。
【０１７８】
【数１３１】
【０１７９】
【数１３２】
【０１８０】
【数１３３】
【０１８１】
また、式（９０）が成立するので、出力の第３成分を式（９１）に置き換え、残りの成分を消去する。
【０１８２】
【数１３４】
【０１８３】
【数１３５】
【０１８４】
ゆえに、A は、式（９２）を解くためのアドバンテージε′を持つ。ここで、この問題は、式（９３）、式（５０）におけるXｉ(ｉ ∈ U)、式（５９）における式（９４）、式（６９）におけるX＊，Y＊およびA のランダムなビット列から選ばれる。
【０１８５】
【数１３６】
【０１８６】
【数１３７】
【０１８７】
【数１３８】
【０１８８】
ここで、ｉ ∈ Uについて、式（９５）と置く。
【０１８９】
【数１３９】
【０１９０】
また、式（９６）が成立するので、A は式（９７）から式（９８）を計算することができる。
【０１９１】
【数１４０】
【０１９２】
【数１４１】
【０１９３】
【数１４２】
【０１９４】
よって、式（９８）に示す各パラメータを式（９２）から消去する。また、式（９９）は、式（１００）に示す式（９２）の出力とは関連性がないので、式（９９）に示すこれらの入力パラメータも式（９２）から消去することができる。
【０１９５】
【数１４３】
【０１９６】
【数１４４】
【０１９７】
式（９２）において、式(１０１)を式（１０２）へ置き換えることにより、Aは、式（１０３）を解くためのアドバンテージε′を持つ。
【０１９８】
【数１４５】
【０１９９】
【数１４６】
【０２００】
【数１４７】
【０２０１】
ここで、（式（１０４）のときでさえ、)式（１０５）が成立するので、式（１０６）が成立することに注意を要する。
【０２０２】
【数１４８】
【０２０３】
【数１４９】
【０２０４】
【数１５０】
【０２０５】
式（１０７）と仮定する。式（１０８）に示すx′を式（９２）から消去したため，h をZｐ＊の乱数として良い。
【０２０６】
【数１５１】
【０２０７】
【数１５２】
【０２０８】
これは、A が、式（１０９）を解くのにアドバンテージε′を持つことに等しい。ここで、この問題は、式（１１０）およびA のランダムなビット列から選ばれる。
【０２０９】
【数１５３】
【０２１０】
【数１５４】
【０２１１】
F. Baoらによる“Variations of Diffie-Hellman problem”（Proc.ICICS2003, Springer-Verlag, 2003）の記載内容から、これは、式（１１１）を解くのにアドバンテージε′をA が持つことに等しい。
【０２１２】
【数１５５】
【０２１３】
ここで、この問題は式（１１２）およびA のランダムなビット列から選ばれる。これは、A が(G２,G１)上のco-ＤＨ問題をnon-negligibleな確率で解くことができることを意味している。
【０２１４】
【数１５６】
【０２１５】
（Ｂ−２．１．２）
s＊ ＝ sｉを満たす数i ∈ U が存在しないその他の場合(すなわち、式（１１３）の場合)、Aは、x′，x１,x２，…，xｎ１，ｙ′，ｙ１,ｙ２，…，ｙｎ２の値を知っているものと仮定する。
【０２１６】
【数１５７】
【０２１７】
そのとき、式（８４）から式（１１４）を消去することができる。また、式（１１５）に示す組を仮定［２］チャレンジの出力と考えると、式（８４）から式（１１６）を消去することができる。
【０２１８】
【数１５８】
【０２１９】
【数１５９】
【０２２０】
【数１６０】
【０２２１】
これらは、式（８４）の確率Pｒが、仮定［２］の矛盾となるように変形することができることを意味している。
【０２２２】
（Ｂ−２．２）
式（８２）、式（８３）が成立しないその他の場合(すなわち、式（１１７）の場合であり、また、式（１１８）である場合)、X＊ ＝ Xｌである。この場合、Aが、式（１１９）の数値を知っている場合の式（１２０）に示す確率Pｒを考えれば十分である。ε’＋ε”＝εとなるあるε”に対し、式（１２０）≧ε”と仮定する。
【０２２３】
【数１６１】
【０２２４】
【数１６２】
【０２２５】
【数１６３】
【０２２６】
【数１６４】
【０２２７】
（Ｂ−２．２．１）
まず、式（１２１）と仮定する。
【０２２８】
【数１６５】
【０２２９】
（Ｂ−２．２．１．１）
r＊＝rｌ,ｋとなるような式（１２２）に示す数kが存在すると仮定する。式（１２０）において、もし、Aが、式（１２３）に示す上線付きのrｌ、ｊとsｌとのすべてを知っているならば、式（１２０）から式（１２４）を消去することができる。
【０２３０】
【数１６６】
【０２３１】
【数１６７】
【０２３２】
【数１６８】
【０２３３】
また、式（１２５）が成立するので、出力の第２成分を式（１２６）に置き換え、第３成分と第４成分とを消去する。
【０２３４】
【数１６９】
【０２３５】
【数１７０】
【０２３６】
ゆえに、A は、式（１２７）を解くためのアドバンテージε”を持つ。ここで、この問題は、式（１２８）、式（５９）における式（１２９）、式（６９）におけるY＊およびA
のランダムなビット列から選ばれる。
【０２３７】
【数１７１】
【０２３８】
【数１７２】
【０２３９】
【数１７３】
【０２４０】
ここで、式（１３０）に示す数jに対し、式（１３１）と置く。
【０２４１】
【数１７４】
【０２４２】
【数１７５】
【０２４３】
式（１３２）が成立するので，A は、式（１３３）から式（１３４）を計算することができる。
【０２４４】
【数１７６】
【０２４５】
【数１７７】
【０２４６】
【数１７８】
【０２４７】
よって、式（１３４）に示す各パラメータを式（１２７）から消去する。また、式（１２７)において、式（１３５）を式（１３６）へ置き換えると、A は、式（１３７）を解くためのアドバンテージε”を持つ。前述の(Ｂ−２．１．１)にて説明した場合と同様に、これは、A が、(G２，G１)上のco-ＤＨ問題をnon-negligibleな確率で解くことができることを意味している。
【０２４８】
【数１７９】
【０２４９】
【数１８０】
【０２５０】
【数１８１】
【０２５１】
（Ｂ−２．２．１．２）
r＊＝rｌ,ｋとなるような式（１２２）に示す数kが存在しないその他の場合(すなわち、式（１３８）となる場合)、A は、x′，x１，x２，…，xｎ１と同様に、y′，y１，y２，…，yｎ２も知っていると仮定する。そのとき、式（１３９）の等式から、式（１２０）の確率Pｒの変形は、仮定［３］に矛盾する。
【０２５２】
【数１８２】
【０２５３】
【数１８３】
【０２５４】
（Ｂ−２．２．２）
次に、式（１２１）を仮定しないその他の場合(すなわち、式（１４０）が成立する場合)、式（１４１）が示す数を次の式（１４２）が成立するすべての数とする。
【０２５５】
【数１８４】
【０２５６】
【数１８５】
【０２５７】
【数１８６】
【０２５８】
そのとき、式（１４３）から式（１４４）となる。また、式（１４５）を式（１４６）とする。これは式（１４７）を意味している。
【０２５９】
【数１８７】
【０２６０】
【数１８８】
【０２６１】
【数１８９】
【０２６２】
【数１９０】
【０２６３】
【数１９１】
【０２６４】
（Ｂ−２．２．２．１）
式（１４８）が成立するときであり、かつ、r＊ = rｋとなる式（１４９）の数ｋが存在すると仮定する。
【０２６５】
【数１９２】
【０２６６】
【数１９３】
【０２６７】
このとき、前述の(Ｂ−２．２．１．１)の場合のように、Aは、(G２，G１)上のco-ＤＨ問題をnon-negligibleな確率で解くことができる。
【０２６８】
（Ｂ−２．２．２．２）
式（１４８）が成立しない場合あるいはr＊ = rｋとなる式（１４９）の数ｋが存在しないその他の場合(すなわち、式（１５０）が成立する場合あるいは式（１５１）が成立する場合)、式（１５２）に示す組は、仮定［３］チャレンジのvalid出力である。
【０２６９】
【数１９４】
【０２７０】
【数１９５】
【０２７１】
【数１９６】
【０２７２】
シミュレーションにおいて、式（１５３）のいずれも満たさない場合の確率は、次の式（１５４）で与えられる。
【０２７３】
【数１９７】
【０２７４】
【数１９８】
【０２７５】
よって、本発明に係わるＩＤベース署名方式S においては、式（１５５）が成立する。
【０２７６】
【数１９９】
【０２７７】
以上の（Ｂ−１）および（Ｂ−２）から、式（１５６）に示す確率Pｒ（≧ε＝ε´＋ε”）は、少なくとも、式（１５５）の左辺の確率Pｒより高い。事象A１，A２に対し、式（１５７）、式（１５８）であるので、式（１５９）である。
【０２７８】
【数２００】
【０２７９】
【数２０１】
【０２８０】
【数２０２】
【０２８１】
【数２０３】
【０２８２】
これは、(t０，ε０)−co-ＤＨ仮定、(q１，t１，ε１)−仮定［２］または(q２，t２，ε２)−仮定［３］に矛盾する。よって、本発明に係わるＩＤベース署名方式は、(qｅ，qｓ，t，ε)−強偽造不可安全である。
【０２８３】
もし、A が、前述の「Ａ．Simulator Description（シミュレータの構成）」に記載のゲームについて、時間t 内の確率ε で、validな偽造を出力したならば、それは、Bが仮定［２］ゲームについて、または、A がco-ＤＨゲームあるいは仮定［３］ゲームについて、式（１６０）に示す時間以内に、式（１６１）に示す確率で成功することを意味している。
【０２８４】
【数２０４】
【０２８５】
【数２０５】
【０２８６】
よって、式（１６２）に示す仮定が必要である。これは、式（１６３）であることを意味している。以上より、前述した定理１は証明された。
【０２８７】
【数２０６】
【０２８８】
【数２０７】
【０２８９】
本発明に係わるＩＢＳ方式は、前述のように、強偽造不可の安全性を満たすことができた。その理由の一つは、３つの数学的仮定と１つの一方向性同型写像f とを使い、安全性証明を直接的に行うことができるからということができる。
【０２９０】
４．結論
以上に詳細に説明したように、本発明においては、５個の署名パラメータからなる、強偽造不可ＩＢＳ方式のスタンダードモデルを提供している。本発明によるＩＢＳ方式の署名長は、Diffie−Hellman問題あるいは離散対数問題に関連した問題をベースにした他のＩＢＳ方式と比較して短い。なお、本発明に係わるＩＢＳ方式の安全性は、前述したように、Diffie−Hellman問題と一方向性同型写像に関連した３つの問題を解くことの困難性に基づいている。
【０２９１】
以上、本発明の好適実施例の構成を説明した。しかし、斯かる実施例は、本発明の単なる例示に過ぎず、何ら本発明を限定するものではないことに留意されたい。本発明の要旨を逸脱することなく、特定用途に応じて種々の変形変更が可能であることが、当業者には容易に理解できよう。例えば、本発明の実施態様は、課題を解決するための手段における構成（１）に加えて、次のような構成として表現できる。
（２）前記セットアップフェーズにおいて、十分大きな素数の位数p を持つ乗法巡回群G１，G２，GＴ，一方向性同型写像f : G２→ G１ (g１：＝ f(g２))および双線形写像e： G１ ×G２→ GＴ を選び、式（Ａ１０）の乱数αから式（Ａ１１）のMKとして示す前記マスターキーを生成し、式（Ａ１２）を計算する
【数１０】
【数１１】
【数１２】
上記（１）のＩＤベース署名システム。
（３）前記セットアップフェーズにおいて、さらに、式（Ａ１３）に示す乱数の入力に対して式（Ａ１４）に示す出力を生成し、
【数１３】
【数１４】
前記システムパラメータを、次の式（Ａ１５）のparamsとする
【数１５】
上記（２）のＩＤベース署名システム。
（４）前記エクストラクトフェーズにおいて、前記ＩＤをn１ビットのＩＤ情報とし、式（Ａ１６）に示すidkを前記ＩＤのk番目のビットとした場合、式（Ａ１７）に示す乱数sを選び、
【数１６】
【数１７】
式（Ａ１８）に示すＩＤに対応するプライベートキーを次の式（Ａ１９）に示すdＩＤとして計算する
【数１８】
【数１９】
上記（３）のＩＤベース署名システム。
（５）前記サインフェーズにおいて、前記文書のMをn２ビットの署名文書とし、パブリックキーをIDとし、式（Ａ２０）に示すmkを、前記文書Mのk 番目のビットとした場合、(ID,M)の組に関する署名σを、式（Ａ２１）により生成する
【数２０】
【数２１】
上記（４）のＩＤベース署名システム。
（６）前記ベリファイフェーズにおいて、前記システムパラメータparams、前記パブリックキー、前記文書の組(ID,M)および前記署名σを用いて、式（Ａ２２）を検証し、
【数２２】
式（Ａ２２）のすべての等式が成り立つとき、検証結果として正常（valid）を出力し、それ以外のとき、異常（invalid）を出力する上記（５）のＩＤベース署名システム。
（７）セキュリティパラメータを入力としてシステムパラメータおよびマスターキーを返すセットアップ（Ｓｅｔｕｐ）フェーズと、該セットアップフェーズが出力する前記システムパラメータおよび前記マスターキーおよび任意のＩＤを入力としてプライベートキーを返すエクストラクト（Ｅｘｔｒａｃｔ）フェーズと、文書、前記エクストラクトフェーズが出力する前記プライベートキーおよび前記セットアップフェーズが出力する前記システムパラメータを入力として、署名を出力するサイン（Ｓｉｇｎ）フェーズ、および、前記文書、前記ＩＤ、前記サインフェーズが出力する前記署名および前記セットアップフェーズが出力する前記システムパラメータを入力として、正常（ｖａｌｉｄ）または異常（ｉｎｖａｌｉｄ）のいずれかを返すベリファイ（Ｖｅｒｉｆｙ）フェーズとの各フェーズを有するＩＤベース署名方法において、
G１,G２,GＴが素数p の位数を持つ乗法巡回群であり、g２はG２の生成元であり、ｆ：G２→G１が、次の式（Ａ２３）を満たす一方向性同型写像であり、e: G１×G２→GＴが、次の式（Ａ２４）を満たす双線形写像とした場合、
【数２３】
【数２４】
ランダムな生成元g１ ∈R G１， g２ ∈R G２およびランダムなx, y ∈R Zｐ＊に対する入力として、次の式（Ａ２５）に示すg１ｘｙの計算、
【数２５】
ランダムな生成元g１∈R G１，g２∈R G２および乱数x，r１，r２，…，rｑ∈R Zｐ*となる次の式（Ａ２６）に示す入力に対し、式（Ａ２７）に示すあるr＊となる式（Ａ２８）の計算、
【数２６】
【数２７】
【数２８】
および、ランダムな生成元g１∈R G１，g２∈R G２および乱数x，r１，r２，…，rｑ∈R Zｐ*となる次の式（Ａ２９）に示す入力に対し、式（Ａ３０）に示すあるr＊となる式（Ａ３１）の計算、
【数２９】
【数３０】
【数３１】
のそれぞれの計算を、攻撃者が、時間t以内で、高々、あらかじめ定めた定数εの確率でしか行うことができないＩＤベース署名方法。
（８）前記セットアップフェーズにおいて、十分大きな素数の位数p を持つ乗法巡回群G１，G２，GＴ，一方向性同型写像f : G２→ G１ (g１：＝ f(g２))および双線形写像e： G１ ×G２→ GＴ を選び、式（Ａ３２）の乱数αから式（Ａ３３）のMKとして示す前記マスターキーを生成し、式（Ａ３４）を計算する
【数３２】
【数３３】
【数３４】
上記（７）のＩＤベース署名方法。
（９）前記セットアップフェーズにおいて、さらに、式（Ａ３５）に示す乱数の入力に対して式（Ａ３６）に示す出力を生成し、
【数３５】
【数３６】
前記システムパラメータを、次の式（Ａ３７）のparamsとする
【数３７】
上記（８）のＩＤベース署名方法。
（１０）前記エクストラクトフェーズにおいて、前記ＩＤをn１ビットのＩＤ情報とし、式（Ａ３８）に示すidkを前記ＩＤのk番目のビットとした場合、式（Ａ３９）に示す乱数sを選び、
【数３８】
【数３９】
式（Ａ４０）に示すＩＤに対応するプライベートキーを次の式（Ａ４１）に示すdＩＤとして計算する
【数４０】
【数４１】
上記（９）のＩＤベース署名方法。
（１１）前記サインフェーズにおいて、前記文書のMをn２ビットの署名文書とし、パブリックキーをIDとし、式（Ａ４２）に示すmkを、前記文書Mのk 番目のビットとした場合、(ID,M)の組に関する署名σを、式（Ａ４３）により生成する
【数４２】
【数４３】
上記（１０）のＩＤベース署名方法。
（１２）前記ベリファイフェーズにおいて、前記システムパラメータparams、前記パブリックキー、前記文書の組(ID,M)および前記署名σを用いて、式（Ａ４４）を検証し、
【数４４】
式（Ａ４４）のすべての等式が成り立つとき、検証結果として正常（valid）を出力し、それ以外のとき、異常（invalid）を出力する上記（１１）のＩＤベース署名方法。
（１３）前記課題を解決する手段における（１）又は前記（２）乃至（６）の何れかに記載のＩＤベース署名システムをコンピュータシステムとして構築したＩＤベース署名システム。
（１４）前記（７）乃至（１２）の何れかに記載のＩＤベース署名方法を、コンピュータにより実行可能なプログラムとして実施するＩＤベース署名プログラム。
（１５）前記（１４）に記載のＩＤベース署名プログラムをコンピュータにより読取可能な記録媒体に記録しているプログラム記録媒体。
【特許請求の範囲】
【請求項１】
セキュリティパラメータを入力としてシステムパラメータおよびマスターキーを返すセットアップ（Ｓｅｔｕｐ）フェーズと、該セットアップフェーズが出力する前記システムパラメータおよび前記マスターキーおよび任意のＩＤを入力としてプライベートキーを返すエクストラクト（Ｅｘｔｒａｃｔ）フェーズと、文書、前記エクストラクトフェーズが出力する前記プライベートキーおよび前記セットアップフェーズが出力する前記システムパラメータを入力として、署名を出力するサイン（Ｓｉｇｎ）フェーズ、および、前記文書、前記ＩＤ、前記サインフェーズが出力する前記署名および前記セットアップフェーズが出力する前記システムパラメータを入力として、正常（ｖａｌｉｄ）または異常（ｉｎｖａｌｉｄ）のいずれかを返すベリファイ（Ｖｅｒｉｆｙ）フェーズとの各フェーズの演算部を備えたＩＤベース署名システムにおいて、
G１,G２,GＴが素数p の位数を持つ乗法巡回群であり、g２はG２の生成元であり、ｆ：G２→G１が、次の式（Ａ１）を満たす一方向性同型写像であり、e: G１×G２→GＴが、次の式（Ａ２）を満たす双線形写像とした場合、
【数１】
【数２】
ランダムな生成元g１ ∈R G１， g２ ∈R G２およびランダムなx, y ∈R Zｐ＊に対する入力として、次の式（Ａ３）に示すg１ｘｙの計算、
【数３】
ランダムな生成元g１∈R G１，g２∈R G２および乱数x，r１，r２，…，rｑ∈R Zｐ*となる次の式（Ａ４）に示す入力に対し、式（Ａ５）に示すあるr＊となる式（Ａ６）の計算、
【数４】
【数５】
【数６】
および、ランダムな生成元g１∈R G１，g２∈R G２および乱数x，r１，r２，…，rｑ∈R Zｐ*となる次の式（Ａ７）に示す入力に対し、式（Ａ８）に示すあるr＊となる式（Ａ９）の計算、
【数７】
【数８】
【数９】
のそれぞれの計算を、攻撃者が、時間t以内で、高々、あらかじめ定めた定数εの確率でしか行うことができないことを特徴とするＩＤベース署名システム。
【請求項２】
前記セットアップフェーズにおいて、十分大きな素数の位数p を持つ乗法巡回群G１，G２，GＴ，一方向性同型写像f : G２→ G１ (g１：＝ f(g２))および双線形写像e： G１ ×G２→ GＴ を選び、式（Ａ１０）の乱数αから式（Ａ１１）のMKとして示す前記マスターキーを生成し、式（Ａ１２）を計算する
【数１０】
【数１１】
【数１２】
ことを特徴とする請求項１に記載のＩＤベース署名システム。
【請求項３】
前記セットアップフェーズにおいて、さらに、式（Ａ１３）に示す乱数の入力に対して式（Ａ１４）に示す出力を生成し、
【数１３】
【数１４】
前記システムパラメータを、次の式（Ａ１５）のparamsとする
【数１５】
ことを特徴とする請求項２に記載のＩＤベース署名システム。
【請求項４】
前記エクストラクトフェーズにおいて、前記ＩＤをn１ビットのＩＤ情報とし、式（Ａ１６）に示すidkを前記ＩＤのk番目のビットとした場合、式（Ａ１７）に示す乱数sを選び、
【数１６】
【数１７】
式（Ａ１８）に示すＩＤに対応するプライベートキーを次の式（Ａ１９）に示すdＩＤとして計算する
【数１８】
【数１９】
ことを特徴とする請求項３に記載のＩＤベース署名システム。
【請求項５】
前記サインフェーズにおいて、前記文書のMをn２ビットの署名文書とし、パブリックキーをIDとし、式（Ａ２０）に示すmkを、前記文書Mのk 番目のビットとした場合、(ID,M)の組に関する署名σを、式（Ａ２１）により生成する
【数２０】
【数２１】
ことを特徴とする請求項４に記載のＩＤベース署名システム。
【請求項６】
前記ベリファイフェーズにおいて、前記システムパラメータparams、前記パブリックキー、前記文書の組(ID,M)および前記署名σを用いて、式（Ａ２２）を検証し、
【数２２】
式（Ａ２２）のすべての等式が成り立つとき、検証結果として正常（valid）を出力し、それ以外のとき、異常（invalid）を出力することを特徴とする請求項５に記載のＩＤベース署名システム。
【請求項７】
セキュリティパラメータを入力としてシステムパラメータおよびマスターキーを返すセットアップ（Ｓｅｔｕｐ）フェーズと、該セットアップフェーズが出力する前記システムパラメータおよび前記マスターキーおよび任意のＩＤを入力としてプライベートキーを返すエクストラクト（Ｅｘｔｒａｃｔ）フェーズと、文書、前記エクストラクトフェーズが出力する前記プライベートキーおよび前記セットアップフェーズが出力する前記システムパラメータを入力として、署名を出力するサイン（Ｓｉｇｎ）フェーズ、および、前記文書、前記ＩＤ、前記サインフェーズが出力する前記署名および前記セットアップフェーズが出力する前記システムパラメータを入力として、正常（ｖａｌｉｄ）または異常（ｉｎｖａｌｉｄ）のいずれかを返すベリファイ（Ｖｅｒｉｆｙ）フェーズとの各フェーズを有するＩＤベース署名方法において、
G１,G２,GＴが素数p の位数を持つ乗法巡回群であり、g２はG２の生成元であり、ｆ：G２→G１が、次の式（Ａ２３）を満たす一方向性同型写像であり、e: G１×G２→GＴが、次の式（Ａ２４）を満たす双線形写像とした場合、
【数２３】
【数２４】
ランダムな生成元g１ ∈R G１， g２ ∈R G２およびランダムなx, y ∈R Zｐ＊に対する入力として、次の式（Ａ２５）に示すg１ｘｙの計算、
【数２５】
ランダムな生成元g１∈R G１，g２∈R G２および乱数x，r１，r２，…，rｑ∈R Zｐ*となる次の式（Ａ２６）に示す入力に対し、式（Ａ２７）に示すあるr＊となる式（Ａ２８）の計算、
【数２６】
【数２７】
【数２８】
および、ランダムな生成元g１∈R G１，g２∈R G２および乱数x，r１，r２，…，rｑ∈R Zｐ*となる次の式（Ａ２９）に示す入力に対し、式（Ａ３０）に示すあるr＊となる式（Ａ３１）の計算、
【数２９】
【数３０】
【数３１】
のそれぞれの計算を、攻撃者が、時間t以内で、高々、あらかじめ定めた定数εの確率でしか行うことができないことを特徴とするＩＤベース署名方法。
【請求項８】
前記セットアップフェーズにおいて、十分大きな素数の位数p を持つ乗法巡回群G１，G２，GＴ，一方向性同型写像f : G２→ G１ (g１：＝ f(g２))および双線形写像e： G１ ×G２→ GＴ を選び、式（Ａ３２）の乱数αから式（Ａ３３）のMKとして示す前記マスターキーを生成し、式（Ａ３４）を計算する
【数３２】
【数３３】
【数３４】
ことを特徴とする請求項７に記載のＩＤベース署名方法。
【請求項９】
前記セットアップフェーズにおいて、さらに、式（Ａ３５）に示す乱数の入力に対して式（Ａ３６）に示す出力を生成し、
【数３５】
【数３６】
前記システムパラメータを、次の式（Ａ３７）のparamsとする
【数３７】
ことを特徴とする請求項８に記載のＩＤベース署名方法。
【請求項１０】
前記エクストラクトフェーズにおいて、前記ＩＤをn１ビットのＩＤ情報とし、式（Ａ３８）に示すidkを前記ＩＤのk番目のビットとした場合、式（Ａ３９）に示す乱数sを選び、
【数３８】
【数３９】
式（Ａ４０）に示すＩＤに対応するプライベートキーを次の式（Ａ４１）に示すdＩＤとして計算する
【数４０】
【数４１】
ことを特徴とする請求項９に記載のＩＤベース署名方法。
【請求項１１】
前記サインフェーズにおいて、前記文書のMをn２ビットの署名文書とし、パブリックキーをIDとし、式（Ａ４２）に示すmkを、前記文書Mのk 番目のビットとした場合、(ID,M)の組に関する署名σを、式（Ａ４３）により生成する
【数４２】
【数４３】
ことを特徴とする請求項１０に記載のＩＤベース署名方法。
【請求項１２】
前記ベリファイフェーズにおいて、前記システムパラメータparams、前記パブリックキー、前記文書の組(ID,M)および前記署名σを用いて、式（Ａ４４）を検証し、
【数４４】
式（Ａ４４）のすべての等式が成り立つとき、検証結果として正常（valid）を出力し、それ以外のとき、異常（invalid）を出力することを特徴とする請求項１１に記載のＩＤベース署名方法。
【請求項１３】
請求項１乃至６に記載のＩＤベース署名システムをコンピュータシステムとして構築したことを特徴とするＩＤベース署名システム。
【請求項１４】
請求項７乃至１２に記載のＩＤベース署名方法を、コンピュータにより実行可能なプログラムとして実施することを特徴とするＩＤベース署名プログラム。
【請求項１５】
請求項１４に記載のＩＤベース署名プログラムをコンピュータにより読取可能な記録媒体に記録していることを特徴とするプログラム記録媒体。
【請求項１】
セキュリティパラメータを入力としてシステムパラメータおよびマスターキーを返すセットアップ（Ｓｅｔｕｐ）フェーズと、該セットアップフェーズが出力する前記システムパラメータおよび前記マスターキーおよび任意のＩＤを入力としてプライベートキーを返すエクストラクト（Ｅｘｔｒａｃｔ）フェーズと、文書、前記エクストラクトフェーズが出力する前記プライベートキーおよび前記セットアップフェーズが出力する前記システムパラメータを入力として、署名を出力するサイン（Ｓｉｇｎ）フェーズ、および、前記文書、前記ＩＤ、前記サインフェーズが出力する前記署名および前記セットアップフェーズが出力する前記システムパラメータを入力として、正常（ｖａｌｉｄ）または異常（ｉｎｖａｌｉｄ）のいずれかを返すベリファイ（Ｖｅｒｉｆｙ）フェーズとの各フェーズの演算部を備えたＩＤベース署名システムにおいて、
G１,G２,GＴが素数p の位数を持つ乗法巡回群であり、g２はG２の生成元であり、ｆ：G２→G１が、次の式（Ａ１）を満たす一方向性同型写像であり、e: G１×G２→GＴが、次の式（Ａ２）を満たす双線形写像とした場合、
【数１】
【数２】
ランダムな生成元g１ ∈R G１， g２ ∈R G２およびランダムなx, y ∈R Zｐ＊に対する入力として、次の式（Ａ３）に示すg１ｘｙの計算、
【数３】
ランダムな生成元g１∈R G１，g２∈R G２および乱数x，r１，r２，…，rｑ∈R Zｐ*となる次の式（Ａ４）に示す入力に対し、式（Ａ５）に示すあるr＊となる式（Ａ６）の計算、
【数４】
【数５】
【数６】
および、ランダムな生成元g１∈R G１，g２∈R G２および乱数x，r１，r２，…，rｑ∈R Zｐ*となる次の式（Ａ７）に示す入力に対し、式（Ａ８）に示すあるr＊となる式（Ａ９）の計算、
【数７】
【数８】
【数９】
のそれぞれの計算を、攻撃者が、時間t以内で、高々、あらかじめ定めた定数εの確率でしか行うことができないことを特徴とするＩＤベース署名システム。
【請求項２】
前記セットアップフェーズにおいて、十分大きな素数の位数p を持つ乗法巡回群G１，G２，GＴ，一方向性同型写像f : G２→ G１ (g１：＝ f(g２))および双線形写像e： G１ ×G２→ GＴ を選び、式（Ａ１０）の乱数αから式（Ａ１１）のMKとして示す前記マスターキーを生成し、式（Ａ１２）を計算する
【数１０】
【数１１】
【数１２】
ことを特徴とする請求項１に記載のＩＤベース署名システム。
【請求項３】
前記セットアップフェーズにおいて、さらに、式（Ａ１３）に示す乱数の入力に対して式（Ａ１４）に示す出力を生成し、
【数１３】
【数１４】
前記システムパラメータを、次の式（Ａ１５）のparamsとする
【数１５】
ことを特徴とする請求項２に記載のＩＤベース署名システム。
【請求項４】
前記エクストラクトフェーズにおいて、前記ＩＤをn１ビットのＩＤ情報とし、式（Ａ１６）に示すidkを前記ＩＤのk番目のビットとした場合、式（Ａ１７）に示す乱数sを選び、
【数１６】
【数１７】
式（Ａ１８）に示すＩＤに対応するプライベートキーを次の式（Ａ１９）に示すdＩＤとして計算する
【数１８】
【数１９】
ことを特徴とする請求項３に記載のＩＤベース署名システム。
【請求項５】
前記サインフェーズにおいて、前記文書のMをn２ビットの署名文書とし、パブリックキーをIDとし、式（Ａ２０）に示すmkを、前記文書Mのk 番目のビットとした場合、(ID,M)の組に関する署名σを、式（Ａ２１）により生成する
【数２０】
【数２１】
ことを特徴とする請求項４に記載のＩＤベース署名システム。
【請求項６】
前記ベリファイフェーズにおいて、前記システムパラメータparams、前記パブリックキー、前記文書の組(ID,M)および前記署名σを用いて、式（Ａ２２）を検証し、
【数２２】
式（Ａ２２）のすべての等式が成り立つとき、検証結果として正常（valid）を出力し、それ以外のとき、異常（invalid）を出力することを特徴とする請求項５に記載のＩＤベース署名システム。
【請求項７】
セキュリティパラメータを入力としてシステムパラメータおよびマスターキーを返すセットアップ（Ｓｅｔｕｐ）フェーズと、該セットアップフェーズが出力する前記システムパラメータおよび前記マスターキーおよび任意のＩＤを入力としてプライベートキーを返すエクストラクト（Ｅｘｔｒａｃｔ）フェーズと、文書、前記エクストラクトフェーズが出力する前記プライベートキーおよび前記セットアップフェーズが出力する前記システムパラメータを入力として、署名を出力するサイン（Ｓｉｇｎ）フェーズ、および、前記文書、前記ＩＤ、前記サインフェーズが出力する前記署名および前記セットアップフェーズが出力する前記システムパラメータを入力として、正常（ｖａｌｉｄ）または異常（ｉｎｖａｌｉｄ）のいずれかを返すベリファイ（Ｖｅｒｉｆｙ）フェーズとの各フェーズを有するＩＤベース署名方法において、
G１,G２,GＴが素数p の位数を持つ乗法巡回群であり、g２はG２の生成元であり、ｆ：G２→G１が、次の式（Ａ２３）を満たす一方向性同型写像であり、e: G１×G２→GＴが、次の式（Ａ２４）を満たす双線形写像とした場合、
【数２３】
【数２４】
ランダムな生成元g１ ∈R G１， g２ ∈R G２およびランダムなx, y ∈R Zｐ＊に対する入力として、次の式（Ａ２５）に示すg１ｘｙの計算、
【数２５】
ランダムな生成元g１∈R G１，g２∈R G２および乱数x，r１，r２，…，rｑ∈R Zｐ*となる次の式（Ａ２６）に示す入力に対し、式（Ａ２７）に示すあるr＊となる式（Ａ２８）の計算、
【数２６】
【数２７】
【数２８】
および、ランダムな生成元g１∈R G１，g２∈R G２および乱数x，r１，r２，…，rｑ∈R Zｐ*となる次の式（Ａ２９）に示す入力に対し、式（Ａ３０）に示すあるr＊となる式（Ａ３１）の計算、
【数２９】
【数３０】
【数３１】
のそれぞれの計算を、攻撃者が、時間t以内で、高々、あらかじめ定めた定数εの確率でしか行うことができないことを特徴とするＩＤベース署名方法。
【請求項８】
前記セットアップフェーズにおいて、十分大きな素数の位数p を持つ乗法巡回群G１，G２，GＴ，一方向性同型写像f : G２→ G１ (g１：＝ f(g２))および双線形写像e： G１ ×G２→ GＴ を選び、式（Ａ３２）の乱数αから式（Ａ３３）のMKとして示す前記マスターキーを生成し、式（Ａ３４）を計算する
【数３２】
【数３３】
【数３４】
ことを特徴とする請求項７に記載のＩＤベース署名方法。
【請求項９】
前記セットアップフェーズにおいて、さらに、式（Ａ３５）に示す乱数の入力に対して式（Ａ３６）に示す出力を生成し、
【数３５】
【数３６】
前記システムパラメータを、次の式（Ａ３７）のparamsとする
【数３７】
ことを特徴とする請求項８に記載のＩＤベース署名方法。
【請求項１０】
前記エクストラクトフェーズにおいて、前記ＩＤをn１ビットのＩＤ情報とし、式（Ａ３８）に示すidkを前記ＩＤのk番目のビットとした場合、式（Ａ３９）に示す乱数sを選び、
【数３８】
【数３９】
式（Ａ４０）に示すＩＤに対応するプライベートキーを次の式（Ａ４１）に示すdＩＤとして計算する
【数４０】
【数４１】
ことを特徴とする請求項９に記載のＩＤベース署名方法。
【請求項１１】
前記サインフェーズにおいて、前記文書のMをn２ビットの署名文書とし、パブリックキーをIDとし、式（Ａ４２）に示すmkを、前記文書Mのk 番目のビットとした場合、(ID,M)の組に関する署名σを、式（Ａ４３）により生成する
【数４２】
【数４３】
ことを特徴とする請求項１０に記載のＩＤベース署名方法。
【請求項１２】
前記ベリファイフェーズにおいて、前記システムパラメータparams、前記パブリックキー、前記文書の組(ID,M)および前記署名σを用いて、式（Ａ４４）を検証し、
【数４４】
式（Ａ４４）のすべての等式が成り立つとき、検証結果として正常（valid）を出力し、それ以外のとき、異常（invalid）を出力することを特徴とする請求項１１に記載のＩＤベース署名方法。
【請求項１３】
請求項１乃至６に記載のＩＤベース署名システムをコンピュータシステムとして構築したことを特徴とするＩＤベース署名システム。
【請求項１４】
請求項７乃至１２に記載のＩＤベース署名方法を、コンピュータにより実行可能なプログラムとして実施することを特徴とするＩＤベース署名プログラム。
【請求項１５】
請求項１４に記載のＩＤベース署名プログラムをコンピュータにより読取可能な記録媒体に記録していることを特徴とするプログラム記録媒体。
【公開番号】特開２０１０−６０７１６（Ｐ２０１０−６０７１６Ａ）
【公開日】平成２２年３月１８日（２０１０．３．１８）
【国際特許分類】
【出願番号】特願２００８−２２４８５５（Ｐ２００８−２２４８５５）
【出願日】平成２０年９月２日（２００８．９．２）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り Ｃｒｙｐｔｏｌｏｇｙ ｅＰｒｉｎｔ Ａｒｃｈｉｖｅ：Ｒｅｐｏｒｔ ２００８／０９５ Ｖｅｒｓｉｏｎ：２００８０３０３：１２３９４８
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り Ｃｒｙｐｔｏｌｏｇｙ ｅＰｒｉｎｔ Ａｒｃｈｉｖｅ：Ｒｅｐｏｒｔ ２００８／０９５ Ｖｅｒｓｉｏｎ：２００８０３２６：０８００２４
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 強偽造不可なＩＤベース署名のスタンダードモデル 信学技報 ＩＥＩＣＥ Ｔｅｃｈｎｉｃａｌ Ｒｅｐｏｒｔ ＩＳＥＣ２００８‐１５（２００８‐０５）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 強偽造不可なＩＤベース署名のスタンダードモデル ＩＳＥＣ ２００８．０５．１６
【出願人】（３０００２９６１７）ＳＢＩネットシステムズ株式会社 (5)
【出願人】（５０８３４７１００）
【出願人】（３０４０００４５６）
【Ｆターム（参考）】
【公開日】平成２２年３月１８日（２０１０．３．１８）
【国際特許分類】
【出願日】平成２０年９月２日（２００８．９．２）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り Ｃｒｙｐｔｏｌｏｇｙ ｅＰｒｉｎｔ Ａｒｃｈｉｖｅ：Ｒｅｐｏｒｔ ２００８／０９５ Ｖｅｒｓｉｏｎ：２００８０３０３：１２３９４８
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り Ｃｒｙｐｔｏｌｏｇｙ ｅＰｒｉｎｔ Ａｒｃｈｉｖｅ：Ｒｅｐｏｒｔ ２００８／０９５ Ｖｅｒｓｉｏｎ：２００８０３２６：０８００２４
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 強偽造不可なＩＤベース署名のスタンダードモデル 信学技報 ＩＥＩＣＥ Ｔｅｃｈｎｉｃａｌ Ｒｅｐｏｒｔ ＩＳＥＣ２００８‐１５（２００８‐０５）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 強偽造不可なＩＤベース署名のスタンダードモデル ＩＳＥＣ ２００８．０５．１６
【出願人】（３０００２９６１７）ＳＢＩネットシステムズ株式会社 (5)
【出願人】（５０８３４７１００）
【出願人】（３０４０００４５６）
【Ｆターム（参考）】
[ Back to top ]