署名・検証システム、署名・検証方法、署名装置、検証装置、プログラム、記録媒体
【課題】署名長が短く、検証式の計算量がより少なく、高い安全性が証明可能な、群要素メッセージに対するデジタル署名方法であり、さらに、従来のようなメッセージの制約がなく、任意のメッセージに対して署名を生成できる署名方法を提供する。
【解決手段】署名・検証システムは、異なる群からなる双線形写像を利用し、群Ｇ１から群Ｇ２への写像が困難であることを仮定する。そして、異なる生成元の指数部を求めることが難しい性質を利用し、２つの異なる群上でのメッセージを署名のアウトプットとする。
【解決手段】署名・検証システムは、異なる群からなる双線形写像を利用し、群Ｇ１から群Ｇ２への写像が困難であることを仮定する。そして、異なる生成元の指数部を求めることが難しい性質を利用し、２つの異なる群上でのメッセージを署名のアウトプットとする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、主に電気通信を介したメッセージの授受の際に用いる署名・検証システム、署名・検証方法、署名装置、検証装置、プログラム、記録媒体に関する。
【背景技術】
【０００２】
デジタル署名はメッセージｍに対して、公開鍵ｐｋに対応する秘密鍵ｓｋを知る署名者が、メッセージｍに対して秘密鍵ｓｋを正しく使ったときにのみ計算できる値ｓを算出し、これを電子的な署名として用いるものである。正しく計算された署名は誰でも公開鍵ｐｋを用いてその正当性を検証でき、秘密鍵ｓｋを知らないいかなる第三者も正当な署名ｓを算出することはできない。
【０００３】
デジタル署名は、電子現金やクレデンシャルシステムなど様々な暗号プロトコルにおいて基本的な構成要素として利用されている。特に、利用者のプライバシーを必要とする応用においては、ゼロ知識証明と組み合わせることにより署名ｓを明かさないまま、あるメッセージｍに対する正しい署名ｓを保持しているという事実を任意の第三者に納得させるなど、高度な利用形態がしばしば見受けられる。
【０００４】
近年のペアリング技術の進展によって、群の要素がある関係を満たすという事実を効率的に証明するゼロ知識証明が構成可能になった（非特許文献１）。これによって、署名ｓが効率的なペアリングを持つ群Ｇの要素である場合、即ちｓ∈Ｇである場合、前述のように署名ｓを明かさないまま、正しい署名ｓを保持しているという事実を証明することが可能である。例えば、非特許文献２に示されている、いわゆるCL-Signatureと呼ばれる方法では、メッセージｍ∈Ｚｑに対する署名ｓは３つの群要素（ａ，ｂ，ｃ）∈Ｇ３から構成されている。
【０００５】
しかしながら、CL-signatureのように、ランダムオラクル等の（実現不可能と知られている）理想化された構成要素を用いず、数論的な仮定のみによって安全性が証明できる既存の署名方法では、メッセージｍが群Ｇの要素ではない。そのため、メッセージを秘匿した状態で、その秘匿したメッセージに対する正しい署名を保持していることを証明するという応用には供さない。メッセージが群Ｇの要素である場合にも安全な署名方法として、上記のCL-Signatureを改良した方式が非特許文献３に示されており、ランダムメッセージ攻撃に対して安全であることが示されているが、より強い選択メッセージ攻撃に対する安全性は不明である。
【０００６】
メッセージが群要素であって、選択メッセージ攻撃に強いことが証明されている方法として、非特許文献４に示された方法がある。この方法を以下に説明する。図１は署名・検証システムの構成例を示す図であり、図２は署名装置の処理フローを示す図、図３は検証装置の処理フローを示す図である。署名・検証システムは、ネットワーク８００に接続された署名装置７００と検証装置９００で構成される。
【０００７】
ｖ＝（ｑ，Ｇ，ＧＴ，ｅ，ｇ）を公開パラメータとする。ｑは大きな素数、Ｇ，ＧＴは位数ｑの群、ｅはＧ×Ｇ→ＧＴの効率的な計算が可能なペアリング、ｇを群Ｇの任意の生成元、Ｆ，Ｈ，Ｋ，Ｔを群Ｇの生成元とする。また、メッセージは群要素の対（Ｍ，Ｎ）∈Ｇ２であって、ｅ（Ｍ，Ｈ）＝ｅ（ｇ，Ｎ）を満たすものに限られているとする。
【０００８】
署名装置７００は、１以上ｑ−１以下のランダムな整数ｘを生成する（Ｓ７１０）。そして、Ｘ＝ｘｇ、Ｙ＝ｘＨを計算し（Ｓ７２０）、（ｖ，ｘｇ，ｘＨ）を公開鍵ｐｋとし、ｘを秘密鍵ｓｋとする（Ｓ７３０）。
【０００９】
署名装置７００は、１以上ｑ−１以下の乱数ｃ，ｒを生成し（Ｓ７５０）、
【００１０】
【数１】
【００１１】
ａ２＝ｃｇ
ａ３＝ｃＦ
ａ４＝ｒｇ
ａ５＝ｒＨ
を計算する（Ｓ７６０）。そして、５つの組（ａ１，ａ２，ａ３，ａ４，ａ５）∈Ｇ５を署名σとする（Ｓ７７０）。
【００１２】
検証装置９００は、ネットワーク８００を介して署名σを受け取る（Ｓ９１０）。そして、メッセージ対（Ｍ，Ｎ）と署名σに対して、
ｅ（ａ１，Ｘ＋ａ２）＝ｅ（Ｋ＋Ｍ，ｇ）ｅ（Ｔ，ａ４）であること、
ｅ（ａ２，Ｆ）＝ｅ（ｇ，ａ３）であること、
ｅ（ａ４，Ｈ）＝ｅ（ｇ，ａ５）であること、
ｅ（Ｍ，Ｈ）＝ｅ（ｇ，Ｎ）であること、
ｅ（Ｘ，Ｈ）＝ｅ（ｇ，Ｙ）であること
を確認する（Ｓ９２０）。そして、すべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する（Ｓ９３０）。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】Jens Groth and Amit Sahai, “Efficient Non-interactive Proof Systems for Bilinear Groups”, Eurocrypt 2008, LNCS 2965, pp.415-432.
【非特許文献２】Jan Camenisch and Anna Lysyanskaya, “Signature Schemes and Anonymous Credentials from Bilinear Maps”, Crypto 2004, LNCS 3152, pp.56-72.
【非特許文献３】Matthew Green and Susan Hohenberger, “Universally Composable Adaptive Oblivious Transfer”, IACR e-Print archive, 2008/163 ［平成２２年２月５日検索］、インターネット<URL: http://eprint.iacr.org/cgi-bin/getfile.pl?entry=2008/163&version=20080806:150034&file=163.pdf>.
【非特許文献４】Georg Fuchsbauer, “Automorphic Signatures in Bilinear Groups”, IACR e-print 200/320 ［平成２２年２月５日検索］、インターネット<URL: http://eprint.iacr.org/2009/320.pdf>.
【発明の概要】
【発明が解決しようとする課題】
【００１４】
しかしながら、従来技術は署名・検証システムでは、署名が群Ｇの５つの要素からなり、また、検証においては５つのペアリングの等式を確認するため、効率が悪いという課題がある。また、メッセージは群要素の対（Ｍ，Ｎ）∈Ｇ２であって、ｅ（Ｍ，Ｈ）＝ｅ（ｇ，Ｎ）を満たさなければならないという制約がある。
【００１５】
そこで、本発明では、署名長が短く、検証式の計算量がより少なく、高い安全性が証明可能な、群要素メッセージに対するデジタル署名方法であり、さらに、従来のようなメッセージの制約がなく、任意のメッセージに対して署名を生成できる署名方法を提供することを目的とする。
【課題を解決するための手段】
【００１６】
まず、Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｑの群、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元とする。本発明の第１の署名・検証システムは、署名装置と検証装置で構成される。署名装置は、署名記録部、鍵乱数生成部、鍵計算部、鍵生成部、メッセージ取得部、署名乱数生成部、署名計算部、署名出力部を備える。検証装置は、検証入力部、検証確認部、検証出力部を備える。署名記録部は、ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２を記録する。鍵乱数生成部は、１以上ｑ−１以下のランダムな整数α，β，ｘ，ｙを生成する。鍵計算部は、
ｈ＝ｇ１ｙ、
ｇ１’＝ｇｘ、
ｈ＝ｈｘ
Ａ＝ｅ（ｇ１，ｇ２）α、
Ｂ＝ｅ（ｈ，ｇ２）β、
を計算する。鍵生成部は、（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２，Ａ，Ｂ，ｈ，ｇ１’，ｈ’）を公開鍵ｐｋとし、（ｐｋ，α，β，ｘ，ｙ）を秘密鍵ｓｋとする。メッセージ取得部は、群Ｇ２上の１以外の元であるメッセージＭを受け取る。署名乱数生成部は、１以上ｑ−１以下のランダムな整数ζ，ρ，ν生成する。署名計算部は、
ｚ＝ｇ２ζ、
ｒ＝ｇ１ρ、
ｕ＝ｈν、
ｓ＝（ｇ２αＭ−ｘｚ−１）１／ρ、
ｖ＝（ｇ２αＭ−ｘｚ−１）１／ν、
を計算する。署名出力部は、（ｒ，ｓ，ｕ，ｖ，ｚ）を署名σとして出力する。検証入力部は、メッセージＭと署名σとを受信する。検証確認部は、
Ａ＝ｅ（ｇ１’，Ｍ）ｅ（ｇ１，ｚ）ｅ（ｒ，ｓ）であること、
Ｂ＝ｅ（ｈ’，Ｍ）ｅ（ｈ，ｚ）ｅ（ｕ，ｖ）であること、
を確認する。検証出力部は、検証確認部がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する。
【００１７】
なお、ランダムな整数αとβを用いる代わりに、αのみを用いてもよい。
本発明の第２の署名・検証システムも、署名装置と検証装置で構成される。第２の署名・検証システムの署名装置は、署名記録部、鍵乱数生成部、鍵群要素選択部、鍵計算部、鍵生成部、メッセージ取得部、署名群要素選択部、署名計算部、署名出力部を備える。検証装置は、検証入力部、検証確認部、検証出力部を備える。署名記録部は、ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１を記録する。鍵乱数生成部は、１以上ｑ−１以下のランダムな整数ｙ，ｚを生成する。鍵群要素選択部は、群Ｇ２の任意の生成元ｒ０，ｓ０を選択する。鍵計算部は、
ｈ＝ｇ１ｙ、
Ｃ＝ｅ（ｇ１，ｒ０）ｅ（ｈ，ｓ０）、
ｆ＝ｇ１ｚ
を計算する。鍵生成部は、（Ｇ１，Ｇ２，ＧＴ，e，Ｃ，ｇ１，ｈ，ｆ）を公開鍵ｐｋとし、（ｐｋ，ｒ０，ｓ０，ｙ，ｚ）を秘密鍵ｓｋとする。メッセージ取得部は、メッセージｍを受け取る。署名群要素選択部は、群Ｇ２の任意の生成元ｒを選択する。署名計算部は、
ｓ＝（ｒ−１ｍ−ｚ）１／ｙ、
を計算する。署名出力部は、（ｒ，ｓ）を署名σとして出力する。検証入力部は、メッセージｍと署名σとを受信する。検証確認部は、
Ｃ＝ｅ（ｇ１，ｒ）ｅ（ｈ，ｓ）ｅ（ｆ，ｍ）であること
を確認する。検証出力部は、検証確認部が条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する。
【発明の効果】
【００１８】
本発明の署名・検証システムによれば、異なる群からなる双線形写像を利用し、群Ｇ１から群Ｇ２への写像が困難であることが仮定されている。そして、異なる生成元の指数部を求めることが難しい性質を利用し、２つの異なる群上でのメッセージを署名のアウトプットとしている。本発明の署名・検証システムはこのような特徴を有するので、検証のときに確認する式の数を少なくできる。また、メッセージに対する制約条件はなく、任意のメッセージに対して署名生成が可能である。
【図面の簡単な説明】
【００１９】
【図１】従来の署名・検証システムの構成例を示す図。
【図２】従来の署名装置の処理フローを示す図。
【図３】従来の検証装置の処理フローを示す図。
【図４】実施例１、実施例１変形例の署名・検証システムの構成例を示す図。
【図５】実施例１、実施例１変形例の署名装置の処理フローを示す図。
【図６】本発明の検証装置の処理フローを示す図。
【図７】実施例２の署名・検証システムの構成例を示す図。
【図８】実施例２の署名装置の処理フローを示す図。
【発明を実施するための形態】
【００２０】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００２１】
図４は実施例１の署名・検証システムの構成例を示す図、図５は署名装置の処理フローを示す図、図６は検証装置の処理フローを示す図である。実施例１の署名・検証システムは、署名装置１００と検証装置２００を含む。この図では、署名装置１００と検証装置２００とはネットワーク８００によって接続されている。なお、署名装置１００が出力した署名σを検証装置２００に渡す方法は、ネットワークを用いる方法に限定する必要はない。例えば、記録媒体によって署名装置１００から検証装置２００に渡されてもよい。
【００２２】
まず、Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｑの群、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元とする。双線形写像の具体例としては、Weilペアリング、Bilinearペアリング、Tateペアリングなどがある。署名装置１００は、署名記録部１９０、鍵乱数生成部１１０、鍵計算部１２０、鍵生成部１３０、メッセージ取得部１４０、署名乱数生成部１５０、署名計算部１６０、署名出力部１７０を備える。検証装置２００は、検証入力部２１０、検証確認部２２０、検証出力部２３０、検証記録部２９０を備える。
【００２３】
署名記録部１９０が、あらかじめｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２を記録しておく。そして、鍵乱数生成部１１０が、１以上ｑ−１以下のランダムな整数α，ｘ，ｙを生成する（Ｓ１１０）。鍵計算部１２０は、
ｈ＝ｇ１ｙ、
ｇ１’＝ｇｘ、
ｈ＝ｈｘ
Ａ＝ｅ（ｇ１，ｇ２）α、
Ｂ＝ｅ（ｈ，ｇ２）α、
を計算する（Ｓ１２０）。鍵生成部１３０は、（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２，Ａ，Ｂ，ｈ，ｇ１’，ｈ’）を公開鍵ｐｋとし、（ｐｋ，α，ｘ，ｙ）を秘密鍵ｓｋとする（Ｓ１３０）。
【００２４】
メッセージ取得部１４０は、群Ｇ２上の１以外の元であるメッセージＭを受け取る（Ｓ１４０）。なお、メッセージＭを受け取るとは、署名装置１００の外部からメッセージＭが入力されることだけでなく、あらかじめ署名記録部１９０に記録されていたメッセージＭを読み出すことなども含む。署名乱数生成部１５０は、１以上ｑ−１以下のランダムな整数ζ，ρ，ν生成する（Ｓ１５０）。署名計算部１６０は、
ｚ＝ｇ２ζ、
ｒ＝ｇ１ρ、
ｕ＝ｈν、
ｓ＝（ｇ２αＭ−ｘｚ−１）１／ρ、
ｖ＝（ｇ２αＭ−ｘｚ−１）１／ν、
を計算する（Ｓ１６０）。署名出力部１７０は、（ｒ，ｓ，ｕ，ｖ，ｚ）を署名σとして出力する（Ｓ１７０）。
【００２５】
検証入力部２１０は、メッセージＭと署名σとを受信し、検証記録部２９０に保管する（Ｓ２１０）。検証確認部２２０は、
Ａ＝ｅ（ｇ１’，Ｍ）ｅ（ｇ１，ｚ）ｅ（ｒ，ｓ）であること、
Ｂ＝ｅ（ｈ’，Ｍ）ｅ（ｈ，ｚ）ｅ（ｕ，ｖ）であること、
を確認する（Ｓ２２０）。検証出力部２３０は、検証確認部２２０がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する（Ｓ２３０）。例えば、署名が正しいことを示す情報として“１”を出力し、署名が正しくないことを示す情報として“０”を出力すればよい。
【００２６】
本実施例の署名・検証システムによれば、異なる群からなる双線形写像を利用し、群Ｇ１から群Ｇ２への写像が困難であることが仮定されている。そして、異なる生成元の指数部を求めることが難しい性質を利用し、２つの異なる群上でのメッセージを署名のアウトプットとしている。本発明の署名・検証システムはこのような特徴を有するので、検証のときに確認する式の数を少なくできる。また、メッセージに対する制約条件はなく、任意のメッセージに対して署名生成が可能である。
【００２７】
［変形例］
実施例１では、ランダムな整数αを鍵計算部のＡ，Ｂの計算に用いた。本実施例では、鍵計算部のＡの計算ではα、Ｂの計算ではβ（アルファとは別のランダムな整数）を用いる。
【００２８】
図４は実施例１変形例の署名・検証システムの構成例を示す図、図５は署名装置の処理フローを示す図、図６は検証装置の処理フローを示す図である。実施例１変形例の署名・検証システムは、署名装置３００と検証装置２００を含む。この図では、署名装置３００と検証装置２００とはネットワーク８００によって接続されている。なお、署名装置３００が出力した署名σを検証装置２００に渡す方法は、ネットワークを用いる方法に限定する必要はない。例えば、記録媒体によって署名装置３００から検証装置２００に渡されてもよい。
【００２９】
まず、Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｑの群、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元とする。署名装置３００は、署名記録部３９０、鍵乱数生成部３１０、鍵計算部３２０、鍵生成部３３０、メッセージ取得部１４０、署名乱数生成部１５０、署名計算部１６０、署名出力部１７０を備える。検証装置２００は、検証入力部２１０、検証確認部２２０、検証出力部２３０、検証記録部２９０を備える。
【００３０】
まず、あらかじめ署名記録部３９０が、ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２を記録しておく。そして、鍵乱数生成部３１０が、１以上ｑ−１以下のランダムな整数α，β，ｘ，ｙを生成する（Ｓ３１０）。鍵計算部３２０は、
ｈ＝ｇ１ｙ、
ｇ１’＝ｇｘ、
ｈ＝ｈｘ
Ａ＝ｅ（ｇ１，ｇ２）α、
Ｂ＝ｅ（ｈ，ｇ２）β、
を計算する（Ｓ３２０）。鍵生成部３３０は、（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２，Ａ，Ｂ，ｈ，ｇ１’，ｈ’）を公開鍵ｐｋとし、（ｐｋ，α，β，ｘ，ｙ）を秘密鍵ｓｋとする（Ｓ３３０）。メッセージ取得部１４０、署名乱数生成部１５０、署名計算部１６０、署名出力部１７０の処理は実施例１の署名装置１００と同じである。
【００３１】
検証装置２００は実施例１と同じである。つまり、検証入力部２１０は、メッセージＭと署名σとを受信し、検証記録部２９０に保管する（Ｓ２１０）。検証確認部２２０は、
Ａ＝ｅ（ｇ１’，Ｍ）ｅ（ｇ１，ｚ）ｅ（ｒ，ｓ）であること、
Ｂ＝ｅ（ｈ’，Ｍ）ｅ（ｈ，ｚ）ｅ（ｕ，ｖ）であること、
を確認する（Ｓ２２０）。検証出力部２３０は、検証確認部２２０がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する（Ｓ２３０）。
【００３２】
本変形例でも、異なる群からなる双線形写像を利用し、群Ｇ１から群Ｇ２への写像が困難であることが仮定されている。そして、異なる生成元の指数部を求めることが難しい性質を利用し、２つの異なる群上でのメッセージを署名のアウトプットとしている。本発明の署名・検証システムはこのような特徴を有するので、検証のときに確認する式の数を少なくできる。また、メッセージに対する制約条件はなく、任意のメッセージに対して署名生成が可能である。
【実施例２】
【００３３】
図７は実施例２の署名・検証システムの構成例を示す図、図８は署名装置の処理フローを示す図、図６は検証装置の処理フローを示す図である。実施例２の署名・検証システムは、署名装置５００と検証装置６００を含む。この図では、署名装置５００と検証装置６００とはネットワーク８００によって接続されている。なお、署名装置５００が出力した署名σを検証装置６００に渡す方法は、ネットワークを用いる方法に限定する必要はない。例えば、記録媒体によって署名装置５００から検証装置６００に渡されてもよい。
【００３４】
本実施例の署名・検証システムは、署名装置５００と検証装置６００で構成される。署名・検証システムの署名装置５００は、署名記録部５９０、鍵乱数生成部５１０、鍵群要素選択部５１５、鍵計算部５２０、鍵生成部５３０、メッセージ取得部５４０、署名群要素選択部５５５、署名計算部５６０、署名出力部５７０を備える。検証装置６００は、検証入力部６１０、検証確認部６２０、検証出力部２３０、検証記録部６９０を備える。署名記録部５９０が、あらかじめｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１を記録しておく。そして、鍵乱数生成部５１０は、１以上ｑ−１以下のランダムな整数ｙ，ｚを生成する（Ｓ５１０）。鍵群要素選択部５１５は、群Ｇ２の任意の生成元ｒ０，ｓ０を選択する（Ｓ５１５）。鍵計算部５２０は、
ｈ＝ｇ１ｙ、
Ｃ＝ｅ（ｇ１，ｒ０）ｅ（ｈ，ｓ０）、
ｆ＝ｇ１ｚ
を計算する（Ｓ５２０）。鍵生成部５３０は、（Ｇ１，Ｇ２，ＧＴ，e，Ｃ，ｇ１，ｈ，ｆ）を公開鍵ｐｋとし、（ｐｋ，ｒ０，ｓ０，ｙ，ｚ）を秘密鍵ｓｋとする（Ｓ５３０）。
【００３５】
なお、ステップＳ５１０〜Ｓ５３０は、次のような順番としてもよい。まず、鍵乱数生成部５１０は、１以上ｑ−１以下のランダムな整数ｙを生成する（Ｓ５１０’）。鍵群要素選択部５１５は、群Ｇ２の任意の生成元ｒ０，ｓ０を選択する（Ｓ５１５）。鍵計算部５２０は、
ｈ＝ｇ１ｙ、
Ｃ＝ｅ（ｇ１，ｒ０）ｅ（ｈ，ｓ０）、
を計算する（Ｓ５２０’）。鍵生成部５３０は、（Ｇ１，Ｇ２，ＧＴ，e，Ｃ，ｇ１，ｈ）を公開鍵ｐｋ’とし、（ｐｋ’，ｒ０，ｓ０，ｙ，ｚ）を秘密鍵ｓｋ’とする（Ｓ５３０’）。そして、鍵乱数生成部５１０は、１以上ｑ−１以下のランダムな整数ｚを生成する（Ｓ５１０”）。鍵計算部５２０は、
ｆ＝ｇ１ｚ
を計算する（Ｓ５２０”）。鍵生成部５３０は、（ｐｋ”，ｆ）を公開鍵ｐｋとし、（ｓｋ”，ｚ）を秘密鍵ｓｋとする（Ｓ５３０”）。
【００３６】
メッセージ取得部５４０は、メッセージｍを受け取る（Ｓ５４０）。署名群要素選択部５５５は、群Ｇ２の任意の生成元ｒを選択する（Ｓ５５５）。署名計算部５６０は、
ｓ＝（ｒ−１ｍ−ｚ）１／ｙ、
を計算する（Ｓ５６０）。署名出力部５７０は、（ｒ，ｓ）を署名σとして出力する（Ｓ５７０）。
【００３７】
検証入力部６１０は、メッセージｍと署名σとを受信し、検証記録部６９０に保管する（Ｓ６１０）。検証確認部６２０は、
Ｃ＝ｅ（ｇ１，ｒ）ｅ（ｈ，ｓ）ｅ（ｆ，ｍ）であること
を確認する（Ｓ６２０）。検証出力部２３０は、検証確認部６２０が条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する（Ｓ２３０）。例えば、署名が正しいことを示す情報として“１”を出力し、署名が正しくないことを示す情報として“０”を出力すればよい。
【００３８】
実施例２の署名・検証システムも、異なる群からなる双線形写像を利用し、群Ｇ１から群Ｇ２への写像が困難であることが仮定されている。そして、異なる生成元の指数部を求めることが難しい性質を利用し、２つの異なる群上でのメッセージを署名のアウトプットとしている。したがって、検証のときに確認する式の数を少なくできる。また、メッセージに対する制約条件はなく、任意のメッセージに対して署名生成が可能である。
【００３９】
プログラム、記録媒体
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００４０】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００４１】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００４２】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００４３】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００４４】
本発明は、電子データの正当性を証明するために利用することができる。
【符号の説明】
【００４５】
１００、３００、５００、７００ 署名装置
１１０、３１０、５１０ 鍵乱数生成部
１２０、３２０、５２０ 鍵計算部
１３０、３３０、５３０ 鍵生成部
１４０、５４０ メッセージ取得部
１５０ 署名乱数生成部 １６０、５６０ 署名計算部
１７０、５７０ 署名出力部
１９０、３９０、５９０ 署名記録部
２００、６００ 検証装置 ２１０、６１０ 検証入力部
２２０、６２０ 検証確認部 ２３０ 検証出力部
２９０、６９０ 検証記録部 ５１５ 鍵群要素選択部
５５５ 署名群要素選択部 ８００ ネットワーク
【技術分野】
【０００１】
本発明は、主に電気通信を介したメッセージの授受の際に用いる署名・検証システム、署名・検証方法、署名装置、検証装置、プログラム、記録媒体に関する。
【背景技術】
【０００２】
デジタル署名はメッセージｍに対して、公開鍵ｐｋに対応する秘密鍵ｓｋを知る署名者が、メッセージｍに対して秘密鍵ｓｋを正しく使ったときにのみ計算できる値ｓを算出し、これを電子的な署名として用いるものである。正しく計算された署名は誰でも公開鍵ｐｋを用いてその正当性を検証でき、秘密鍵ｓｋを知らないいかなる第三者も正当な署名ｓを算出することはできない。
【０００３】
デジタル署名は、電子現金やクレデンシャルシステムなど様々な暗号プロトコルにおいて基本的な構成要素として利用されている。特に、利用者のプライバシーを必要とする応用においては、ゼロ知識証明と組み合わせることにより署名ｓを明かさないまま、あるメッセージｍに対する正しい署名ｓを保持しているという事実を任意の第三者に納得させるなど、高度な利用形態がしばしば見受けられる。
【０００４】
近年のペアリング技術の進展によって、群の要素がある関係を満たすという事実を効率的に証明するゼロ知識証明が構成可能になった（非特許文献１）。これによって、署名ｓが効率的なペアリングを持つ群Ｇの要素である場合、即ちｓ∈Ｇである場合、前述のように署名ｓを明かさないまま、正しい署名ｓを保持しているという事実を証明することが可能である。例えば、非特許文献２に示されている、いわゆるCL-Signatureと呼ばれる方法では、メッセージｍ∈Ｚｑに対する署名ｓは３つの群要素（ａ，ｂ，ｃ）∈Ｇ３から構成されている。
【０００５】
しかしながら、CL-signatureのように、ランダムオラクル等の（実現不可能と知られている）理想化された構成要素を用いず、数論的な仮定のみによって安全性が証明できる既存の署名方法では、メッセージｍが群Ｇの要素ではない。そのため、メッセージを秘匿した状態で、その秘匿したメッセージに対する正しい署名を保持していることを証明するという応用には供さない。メッセージが群Ｇの要素である場合にも安全な署名方法として、上記のCL-Signatureを改良した方式が非特許文献３に示されており、ランダムメッセージ攻撃に対して安全であることが示されているが、より強い選択メッセージ攻撃に対する安全性は不明である。
【０００６】
メッセージが群要素であって、選択メッセージ攻撃に強いことが証明されている方法として、非特許文献４に示された方法がある。この方法を以下に説明する。図１は署名・検証システムの構成例を示す図であり、図２は署名装置の処理フローを示す図、図３は検証装置の処理フローを示す図である。署名・検証システムは、ネットワーク８００に接続された署名装置７００と検証装置９００で構成される。
【０００７】
ｖ＝（ｑ，Ｇ，ＧＴ，ｅ，ｇ）を公開パラメータとする。ｑは大きな素数、Ｇ，ＧＴは位数ｑの群、ｅはＧ×Ｇ→ＧＴの効率的な計算が可能なペアリング、ｇを群Ｇの任意の生成元、Ｆ，Ｈ，Ｋ，Ｔを群Ｇの生成元とする。また、メッセージは群要素の対（Ｍ，Ｎ）∈Ｇ２であって、ｅ（Ｍ，Ｈ）＝ｅ（ｇ，Ｎ）を満たすものに限られているとする。
【０００８】
署名装置７００は、１以上ｑ−１以下のランダムな整数ｘを生成する（Ｓ７１０）。そして、Ｘ＝ｘｇ、Ｙ＝ｘＨを計算し（Ｓ７２０）、（ｖ，ｘｇ，ｘＨ）を公開鍵ｐｋとし、ｘを秘密鍵ｓｋとする（Ｓ７３０）。
【０００９】
署名装置７００は、１以上ｑ−１以下の乱数ｃ，ｒを生成し（Ｓ７５０）、
【００１０】
【数１】
【００１１】
ａ２＝ｃｇ
ａ３＝ｃＦ
ａ４＝ｒｇ
ａ５＝ｒＨ
を計算する（Ｓ７６０）。そして、５つの組（ａ１，ａ２，ａ３，ａ４，ａ５）∈Ｇ５を署名σとする（Ｓ７７０）。
【００１２】
検証装置９００は、ネットワーク８００を介して署名σを受け取る（Ｓ９１０）。そして、メッセージ対（Ｍ，Ｎ）と署名σに対して、
ｅ（ａ１，Ｘ＋ａ２）＝ｅ（Ｋ＋Ｍ，ｇ）ｅ（Ｔ，ａ４）であること、
ｅ（ａ２，Ｆ）＝ｅ（ｇ，ａ３）であること、
ｅ（ａ４，Ｈ）＝ｅ（ｇ，ａ５）であること、
ｅ（Ｍ，Ｈ）＝ｅ（ｇ，Ｎ）であること、
ｅ（Ｘ，Ｈ）＝ｅ（ｇ，Ｙ）であること
を確認する（Ｓ９２０）。そして、すべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する（Ｓ９３０）。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】Jens Groth and Amit Sahai, “Efficient Non-interactive Proof Systems for Bilinear Groups”, Eurocrypt 2008, LNCS 2965, pp.415-432.
【非特許文献２】Jan Camenisch and Anna Lysyanskaya, “Signature Schemes and Anonymous Credentials from Bilinear Maps”, Crypto 2004, LNCS 3152, pp.56-72.
【非特許文献３】Matthew Green and Susan Hohenberger, “Universally Composable Adaptive Oblivious Transfer”, IACR e-Print archive, 2008/163 ［平成２２年２月５日検索］、インターネット<URL: http://eprint.iacr.org/cgi-bin/getfile.pl?entry=2008/163&version=20080806:150034&file=163.pdf>.
【非特許文献４】Georg Fuchsbauer, “Automorphic Signatures in Bilinear Groups”, IACR e-print 200/320 ［平成２２年２月５日検索］、インターネット<URL: http://eprint.iacr.org/2009/320.pdf>.
【発明の概要】
【発明が解決しようとする課題】
【００１４】
しかしながら、従来技術は署名・検証システムでは、署名が群Ｇの５つの要素からなり、また、検証においては５つのペアリングの等式を確認するため、効率が悪いという課題がある。また、メッセージは群要素の対（Ｍ，Ｎ）∈Ｇ２であって、ｅ（Ｍ，Ｈ）＝ｅ（ｇ，Ｎ）を満たさなければならないという制約がある。
【００１５】
そこで、本発明では、署名長が短く、検証式の計算量がより少なく、高い安全性が証明可能な、群要素メッセージに対するデジタル署名方法であり、さらに、従来のようなメッセージの制約がなく、任意のメッセージに対して署名を生成できる署名方法を提供することを目的とする。
【課題を解決するための手段】
【００１６】
まず、Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｑの群、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元とする。本発明の第１の署名・検証システムは、署名装置と検証装置で構成される。署名装置は、署名記録部、鍵乱数生成部、鍵計算部、鍵生成部、メッセージ取得部、署名乱数生成部、署名計算部、署名出力部を備える。検証装置は、検証入力部、検証確認部、検証出力部を備える。署名記録部は、ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２を記録する。鍵乱数生成部は、１以上ｑ−１以下のランダムな整数α，β，ｘ，ｙを生成する。鍵計算部は、
ｈ＝ｇ１ｙ、
ｇ１’＝ｇｘ、
ｈ＝ｈｘ
Ａ＝ｅ（ｇ１，ｇ２）α、
Ｂ＝ｅ（ｈ，ｇ２）β、
を計算する。鍵生成部は、（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２，Ａ，Ｂ，ｈ，ｇ１’，ｈ’）を公開鍵ｐｋとし、（ｐｋ，α，β，ｘ，ｙ）を秘密鍵ｓｋとする。メッセージ取得部は、群Ｇ２上の１以外の元であるメッセージＭを受け取る。署名乱数生成部は、１以上ｑ−１以下のランダムな整数ζ，ρ，ν生成する。署名計算部は、
ｚ＝ｇ２ζ、
ｒ＝ｇ１ρ、
ｕ＝ｈν、
ｓ＝（ｇ２αＭ−ｘｚ−１）１／ρ、
ｖ＝（ｇ２αＭ−ｘｚ−１）１／ν、
を計算する。署名出力部は、（ｒ，ｓ，ｕ，ｖ，ｚ）を署名σとして出力する。検証入力部は、メッセージＭと署名σとを受信する。検証確認部は、
Ａ＝ｅ（ｇ１’，Ｍ）ｅ（ｇ１，ｚ）ｅ（ｒ，ｓ）であること、
Ｂ＝ｅ（ｈ’，Ｍ）ｅ（ｈ，ｚ）ｅ（ｕ，ｖ）であること、
を確認する。検証出力部は、検証確認部がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する。
【００１７】
なお、ランダムな整数αとβを用いる代わりに、αのみを用いてもよい。
本発明の第２の署名・検証システムも、署名装置と検証装置で構成される。第２の署名・検証システムの署名装置は、署名記録部、鍵乱数生成部、鍵群要素選択部、鍵計算部、鍵生成部、メッセージ取得部、署名群要素選択部、署名計算部、署名出力部を備える。検証装置は、検証入力部、検証確認部、検証出力部を備える。署名記録部は、ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１を記録する。鍵乱数生成部は、１以上ｑ−１以下のランダムな整数ｙ，ｚを生成する。鍵群要素選択部は、群Ｇ２の任意の生成元ｒ０，ｓ０を選択する。鍵計算部は、
ｈ＝ｇ１ｙ、
Ｃ＝ｅ（ｇ１，ｒ０）ｅ（ｈ，ｓ０）、
ｆ＝ｇ１ｚ
を計算する。鍵生成部は、（Ｇ１，Ｇ２，ＧＴ，e，Ｃ，ｇ１，ｈ，ｆ）を公開鍵ｐｋとし、（ｐｋ，ｒ０，ｓ０，ｙ，ｚ）を秘密鍵ｓｋとする。メッセージ取得部は、メッセージｍを受け取る。署名群要素選択部は、群Ｇ２の任意の生成元ｒを選択する。署名計算部は、
ｓ＝（ｒ−１ｍ−ｚ）１／ｙ、
を計算する。署名出力部は、（ｒ，ｓ）を署名σとして出力する。検証入力部は、メッセージｍと署名σとを受信する。検証確認部は、
Ｃ＝ｅ（ｇ１，ｒ）ｅ（ｈ，ｓ）ｅ（ｆ，ｍ）であること
を確認する。検証出力部は、検証確認部が条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する。
【発明の効果】
【００１８】
本発明の署名・検証システムによれば、異なる群からなる双線形写像を利用し、群Ｇ１から群Ｇ２への写像が困難であることが仮定されている。そして、異なる生成元の指数部を求めることが難しい性質を利用し、２つの異なる群上でのメッセージを署名のアウトプットとしている。本発明の署名・検証システムはこのような特徴を有するので、検証のときに確認する式の数を少なくできる。また、メッセージに対する制約条件はなく、任意のメッセージに対して署名生成が可能である。
【図面の簡単な説明】
【００１９】
【図１】従来の署名・検証システムの構成例を示す図。
【図２】従来の署名装置の処理フローを示す図。
【図３】従来の検証装置の処理フローを示す図。
【図４】実施例１、実施例１変形例の署名・検証システムの構成例を示す図。
【図５】実施例１、実施例１変形例の署名装置の処理フローを示す図。
【図６】本発明の検証装置の処理フローを示す図。
【図７】実施例２の署名・検証システムの構成例を示す図。
【図８】実施例２の署名装置の処理フローを示す図。
【発明を実施するための形態】
【００２０】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００２１】
図４は実施例１の署名・検証システムの構成例を示す図、図５は署名装置の処理フローを示す図、図６は検証装置の処理フローを示す図である。実施例１の署名・検証システムは、署名装置１００と検証装置２００を含む。この図では、署名装置１００と検証装置２００とはネットワーク８００によって接続されている。なお、署名装置１００が出力した署名σを検証装置２００に渡す方法は、ネットワークを用いる方法に限定する必要はない。例えば、記録媒体によって署名装置１００から検証装置２００に渡されてもよい。
【００２２】
まず、Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｑの群、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元とする。双線形写像の具体例としては、Weilペアリング、Bilinearペアリング、Tateペアリングなどがある。署名装置１００は、署名記録部１９０、鍵乱数生成部１１０、鍵計算部１２０、鍵生成部１３０、メッセージ取得部１４０、署名乱数生成部１５０、署名計算部１６０、署名出力部１７０を備える。検証装置２００は、検証入力部２１０、検証確認部２２０、検証出力部２３０、検証記録部２９０を備える。
【００２３】
署名記録部１９０が、あらかじめｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２を記録しておく。そして、鍵乱数生成部１１０が、１以上ｑ−１以下のランダムな整数α，ｘ，ｙを生成する（Ｓ１１０）。鍵計算部１２０は、
ｈ＝ｇ１ｙ、
ｇ１’＝ｇｘ、
ｈ＝ｈｘ
Ａ＝ｅ（ｇ１，ｇ２）α、
Ｂ＝ｅ（ｈ，ｇ２）α、
を計算する（Ｓ１２０）。鍵生成部１３０は、（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２，Ａ，Ｂ，ｈ，ｇ１’，ｈ’）を公開鍵ｐｋとし、（ｐｋ，α，ｘ，ｙ）を秘密鍵ｓｋとする（Ｓ１３０）。
【００２４】
メッセージ取得部１４０は、群Ｇ２上の１以外の元であるメッセージＭを受け取る（Ｓ１４０）。なお、メッセージＭを受け取るとは、署名装置１００の外部からメッセージＭが入力されることだけでなく、あらかじめ署名記録部１９０に記録されていたメッセージＭを読み出すことなども含む。署名乱数生成部１５０は、１以上ｑ−１以下のランダムな整数ζ，ρ，ν生成する（Ｓ１５０）。署名計算部１６０は、
ｚ＝ｇ２ζ、
ｒ＝ｇ１ρ、
ｕ＝ｈν、
ｓ＝（ｇ２αＭ−ｘｚ−１）１／ρ、
ｖ＝（ｇ２αＭ−ｘｚ−１）１／ν、
を計算する（Ｓ１６０）。署名出力部１７０は、（ｒ，ｓ，ｕ，ｖ，ｚ）を署名σとして出力する（Ｓ１７０）。
【００２５】
検証入力部２１０は、メッセージＭと署名σとを受信し、検証記録部２９０に保管する（Ｓ２１０）。検証確認部２２０は、
Ａ＝ｅ（ｇ１’，Ｍ）ｅ（ｇ１，ｚ）ｅ（ｒ，ｓ）であること、
Ｂ＝ｅ（ｈ’，Ｍ）ｅ（ｈ，ｚ）ｅ（ｕ，ｖ）であること、
を確認する（Ｓ２２０）。検証出力部２３０は、検証確認部２２０がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する（Ｓ２３０）。例えば、署名が正しいことを示す情報として“１”を出力し、署名が正しくないことを示す情報として“０”を出力すればよい。
【００２６】
本実施例の署名・検証システムによれば、異なる群からなる双線形写像を利用し、群Ｇ１から群Ｇ２への写像が困難であることが仮定されている。そして、異なる生成元の指数部を求めることが難しい性質を利用し、２つの異なる群上でのメッセージを署名のアウトプットとしている。本発明の署名・検証システムはこのような特徴を有するので、検証のときに確認する式の数を少なくできる。また、メッセージに対する制約条件はなく、任意のメッセージに対して署名生成が可能である。
【００２７】
［変形例］
実施例１では、ランダムな整数αを鍵計算部のＡ，Ｂの計算に用いた。本実施例では、鍵計算部のＡの計算ではα、Ｂの計算ではβ（アルファとは別のランダムな整数）を用いる。
【００２８】
図４は実施例１変形例の署名・検証システムの構成例を示す図、図５は署名装置の処理フローを示す図、図６は検証装置の処理フローを示す図である。実施例１変形例の署名・検証システムは、署名装置３００と検証装置２００を含む。この図では、署名装置３００と検証装置２００とはネットワーク８００によって接続されている。なお、署名装置３００が出力した署名σを検証装置２００に渡す方法は、ネットワークを用いる方法に限定する必要はない。例えば、記録媒体によって署名装置３００から検証装置２００に渡されてもよい。
【００２９】
まず、Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｑの群、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元とする。署名装置３００は、署名記録部３９０、鍵乱数生成部３１０、鍵計算部３２０、鍵生成部３３０、メッセージ取得部１４０、署名乱数生成部１５０、署名計算部１６０、署名出力部１７０を備える。検証装置２００は、検証入力部２１０、検証確認部２２０、検証出力部２３０、検証記録部２９０を備える。
【００３０】
まず、あらかじめ署名記録部３９０が、ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２を記録しておく。そして、鍵乱数生成部３１０が、１以上ｑ−１以下のランダムな整数α，β，ｘ，ｙを生成する（Ｓ３１０）。鍵計算部３２０は、
ｈ＝ｇ１ｙ、
ｇ１’＝ｇｘ、
ｈ＝ｈｘ
Ａ＝ｅ（ｇ１，ｇ２）α、
Ｂ＝ｅ（ｈ，ｇ２）β、
を計算する（Ｓ３２０）。鍵生成部３３０は、（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２，Ａ，Ｂ，ｈ，ｇ１’，ｈ’）を公開鍵ｐｋとし、（ｐｋ，α，β，ｘ，ｙ）を秘密鍵ｓｋとする（Ｓ３３０）。メッセージ取得部１４０、署名乱数生成部１５０、署名計算部１６０、署名出力部１７０の処理は実施例１の署名装置１００と同じである。
【００３１】
検証装置２００は実施例１と同じである。つまり、検証入力部２１０は、メッセージＭと署名σとを受信し、検証記録部２９０に保管する（Ｓ２１０）。検証確認部２２０は、
Ａ＝ｅ（ｇ１’，Ｍ）ｅ（ｇ１，ｚ）ｅ（ｒ，ｓ）であること、
Ｂ＝ｅ（ｈ’，Ｍ）ｅ（ｈ，ｚ）ｅ（ｕ，ｖ）であること、
を確認する（Ｓ２２０）。検証出力部２３０は、検証確認部２２０がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する（Ｓ２３０）。
【００３２】
本変形例でも、異なる群からなる双線形写像を利用し、群Ｇ１から群Ｇ２への写像が困難であることが仮定されている。そして、異なる生成元の指数部を求めることが難しい性質を利用し、２つの異なる群上でのメッセージを署名のアウトプットとしている。本発明の署名・検証システムはこのような特徴を有するので、検証のときに確認する式の数を少なくできる。また、メッセージに対する制約条件はなく、任意のメッセージに対して署名生成が可能である。
【実施例２】
【００３３】
図７は実施例２の署名・検証システムの構成例を示す図、図８は署名装置の処理フローを示す図、図６は検証装置の処理フローを示す図である。実施例２の署名・検証システムは、署名装置５００と検証装置６００を含む。この図では、署名装置５００と検証装置６００とはネットワーク８００によって接続されている。なお、署名装置５００が出力した署名σを検証装置６００に渡す方法は、ネットワークを用いる方法に限定する必要はない。例えば、記録媒体によって署名装置５００から検証装置６００に渡されてもよい。
【００３４】
本実施例の署名・検証システムは、署名装置５００と検証装置６００で構成される。署名・検証システムの署名装置５００は、署名記録部５９０、鍵乱数生成部５１０、鍵群要素選択部５１５、鍵計算部５２０、鍵生成部５３０、メッセージ取得部５４０、署名群要素選択部５５５、署名計算部５６０、署名出力部５７０を備える。検証装置６００は、検証入力部６１０、検証確認部６２０、検証出力部２３０、検証記録部６９０を備える。署名記録部５９０が、あらかじめｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１を記録しておく。そして、鍵乱数生成部５１０は、１以上ｑ−１以下のランダムな整数ｙ，ｚを生成する（Ｓ５１０）。鍵群要素選択部５１５は、群Ｇ２の任意の生成元ｒ０，ｓ０を選択する（Ｓ５１５）。鍵計算部５２０は、
ｈ＝ｇ１ｙ、
Ｃ＝ｅ（ｇ１，ｒ０）ｅ（ｈ，ｓ０）、
ｆ＝ｇ１ｚ
を計算する（Ｓ５２０）。鍵生成部５３０は、（Ｇ１，Ｇ２，ＧＴ，e，Ｃ，ｇ１，ｈ，ｆ）を公開鍵ｐｋとし、（ｐｋ，ｒ０，ｓ０，ｙ，ｚ）を秘密鍵ｓｋとする（Ｓ５３０）。
【００３５】
なお、ステップＳ５１０〜Ｓ５３０は、次のような順番としてもよい。まず、鍵乱数生成部５１０は、１以上ｑ−１以下のランダムな整数ｙを生成する（Ｓ５１０’）。鍵群要素選択部５１５は、群Ｇ２の任意の生成元ｒ０，ｓ０を選択する（Ｓ５１５）。鍵計算部５２０は、
ｈ＝ｇ１ｙ、
Ｃ＝ｅ（ｇ１，ｒ０）ｅ（ｈ，ｓ０）、
を計算する（Ｓ５２０’）。鍵生成部５３０は、（Ｇ１，Ｇ２，ＧＴ，e，Ｃ，ｇ１，ｈ）を公開鍵ｐｋ’とし、（ｐｋ’，ｒ０，ｓ０，ｙ，ｚ）を秘密鍵ｓｋ’とする（Ｓ５３０’）。そして、鍵乱数生成部５１０は、１以上ｑ−１以下のランダムな整数ｚを生成する（Ｓ５１０”）。鍵計算部５２０は、
ｆ＝ｇ１ｚ
を計算する（Ｓ５２０”）。鍵生成部５３０は、（ｐｋ”，ｆ）を公開鍵ｐｋとし、（ｓｋ”，ｚ）を秘密鍵ｓｋとする（Ｓ５３０”）。
【００３６】
メッセージ取得部５４０は、メッセージｍを受け取る（Ｓ５４０）。署名群要素選択部５５５は、群Ｇ２の任意の生成元ｒを選択する（Ｓ５５５）。署名計算部５６０は、
ｓ＝（ｒ−１ｍ−ｚ）１／ｙ、
を計算する（Ｓ５６０）。署名出力部５７０は、（ｒ，ｓ）を署名σとして出力する（Ｓ５７０）。
【００３７】
検証入力部６１０は、メッセージｍと署名σとを受信し、検証記録部６９０に保管する（Ｓ６１０）。検証確認部６２０は、
Ｃ＝ｅ（ｇ１，ｒ）ｅ（ｈ，ｓ）ｅ（ｆ，ｍ）であること
を確認する（Ｓ６２０）。検証出力部２３０は、検証確認部６２０が条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する（Ｓ２３０）。例えば、署名が正しいことを示す情報として“１”を出力し、署名が正しくないことを示す情報として“０”を出力すればよい。
【００３８】
実施例２の署名・検証システムも、異なる群からなる双線形写像を利用し、群Ｇ１から群Ｇ２への写像が困難であることが仮定されている。そして、異なる生成元の指数部を求めることが難しい性質を利用し、２つの異なる群上でのメッセージを署名のアウトプットとしている。したがって、検証のときに確認する式の数を少なくできる。また、メッセージに対する制約条件はなく、任意のメッセージに対して署名生成が可能である。
【００３９】
プログラム、記録媒体
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００４０】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００４１】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００４２】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００４３】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００４４】
本発明は、電子データの正当性を証明するために利用することができる。
【符号の説明】
【００４５】
１００、３００、５００、７００ 署名装置
１１０、３１０、５１０ 鍵乱数生成部
１２０、３２０、５２０ 鍵計算部
１３０、３３０、５３０ 鍵生成部
１４０、５４０ メッセージ取得部
１５０ 署名乱数生成部 １６０、５６０ 署名計算部
１７０、５７０ 署名出力部
１９０、３９０、５９０ 署名記録部
２００、６００ 検証装置 ２１０、６１０ 検証入力部
２２０、６２０ 検証確認部 ２３０ 検証出力部
２９０、６９０ 検証記録部 ５１５ 鍵群要素選択部
５５５ 署名群要素選択部 ８００ ネットワーク
【特許請求の範囲】
【請求項１】
Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｑの群、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元とし、
ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２を記録する署名記録部と、
１以上ｑ−１以下のランダムな整数α，ｘ，ｙを生成する鍵乱数生成部と、
ｈ＝ｇ１ｙ、
ｇ１’＝ｇｘ、
ｈ＝ｈｘ
Ａ＝ｅ（ｇ１，ｇ２）α、
Ｂ＝ｅ（ｈ，ｇ２）α、
を計算する鍵計算部と、
（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２，Ａ，Ｂ，ｈ，ｇ１’，ｈ’）を公開鍵ｐｋとし、（ｐｋ，α，ｘ，ｙ）を秘密鍵ｓｋとする鍵生成部と、
群Ｇ２上の１以外の元であるメッセージＭを受け取るメッセージ取得部と、
１以上ｑ−１以下のランダムな整数ζ，ρ，ν生成する署名乱数生成部と、
ｚ＝ｇ２ζ、
ｒ＝ｇ１ρ、
ｕ＝ｈν、
ｓ＝（ｇ２αＭ−ｘｚ−１）１／ρ、
ｖ＝（ｇ２αＭ−ｘｚ−１）１／ν、
を計算する署名計算部と、
（ｒ，ｓ，ｕ，ｖ，ｚ）を署名σとして出力する署名出力部と
を備える署名装置と、
メッセージＭと署名σとを受信する検証入力部と、
Ａ＝ｅ（ｇ１’，Ｍ）ｅ（ｇ１，ｚ）ｅ（ｒ，ｓ）であること、
Ｂ＝ｅ（ｈ’，Ｍ）ｅ（ｈ，ｚ）ｅ（ｕ，ｖ）であること、
を確認する検証確認部と、
前記検証確認部がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する検証出力部と
を備える検証装置と
を有する署名・検証システム。
【請求項２】
Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｑの群、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元とし、
ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２を記録する署名記録部と、
１以上ｑ−１以下のランダムな整数α，β，ｘ，ｙを生成する鍵乱数生成部と、
ｈ＝ｇ１ｙ、
ｇ１’＝ｇｘ、
ｈ＝ｈｘ
Ａ＝ｅ（ｇ１，ｇ２）α、
Ｂ＝ｅ（ｈ，ｇ２）β、
を計算する鍵計算部と、
（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２，Ａ，Ｂ，ｈ，ｇ１’，ｈ’）を公開鍵ｐｋとし、（ｐｋ，α，β，ｘ，ｙ）を秘密鍵ｓｋとする鍵生成部と、
群Ｇ２上の１以外の元であるメッセージＭを受け取るメッセージ取得部と、
１以上ｑ−１以下のランダムな整数ζ，ρ，ν生成する署名乱数生成部と、
ｚ＝ｇ２ζ、
ｒ＝ｇ１ρ、
ｕ＝ｈν、
ｓ＝（ｇ２αＭ−ｘｚ−１）１／ρ、
ｖ＝（ｇ２αＭ−ｘｚ−１）１／ν、
を計算する署名計算部と、
（ｒ，ｓ，ｕ，ｖ，ｚ）を署名σとして出力する署名出力部と
を備える署名装置と、
メッセージＭと署名σとを受信する検証入力部と、
Ａ＝ｅ（ｇ１’，Ｍ）ｅ（ｇ１，ｚ）ｅ（ｒ，ｓ）であること、
Ｂ＝ｅ（ｈ’，Ｍ）ｅ（ｈ，ｚ）ｅ（ｕ，ｖ）であること、
を確認する検証確認部と、
前記検証確認部がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する検証出力部と
を備える検証装置と
を有する署名・検証システム。
【請求項３】
Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｑの群、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１を群Ｇ１の任意の生成元とし、
ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１を記録する署名記録部と、
１以上ｑ−１以下のランダムな整数ｙ，ｚを生成する鍵乱数生成部と、
群Ｇ２の任意の生成元ｒ０，ｓ０を選択する鍵群要素選択部と、
ｈ＝ｇ１ｙ、
Ｃ＝ｅ（ｇ１，ｒ０）ｅ（ｈ，ｓ０）、
ｆ＝ｇ１ｚ
を計算する鍵計算部と、
（Ｇ１，Ｇ２，ＧＴ，e，Ｃ，ｇ１，ｈ，ｆ）を公開鍵ｐｋとし、（ｐｋ，ｒ０，ｓ０，ｙ，ｚ）を秘密鍵ｓｋとする鍵生成部と、
メッセージｍを受け取るメッセージ取得部と、
群Ｇ２の任意の生成元ｒを選択する署名群要素選択部と、
ｓ＝（ｒ−１ｍ−ｚ）１／ｙ、
を計算する署名計算部と、
（ｒ，ｓ）を署名σとして出力する署名出力部と
を備える署名装置と、
メッセージｍと署名σとを受信する検証入力部と、
Ｃ＝ｅ（ｇ１，ｒ）ｅ（ｈ，ｓ）ｅ（ｆ，ｍ）であること
を確認する検証確認部と、
前記検証確認部がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する検証出力部と
を備える検証装置と
を有する署名・検証システム。
【請求項４】
署名装置と検証装置とを含む署名・検証システムでの署名・検証方法であって、
Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｑの群、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元とし、
前記署名装置において、
署名記録部が、あらかじめｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２を記録しておき、
鍵乱数生成部が、１以上ｑ−１以下のランダムな整数α，ｘ，ｙを生成する鍵乱数生成ステップと、
鍵計算部が、
ｈ＝ｇ１ｙ、
ｇ１’＝ｇｘ、
ｈ＝ｈｘ
Ａ＝ｅ（ｇ１，ｇ２）α、
Ｂ＝ｅ（ｈ，ｇ２）α、
を計算する鍵計算ステップと、
鍵生成部が、（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２，Ａ，Ｂ，ｈ，ｇ１’，ｈ’）を公開鍵ｐｋとし、（ｐｋ，α，ｘ，ｙ）を秘密鍵ｓｋとする鍵生成ステップと、
メッセージ取得部が、群Ｇ２上の１以外の元であるメッセージＭを受け取るメッセージ取得ステップと、
署名乱数生成部が、１以上ｑ−１以下のランダムな整数ζ，ρ，ν生成する署名乱数生成ステップと、
署名計算部が、
ｚ＝ｇ２ζ、
ｒ＝ｇ１ρ、
ｕ＝ｈν、
ｓ＝（ｇ２αＭ−ｘｚ−１）１／ρ、
ｖ＝（ｇ２αＭ−ｘｚ−１）１／ν、
を計算する署名計算ステップと、
署名出力部が、（ｒ，ｓ，ｕ，ｖ，ｚ）を署名σとして出力する署名出力ステップと
を有し、
前記検証装置において、
検証入力部が、メッセージＭと署名σとを受信する検証入力ステップと、
検証確認部が、
Ａ＝ｅ（ｇ１’，Ｍ）ｅ（ｇ１，ｚ）ｅ（ｒ，ｓ）であること、
Ｂ＝ｅ（ｈ’，Ｍ）ｅ（ｈ，ｚ）ｅ（ｕ，ｖ）であること、
を確認する検証確認ステップと、
検証出力部が、前記検証確認部がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する検証出力ステップと
を有する署名・検証方法。
【請求項５】
署名装置と検証装置とを含む署名・検証システムでの署名・検証方法であって、
Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｑの群、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元とし、
前記署名装置において、
署名記録部が、あらかじめｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２を記録しておき、
鍵乱数生成部が、１以上ｑ−１以下のランダムな整数α，β，ｘ，ｙを生成する鍵乱数生成ステップと、
鍵計算部が、
ｈ＝ｇ１ｙ、
ｇ１’＝ｇｘ、
ｈ＝ｈｘ
Ａ＝ｅ（ｇ１，ｇ２）α、
Ｂ＝ｅ（ｈ，ｇ２）β、
を計算する鍵計算ステップと、
鍵生成部が、（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２，Ａ，Ｂ，ｈ，ｇ１’，ｈ’）を公開鍵ｐｋとし、（ｐｋ，α，β，ｘ，ｙ）を秘密鍵ｓｋとする鍵生成ステップと、
メッセージ取得部が、群Ｇ２上の１以外の元であるメッセージＭを受け取るメッセージ取得ステップと、
署名乱数生成部が、１以上ｑ−１以下のランダムな整数ζ，ρ，ν生成する署名乱数生成ステップと、
署名計算部が、
ｚ＝ｇ２ζ、
ｒ＝ｇ１ρ、
ｕ＝ｈν、
ｓ＝（ｇ２αＭ−ｘｚ−１）１／ρ、
ｖ＝（ｇ２αＭ−ｘｚ−１）１／ν、
を計算する署名計算ステップと、
署名出力部が、（ｒ，ｓ，ｕ，ｖ，ｚ）を署名σとして出力する署名出力ステップと
を有し、
前記検証装置において、
検証入力部が、メッセージＭと署名σとを受信する検証入力ステップと、
検証確認部が、
Ａ＝ｅ（ｇ１’，Ｍ）ｅ（ｇ１，ｚ）ｅ（ｒ，ｓ）であること、
Ｂ＝ｅ（ｈ’，Ｍ）ｅ（ｈ，ｚ）ｅ（ｕ，ｖ）であること、
を確認する検証確認ステップと、
検証出力部が、前記検証確認部がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する検証出力ステップと
を有す署名・検証方法。
【請求項６】
署名装置と検証装置とを含む署名・検証システムでの署名・検証方法であって、
Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｑの群、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１を群Ｇ１の任意の生成元とし、
前記署名装置において、
署名記録部が、あらかじめｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１を記録しておき、
鍵乱数生成部が、１以上ｑ−１以下のランダムな整数ｙ，ｚを生成する鍵乱数生成ステップと、
鍵群要素選択部が、群Ｇ２の任意の生成元ｒ０，ｓ０を選択する鍵群要素選択ステップと、
鍵計算部が、
ｈ＝ｇ１ｙ、
Ｃ＝ｅ（ｇ１，ｒ０）ｅ（ｈ，ｓ０）、
ｆ＝ｇ１ｚ
を計算する鍵計算ステップと、
鍵生成部が、（Ｇ１，Ｇ２，ＧＴ，e，Ｃ，ｇ１，ｈ，ｆ）を公開鍵ｐｋとし、（ｐｋ，ｒ０，ｓ０，ｙ，ｚ）を秘密鍵ｓｋとする鍵生成ステップと、
メッセージ取得部が、メッセージｍを受け取るメッセージ取得ステップと、
署名群要素選択部が、群Ｇ２の任意の生成元ｒを選択する署名群要素選択ステップと、
署名計算部が、
ｓ＝（ｒ−１ｍ−ｚ）１／ｙ、
を計算する署名計算ステップと、
署名出力部が、（ｒ，ｓ）を署名σとして出力する署名出力ステップと
を有し、
前記検証装置において、
検証入力部が、メッセージｍと署名σとを受信する検証入力ステップと、
検証確認部が、
Ｃ＝ｅ（ｇ１，ｒ）ｅ（ｈ，ｓ）ｅ（ｆ，ｍ）であること
を確認する検証確認ステップと、
検証出力部が、前記検証確認部がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する検証出力ステップと
を有する署名・検証方法。
【請求項７】
Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｑの群、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元とし、
ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２を記録する署名記録部と、
１以上ｑ−１以下のランダムな整数α，ｘ，ｙを生成する鍵乱数生成部と、
ｈ＝ｇ１ｙ、
ｇ１’＝ｇｘ、
ｈ＝ｈｘ
Ａ＝ｅ（ｇ１，ｇ２）α、
Ｂ＝ｅ（ｈ，ｇ２）α、
を計算する鍵計算部と、
（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２，Ａ，Ｂ，ｈ，ｇ１’，ｈ’）を公開鍵ｐｋとし、（ｐｋ，α，ｘ，ｙ）を秘密鍵ｓｋとする鍵生成部と、
群Ｇ２上の１以外の元であるメッセージＭを受け取るメッセージ取得部と、
１以上ｑ−１以下のランダムな整数ζ，ρ，ν生成する署名乱数生成部と、
ｚ＝ｇ２ζ、
ｒ＝ｇ１ρ、
ｕ＝ｈν、
ｓ＝（ｇ２αＭ−ｘｚ−１）１／ρ、
ｖ＝（ｇ２αＭ−ｘｚ−１）１／ν、
を計算する署名計算部と、
（ｒ，ｓ，ｕ，ｖ，ｚ）を署名σとして出力する署名出力部と
を備える署名装置。
【請求項８】
Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｑの群、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元とし、
ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２を記録する署名記録部と、
１以上ｑ−１以下のランダムな整数α，β，ｘ，ｙを生成する鍵乱数生成部と、
ｈ＝ｇ１ｙ、
ｇ１’＝ｇｘ、
ｈ＝ｈｘ
Ａ＝ｅ（ｇ１，ｇ２）α、
Ｂ＝ｅ（ｈ，ｇ２）β、
を計算する鍵計算部と、
（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２，Ａ，Ｂ，ｈ，ｇ１’，ｈ’）を公開鍵ｐｋとし、（ｐｋ，α，β，ｘ，ｙ）を秘密鍵ｓｋとする鍵生成部と、
群Ｇ２上の１以外の元であるメッセージＭを受け取るメッセージ取得部と、
１以上ｑ−１以下のランダムな整数ζ，ρ，ν生成する署名乱数生成部と、
ｚ＝ｇ２ζ、
ｒ＝ｇ１ρ、
ｕ＝ｈν、
ｓ＝（ｇ２αＭ−ｘｚ−１）１／ρ、
ｖ＝（ｇ２αＭ−ｘｚ−１）１／ν、
を計算する署名計算部と、
（ｒ，ｓ，ｕ，ｖ，ｚ）を署名σとして出力する署名出力部と
を備える署名装置。
【請求項９】
Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｑの群、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１を群Ｇ１の任意の生成元とし、
ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１を記録する署名記録部と、
１以上ｑ−１以下のランダムな整数ｙ，ｚを生成する鍵乱数生成部と、
群Ｇ２の任意の生成元ｒ０，ｓ０を選択する鍵群要素選択部と、
ｈ＝ｇ１ｙ、
Ｃ＝ｅ（ｇ１，ｒ０）ｅ（ｈ，ｓ０）、
ｆ＝ｇ１ｚ
を計算する鍵計算部と、
（Ｇ１，Ｇ２，ＧＴ，e，Ｃ，ｇ１，ｈ，ｆ）を公開鍵ｐｋとし、（ｐｋ，ｒ０，ｓ０，ｙ，ｚ）を秘密鍵ｓｋとする鍵生成部と、
メッセージｍを受け取るメッセージ取得部と、
群Ｇ２の任意の生成元ｒを選択する署名群要素選択部と、
ｓ＝（ｒ−１ｍ−ｚ）１／ｙ、
を計算する署名計算部と、
（ｒ，ｓ）を署名σとして出力する署名出力部と
を備える署名装置。
【請求項１０】
Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｑの群、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元、（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２，Ａ，Ｂ，ｈ，ｇ１’，ｈ’）を公開鍵ｐｋとし、
メッセージＭと署名σ＝（ｒ，ｓ，ｕ，ｖ，ｚ）とを受信する検証入力部と、
Ａ＝ｅ（ｇ１’，Ｍ）ｅ（ｇ１，ｚ）ｅ（ｒ，ｓ）であること、
Ｂ＝ｅ（ｈ’，Ｍ）ｅ（ｈ，ｚ）ｅ（ｕ，ｖ）であること、
を確認する検証確認部と、
前記検証確認部がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する検証出力部と
を備える検証装置。
【請求項１１】
Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｑの群、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１を群Ｇ１の任意の生成元、（Ｇ１，Ｇ２，ＧＴ，e，Ｃ，ｇ１，ｈ，ｆ）を公開鍵ｐｋとし、
メッセージｍと署名σ＝（ｒ，ｓ）とを受信する検証入力部と、
Ｃ＝ｅ（ｇ１，ｒ）ｅ（ｈ，ｓ）ｅ（ｆ，ｍ）であること
を確認する検証確認部と、
前記検証確認部がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する検証出力部と
を備える検証装置。
【請求項１２】
請求項７から９のいずれかに記載の署名装置、もしくは請求項１０または１１記載の検証装置のいずれかの装置として、コンピュータを機能させるプログラム。
【請求項１３】
請求項１２記載のプログラムを記録した記録媒体。
【請求項１】
Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｑの群、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元とし、
ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２を記録する署名記録部と、
１以上ｑ−１以下のランダムな整数α，ｘ，ｙを生成する鍵乱数生成部と、
ｈ＝ｇ１ｙ、
ｇ１’＝ｇｘ、
ｈ＝ｈｘ
Ａ＝ｅ（ｇ１，ｇ２）α、
Ｂ＝ｅ（ｈ，ｇ２）α、
を計算する鍵計算部と、
（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２，Ａ，Ｂ，ｈ，ｇ１’，ｈ’）を公開鍵ｐｋとし、（ｐｋ，α，ｘ，ｙ）を秘密鍵ｓｋとする鍵生成部と、
群Ｇ２上の１以外の元であるメッセージＭを受け取るメッセージ取得部と、
１以上ｑ−１以下のランダムな整数ζ，ρ，ν生成する署名乱数生成部と、
ｚ＝ｇ２ζ、
ｒ＝ｇ１ρ、
ｕ＝ｈν、
ｓ＝（ｇ２αＭ−ｘｚ−１）１／ρ、
ｖ＝（ｇ２αＭ−ｘｚ−１）１／ν、
を計算する署名計算部と、
（ｒ，ｓ，ｕ，ｖ，ｚ）を署名σとして出力する署名出力部と
を備える署名装置と、
メッセージＭと署名σとを受信する検証入力部と、
Ａ＝ｅ（ｇ１’，Ｍ）ｅ（ｇ１，ｚ）ｅ（ｒ，ｓ）であること、
Ｂ＝ｅ（ｈ’，Ｍ）ｅ（ｈ，ｚ）ｅ（ｕ，ｖ）であること、
を確認する検証確認部と、
前記検証確認部がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する検証出力部と
を備える検証装置と
を有する署名・検証システム。
【請求項２】
Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｑの群、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元とし、
ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２を記録する署名記録部と、
１以上ｑ−１以下のランダムな整数α，β，ｘ，ｙを生成する鍵乱数生成部と、
ｈ＝ｇ１ｙ、
ｇ１’＝ｇｘ、
ｈ＝ｈｘ
Ａ＝ｅ（ｇ１，ｇ２）α、
Ｂ＝ｅ（ｈ，ｇ２）β、
を計算する鍵計算部と、
（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２，Ａ，Ｂ，ｈ，ｇ１’，ｈ’）を公開鍵ｐｋとし、（ｐｋ，α，β，ｘ，ｙ）を秘密鍵ｓｋとする鍵生成部と、
群Ｇ２上の１以外の元であるメッセージＭを受け取るメッセージ取得部と、
１以上ｑ−１以下のランダムな整数ζ，ρ，ν生成する署名乱数生成部と、
ｚ＝ｇ２ζ、
ｒ＝ｇ１ρ、
ｕ＝ｈν、
ｓ＝（ｇ２αＭ−ｘｚ−１）１／ρ、
ｖ＝（ｇ２αＭ−ｘｚ−１）１／ν、
を計算する署名計算部と、
（ｒ，ｓ，ｕ，ｖ，ｚ）を署名σとして出力する署名出力部と
を備える署名装置と、
メッセージＭと署名σとを受信する検証入力部と、
Ａ＝ｅ（ｇ１’，Ｍ）ｅ（ｇ１，ｚ）ｅ（ｒ，ｓ）であること、
Ｂ＝ｅ（ｈ’，Ｍ）ｅ（ｈ，ｚ）ｅ（ｕ，ｖ）であること、
を確認する検証確認部と、
前記検証確認部がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する検証出力部と
を備える検証装置と
を有する署名・検証システム。
【請求項３】
Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｑの群、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１を群Ｇ１の任意の生成元とし、
ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１を記録する署名記録部と、
１以上ｑ−１以下のランダムな整数ｙ，ｚを生成する鍵乱数生成部と、
群Ｇ２の任意の生成元ｒ０，ｓ０を選択する鍵群要素選択部と、
ｈ＝ｇ１ｙ、
Ｃ＝ｅ（ｇ１，ｒ０）ｅ（ｈ，ｓ０）、
ｆ＝ｇ１ｚ
を計算する鍵計算部と、
（Ｇ１，Ｇ２，ＧＴ，e，Ｃ，ｇ１，ｈ，ｆ）を公開鍵ｐｋとし、（ｐｋ，ｒ０，ｓ０，ｙ，ｚ）を秘密鍵ｓｋとする鍵生成部と、
メッセージｍを受け取るメッセージ取得部と、
群Ｇ２の任意の生成元ｒを選択する署名群要素選択部と、
ｓ＝（ｒ−１ｍ−ｚ）１／ｙ、
を計算する署名計算部と、
（ｒ，ｓ）を署名σとして出力する署名出力部と
を備える署名装置と、
メッセージｍと署名σとを受信する検証入力部と、
Ｃ＝ｅ（ｇ１，ｒ）ｅ（ｈ，ｓ）ｅ（ｆ，ｍ）であること
を確認する検証確認部と、
前記検証確認部がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する検証出力部と
を備える検証装置と
を有する署名・検証システム。
【請求項４】
署名装置と検証装置とを含む署名・検証システムでの署名・検証方法であって、
Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｑの群、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元とし、
前記署名装置において、
署名記録部が、あらかじめｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２を記録しておき、
鍵乱数生成部が、１以上ｑ−１以下のランダムな整数α，ｘ，ｙを生成する鍵乱数生成ステップと、
鍵計算部が、
ｈ＝ｇ１ｙ、
ｇ１’＝ｇｘ、
ｈ＝ｈｘ
Ａ＝ｅ（ｇ１，ｇ２）α、
Ｂ＝ｅ（ｈ，ｇ２）α、
を計算する鍵計算ステップと、
鍵生成部が、（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２，Ａ，Ｂ，ｈ，ｇ１’，ｈ’）を公開鍵ｐｋとし、（ｐｋ，α，ｘ，ｙ）を秘密鍵ｓｋとする鍵生成ステップと、
メッセージ取得部が、群Ｇ２上の１以外の元であるメッセージＭを受け取るメッセージ取得ステップと、
署名乱数生成部が、１以上ｑ−１以下のランダムな整数ζ，ρ，ν生成する署名乱数生成ステップと、
署名計算部が、
ｚ＝ｇ２ζ、
ｒ＝ｇ１ρ、
ｕ＝ｈν、
ｓ＝（ｇ２αＭ−ｘｚ−１）１／ρ、
ｖ＝（ｇ２αＭ−ｘｚ−１）１／ν、
を計算する署名計算ステップと、
署名出力部が、（ｒ，ｓ，ｕ，ｖ，ｚ）を署名σとして出力する署名出力ステップと
を有し、
前記検証装置において、
検証入力部が、メッセージＭと署名σとを受信する検証入力ステップと、
検証確認部が、
Ａ＝ｅ（ｇ１’，Ｍ）ｅ（ｇ１，ｚ）ｅ（ｒ，ｓ）であること、
Ｂ＝ｅ（ｈ’，Ｍ）ｅ（ｈ，ｚ）ｅ（ｕ，ｖ）であること、
を確認する検証確認ステップと、
検証出力部が、前記検証確認部がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する検証出力ステップと
を有する署名・検証方法。
【請求項５】
署名装置と検証装置とを含む署名・検証システムでの署名・検証方法であって、
Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｑの群、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元とし、
前記署名装置において、
署名記録部が、あらかじめｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２を記録しておき、
鍵乱数生成部が、１以上ｑ−１以下のランダムな整数α，β，ｘ，ｙを生成する鍵乱数生成ステップと、
鍵計算部が、
ｈ＝ｇ１ｙ、
ｇ１’＝ｇｘ、
ｈ＝ｈｘ
Ａ＝ｅ（ｇ１，ｇ２）α、
Ｂ＝ｅ（ｈ，ｇ２）β、
を計算する鍵計算ステップと、
鍵生成部が、（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２，Ａ，Ｂ，ｈ，ｇ１’，ｈ’）を公開鍵ｐｋとし、（ｐｋ，α，β，ｘ，ｙ）を秘密鍵ｓｋとする鍵生成ステップと、
メッセージ取得部が、群Ｇ２上の１以外の元であるメッセージＭを受け取るメッセージ取得ステップと、
署名乱数生成部が、１以上ｑ−１以下のランダムな整数ζ，ρ，ν生成する署名乱数生成ステップと、
署名計算部が、
ｚ＝ｇ２ζ、
ｒ＝ｇ１ρ、
ｕ＝ｈν、
ｓ＝（ｇ２αＭ−ｘｚ−１）１／ρ、
ｖ＝（ｇ２αＭ−ｘｚ−１）１／ν、
を計算する署名計算ステップと、
署名出力部が、（ｒ，ｓ，ｕ，ｖ，ｚ）を署名σとして出力する署名出力ステップと
を有し、
前記検証装置において、
検証入力部が、メッセージＭと署名σとを受信する検証入力ステップと、
検証確認部が、
Ａ＝ｅ（ｇ１’，Ｍ）ｅ（ｇ１，ｚ）ｅ（ｒ，ｓ）であること、
Ｂ＝ｅ（ｈ’，Ｍ）ｅ（ｈ，ｚ）ｅ（ｕ，ｖ）であること、
を確認する検証確認ステップと、
検証出力部が、前記検証確認部がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する検証出力ステップと
を有す署名・検証方法。
【請求項６】
署名装置と検証装置とを含む署名・検証システムでの署名・検証方法であって、
Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｑの群、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１を群Ｇ１の任意の生成元とし、
前記署名装置において、
署名記録部が、あらかじめｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１を記録しておき、
鍵乱数生成部が、１以上ｑ−１以下のランダムな整数ｙ，ｚを生成する鍵乱数生成ステップと、
鍵群要素選択部が、群Ｇ２の任意の生成元ｒ０，ｓ０を選択する鍵群要素選択ステップと、
鍵計算部が、
ｈ＝ｇ１ｙ、
Ｃ＝ｅ（ｇ１，ｒ０）ｅ（ｈ，ｓ０）、
ｆ＝ｇ１ｚ
を計算する鍵計算ステップと、
鍵生成部が、（Ｇ１，Ｇ２，ＧＴ，e，Ｃ，ｇ１，ｈ，ｆ）を公開鍵ｐｋとし、（ｐｋ，ｒ０，ｓ０，ｙ，ｚ）を秘密鍵ｓｋとする鍵生成ステップと、
メッセージ取得部が、メッセージｍを受け取るメッセージ取得ステップと、
署名群要素選択部が、群Ｇ２の任意の生成元ｒを選択する署名群要素選択ステップと、
署名計算部が、
ｓ＝（ｒ−１ｍ−ｚ）１／ｙ、
を計算する署名計算ステップと、
署名出力部が、（ｒ，ｓ）を署名σとして出力する署名出力ステップと
を有し、
前記検証装置において、
検証入力部が、メッセージｍと署名σとを受信する検証入力ステップと、
検証確認部が、
Ｃ＝ｅ（ｇ１，ｒ）ｅ（ｈ，ｓ）ｅ（ｆ，ｍ）であること
を確認する検証確認ステップと、
検証出力部が、前記検証確認部がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する検証出力ステップと
を有する署名・検証方法。
【請求項７】
Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｑの群、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元とし、
ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２を記録する署名記録部と、
１以上ｑ−１以下のランダムな整数α，ｘ，ｙを生成する鍵乱数生成部と、
ｈ＝ｇ１ｙ、
ｇ１’＝ｇｘ、
ｈ＝ｈｘ
Ａ＝ｅ（ｇ１，ｇ２）α、
Ｂ＝ｅ（ｈ，ｇ２）α、
を計算する鍵計算部と、
（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２，Ａ，Ｂ，ｈ，ｇ１’，ｈ’）を公開鍵ｐｋとし、（ｐｋ，α，ｘ，ｙ）を秘密鍵ｓｋとする鍵生成部と、
群Ｇ２上の１以外の元であるメッセージＭを受け取るメッセージ取得部と、
１以上ｑ−１以下のランダムな整数ζ，ρ，ν生成する署名乱数生成部と、
ｚ＝ｇ２ζ、
ｒ＝ｇ１ρ、
ｕ＝ｈν、
ｓ＝（ｇ２αＭ−ｘｚ−１）１／ρ、
ｖ＝（ｇ２αＭ−ｘｚ−１）１／ν、
を計算する署名計算部と、
（ｒ，ｓ，ｕ，ｖ，ｚ）を署名σとして出力する署名出力部と
を備える署名装置。
【請求項８】
Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｑの群、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元とし、
ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２を記録する署名記録部と、
１以上ｑ−１以下のランダムな整数α，β，ｘ，ｙを生成する鍵乱数生成部と、
ｈ＝ｇ１ｙ、
ｇ１’＝ｇｘ、
ｈ＝ｈｘ
Ａ＝ｅ（ｇ１，ｇ２）α、
Ｂ＝ｅ（ｈ，ｇ２）β、
を計算する鍵計算部と、
（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２，Ａ，Ｂ，ｈ，ｇ１’，ｈ’）を公開鍵ｐｋとし、（ｐｋ，α，β，ｘ，ｙ）を秘密鍵ｓｋとする鍵生成部と、
群Ｇ２上の１以外の元であるメッセージＭを受け取るメッセージ取得部と、
１以上ｑ−１以下のランダムな整数ζ，ρ，ν生成する署名乱数生成部と、
ｚ＝ｇ２ζ、
ｒ＝ｇ１ρ、
ｕ＝ｈν、
ｓ＝（ｇ２αＭ−ｘｚ−１）１／ρ、
ｖ＝（ｇ２αＭ−ｘｚ−１）１／ν、
を計算する署名計算部と、
（ｒ，ｓ，ｕ，ｖ，ｚ）を署名σとして出力する署名出力部と
を備える署名装置。
【請求項９】
Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｑの群、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１を群Ｇ１の任意の生成元とし、
ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１を記録する署名記録部と、
１以上ｑ−１以下のランダムな整数ｙ，ｚを生成する鍵乱数生成部と、
群Ｇ２の任意の生成元ｒ０，ｓ０を選択する鍵群要素選択部と、
ｈ＝ｇ１ｙ、
Ｃ＝ｅ（ｇ１，ｒ０）ｅ（ｈ，ｓ０）、
ｆ＝ｇ１ｚ
を計算する鍵計算部と、
（Ｇ１，Ｇ２，ＧＴ，e，Ｃ，ｇ１，ｈ，ｆ）を公開鍵ｐｋとし、（ｐｋ，ｒ０，ｓ０，ｙ，ｚ）を秘密鍵ｓｋとする鍵生成部と、
メッセージｍを受け取るメッセージ取得部と、
群Ｇ２の任意の生成元ｒを選択する署名群要素選択部と、
ｓ＝（ｒ−１ｍ−ｚ）１／ｙ、
を計算する署名計算部と、
（ｒ，ｓ）を署名σとして出力する署名出力部と
を備える署名装置。
【請求項１０】
Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｑの群、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１を群Ｇ１の任意の生成元、ｇ２を群Ｇ２の任意の生成元、（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ１，ｇ２，Ａ，Ｂ，ｈ，ｇ１’，ｈ’）を公開鍵ｐｋとし、
メッセージＭと署名σ＝（ｒ，ｓ，ｕ，ｖ，ｚ）とを受信する検証入力部と、
Ａ＝ｅ（ｇ１’，Ｍ）ｅ（ｇ１，ｚ）ｅ（ｒ，ｓ）であること、
Ｂ＝ｅ（ｈ’，Ｍ）ｅ（ｈ，ｚ）ｅ（ｕ，ｖ）であること、
を確認する検証確認部と、
前記検証確認部がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する検証出力部と
を備える検証装置。
【請求項１１】
Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｑの群、ＧＴを位数ｑの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、ｇ１を群Ｇ１の任意の生成元、（Ｇ１，Ｇ２，ＧＴ，e，Ｃ，ｇ１，ｈ，ｆ）を公開鍵ｐｋとし、
メッセージｍと署名σ＝（ｒ，ｓ）とを受信する検証入力部と、
Ｃ＝ｅ（ｇ１，ｒ）ｅ（ｈ，ｓ）ｅ（ｆ，ｍ）であること
を確認する検証確認部と、
前記検証確認部がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する検証出力部と
を備える検証装置。
【請求項１２】
請求項７から９のいずれかに記載の署名装置、もしくは請求項１０または１１記載の検証装置のいずれかの装置として、コンピュータを機能させるプログラム。
【請求項１３】
請求項１２記載のプログラムを記録した記録媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１１−１７０２４６（Ｐ２０１１−１７０２４６Ａ）
【公開日】平成２３年９月１日（２０１１．９．１）
【国際特許分類】
【出願番号】特願２０１０−３５９２８（Ｐ２０１０−３５９２８）
【出願日】平成２２年２月２２日（２０１０．２．２２）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２３年９月１日（２０１１．９．１）
【国際特許分類】
【出願日】平成２２年２月２２日（２０１０．２．２２）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]