署名・検証システム、署名・検証方法、署名装置、検証装置、プログラム、記録媒体
【課題】署名長が短く、署名生成と署名検証の計算量がより少な署名方法を提供する。
【解決手段】本発明の署名・検証システムは、異なる群（Ｇ１，Ｇ２）からなる双線形写像を利用し、群Ｇ１から群Ｇ２への写像が困難であることを仮定し、異なる生成元の指数部を求めることが難しい性質を利用し、２つの異なる群上でのメッセージを署名のアウトプットとする。本発明の署名装置は、少なくとも署名記録部、コミットメント群要素選択部、コミットメント乱数生成部、コミットメント計算部、鍵乱数生成部、鍵計算部、鍵群要素選択部、鍵ランダマイズ部、鍵生成部、メッセージ取得部、署名乱数生成部、署名計算部、署名出力部を備える。検証装置は、検証入力部、検証確認部、検証出力部を備える。
【解決手段】本発明の署名・検証システムは、異なる群（Ｇ１，Ｇ２）からなる双線形写像を利用し、群Ｇ１から群Ｇ２への写像が困難であることを仮定し、異なる生成元の指数部を求めることが難しい性質を利用し、２つの異なる群上でのメッセージを署名のアウトプットとする。本発明の署名装置は、少なくとも署名記録部、コミットメント群要素選択部、コミットメント乱数生成部、コミットメント計算部、鍵乱数生成部、鍵計算部、鍵群要素選択部、鍵ランダマイズ部、鍵生成部、メッセージ取得部、署名乱数生成部、署名計算部、署名出力部を備える。検証装置は、検証入力部、検証確認部、検証出力部を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、主に電気通信を介したメッセージの授受の際に用いる署名・検証システム、署名・検証方法、署名装置、検証装置、プログラム、記録媒体に関する。
【背景技術】
【０００２】
デジタル署名はメッセージｍに対して、公開鍵ｐｋに対応する秘密鍵ｓｋを知る署名者が、メッセージｍに対して秘密鍵ｓｋを正しく使ったときにのみ計算できる値ｓを算出し、これを電子的な署名として用いるものである。正しく計算された署名は誰でも公開鍵ｐｋを用いてその正当性を検証でき、秘密鍵ｓｋを知らないいかなる第三者も正当な署名ｓを算出することはできない。
【０００３】
デジタル署名は、電子現金やクレデンシャルシステムなど様々な暗号プロトコルにおいて基本的な構成要素として利用されている。特に、利用者のプライバシーを必要とする応用においては、ゼロ知識証明と組み合わせることにより署名ｓを明かさないまま、あるメッセージｍに対する正しい署名ｓを保持しているという事実を任意の第三者に納得させるなど、高度な利用形態がしばしば見受けられる。
【０００４】
近年のペアリング技術の進展によって、群の要素がある関係を満たすという事実を効率的に証明するゼロ知識証明が構成可能になった（非特許文献１）。これによって、署名ｓが効率的なペアリングを持つ群Ｇの要素である場合、即ちｓ∈Ｇである場合、前述のように署名ｓを明かさないまま、正しい署名ｓを保持しているという事実を証明することが可能である。例えば、非特許文献２に示されている、いわゆるCL-Signatureと呼ばれる方法では、メッセージｍ∈Ｚｑに対する署名ｓは３つの群要素（ａ，ｂ，ｃ）∈Ｇ３から構成されている。
【０００５】
しかしながら、CL-signatureのように、ランダムオラクル等の（実現不可能と知られている）理想化された構成要素を用いず、数論的な仮定のみによって安全性が証明できる既存の署名方法では、メッセージｍが群Ｇの要素ではない。そのため、メッセージを秘匿した状態で、その秘匿したメッセージに対する正しい署名を保持していることを証明するという応用には供さない。メッセージが群Ｇの要素である場合にも安全な署名方法として、上記のCL-Signatureを改良した方式が非特許文献３に示されており、ランダムメッセージ攻撃に対して安全であることが示されているが、より強い選択メッセージ攻撃に対する安全性は不明である。
【０００６】
メッセージが群要素であって、選択メッセージ攻撃に強いことが証明されている方法として、非特許文献４に示された方法がある。この方法を以下に説明する。図１は署名・検証システムの構成例を示す図であり、図２は署名装置の処理フローを示す図、図３は検証装置の処理フローを示す図である。署名・検証システムは、ネットワーク８００に接続された署名装置７００と検証装置９００で構成される。
【０００７】
ｖ＝（ｑ，Ｇ，ＧＴ，ｅ，ｇ）を公開パラメータとする。ｑは大きな素数、Ｇ，ＧＴは位数ｑの群、ｅはＧ×Ｇ→ＧＴの効率的な計算が可能なペアリング、ｇを群Ｇの任意の生成元、Ｆ，Ｈ，Ｋ，Ｔを群Ｇの生成元とする。また、メッセージは群要素の対（Ｍ，Ｎ）∈Ｇ２であって、ｅ（Ｍ，Ｈ）＝ｅ（ｇ，Ｎ）を満たすものに限られているとする。
【０００８】
署名装置７００は、１以上ｑ−１以下のランダムな整数ｘを生成する（Ｓ７１０）。そして、Ｘ＝ｘｇ、Ｙ＝ｘＨを計算し（Ｓ７２０）、（ｖ，ｘｇ，ｘＨ）を公開鍵ｐｋとし、ｘを秘密鍵ｓｋとする（Ｓ７３０）。
【０００９】
署名装置７００は、１以上ｑ−１以下の乱数ｃ，ｒを生成し（Ｓ７５０）、
【００１０】
【数１】
【００１１】
ａ２＝ｃｇ
ａ３＝ｃＦ
ａ４＝ｒｇ
ａ５＝ｒＨ
を計算する（Ｓ７６０）。そして、５つの組（ａ１，ａ２，ａ３，ａ４，ａ５）∈Ｇ５を署名σとする（Ｓ７７０）。
【００１２】
検証装置９００は、ネットワーク８００を介して署名σを受け取る（Ｓ９１０）。そして、メッセージ対（Ｍ，Ｎ）と署名σに対して、
ｅ（ａ１，Ｘ＋ａ２）＝ｅ（Ｋ＋Ｍ，ｇ）ｅ（Ｔ，ａ４）であること、
ｅ（ａ２，Ｆ）＝ｅ（ｇ，ａ３）であること、
ｅ（ａ４，Ｈ）＝ｅ（ｇ，ａ５）であること、
ｅ（Ｍ，Ｈ）＝ｅ（ｇ，Ｎ）であること、
ｅ（Ｘ，Ｈ）＝ｅ（ｇ，Ｙ）であること
を確認する（Ｓ９２０）。そして、すべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する（Ｓ９３０）。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】Jens Groth and AmitSahai, “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, “AutomorphicSignatures in Bilinear Groups”, IACR e-print 200/320 ［平成２２年２月５日検索］、インターネット<URL: http://eprint.iacr.org/2009/320.pdf>.
【発明の概要】
【発明が解決しようとする課題】
【００１４】
しかしながら、従来技術は署名・検証システムでは、署名が群Ｇの５つの要素からなり、また、検証においては５つのペアリングの等式を確認するため、効率が悪いという課題がある。また、メッセージは群要素の対（Ｍ，Ｎ）∈Ｇ２であって、ｅ（Ｍ，Ｈ）＝ｅ（ｇ，Ｎ）を満たさなければならないという制約がある。
【００１５】
そこで、本発明では、署名長が短く、署名生成と署名検証の計算量がより少な署名方法を提供することを目的とする。
【課題を解決するための手段】
【００１６】
本発明の署名・検証システムは、群要素の複数メッセージに対して署名生成と署名検証を行う。まず、Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｐの群、ＧＴを位数ｐの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、Ｋを２以上の整数、＾をべき乗を示す記号とする。本発明の署名・検証システムは、署名装置と検証装置で構成される。署名装置は、署名記録部、コミットメント群要素選択部、コミットメント乱数生成部、コミットメント計算部、ＣＲＳ生成部、鍵乱数生成部、鍵計算部、鍵群要素選択部、鍵ランダマイズ部、鍵生成部、メッセージ取得部、署名乱数生成部、署名計算部、署名ランダマイズ部、署名出力部を備える。検証装置は、検証入力部、検証確認部、検証出力部を備える。署名記録部は、ｐ，Ｇ１，Ｇ２，ＧＴ，eを記録する。コミットメント群要素選択部は、群Ｇ２の生成元ｇ０，ｈ０をランダムに選択する。コミットメント乱数生成部は、１以上ｐ−１以下のランダムな整数ｘ１，…，ｘＫと整数ｙ１，…，ｙＫを生成する。コミットメント計算部は、
ｋ＝１，…，Ｋに対して、
ｇｋ＝ｇ０＾ｘｋ、
ｈｋ＝ｈ０＾ｙｋ、
を計算する。ＣＲＳ生成部は、（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ０，ｈ０，…，ｇＫ，ｈＫ）をＣＲＳ（Common Reference String）として設定し、（ｘ１，ｙ１，…，ｘＫ，ｙＫ）をトラップドアτとする。鍵乱数生成部は、１以上ｐ−１以下のランダムな整数αｚ，βｚと、ランダムな整数α０，…，αＫと整数β０，…，βＫを生成する。鍵計算部は、
ｇｚ＝ｇ０＾αｚ、
ｈｚ＝ｇ０＾βｚ、
を計算する。鍵群要素選択部は、群Ｇ２の生成元ｇｓをランダムに選択する。鍵ランダマイズ部は、
【００１７】
【数２】
【００１８】
となる（ｇｋ，ｇｓ＾αｋ）以外の組合せ（ａ１ｋ，ａ２ｋ）と、（ｈｋ，ｇｓ＾βｋ）以外の組合せ（ｂ１ｋ，ｂ２ｋ）を求める。鍵生成部は、（ｇｓ，αｚ，βｚ，α０，β０，…，αＫ，βＫ）を秘密鍵ｓｋとし、（ｇｚ，ｈｚ，｛ａ１０，ａ２０，ｂ１０，ｂ２０｝，…，｛ａ１Ｋ，ａ２Ｋ，ｂ１Ｋ，ｂ２Ｋ｝）を検証鍵ｖｋとし、当該検証鍵ｖｋを公開する。メッセージ取得部は、群Ｇ２上の１以外の元であるメッセージｍ１，…，ｍＫを受け取る。署名乱数生成部は、１以上ｐ−１以下のランダムな整数ζ，η１，…，ηＫ，ξ１，…，ξＫを生成する。署名計算部は、
【００１９】
【数３】
【００２０】
を計算する。署名ランダマイズ部は、
【００２１】
【数４】
【００２２】
となる（ｒ’ｋ，ｓ’ｋ）以外の組合せ（ｒｋ，ｓｋ）と、（ｕ’ｋ，ｖ’ｋ）以外の組合せ（ｕｋ，ｖｋ）を求める。署名出力部は、（ｚ，ｔ，ｗ，｛ｒ１，ｓ１，ｕ１，ｖ１｝，…，｛ｒＫ，ｓＫ，ｕＫ，ｖＫ｝）を署名σとして出力する。検証装置の検証入力部は、メッセージｍ１，…，ｍＫと署名σとを受信する。検証確認部は、
【００２３】
【数５】
【００２４】
で得られるＡ，Ｂに対して、
【００２５】
【数６】
【００２６】
であることを確認する。検証出力部は、検証確認部がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する。
【発明の効果】
【００２７】
本発明の署名・検証システムは、異なる群（Ｇ１，Ｇ２）からなる双線形写像を利用し、群Ｇ１から群Ｇ２への写像が困難であることを仮定し、異なる生成元の指数部を求めることが難しい性質を利用し、２つの異なる群上でのメッセージを署名のアウトプットとしている。
【００２８】
したがって、本発明の署名・検証システムによれば、群要素の複数メッセージに対して、ここに署名を生成するよりも、署名長を短くでき、署名生成と署名検証に必要な計算量を少なくできる。
【図面の簡単な説明】
【００２９】
【図１】従来の署名・検証システムの構成例を示す図。
【図２】従来の署名装置の処理フローを示す図。
【図３】従来の検証装置の処理フローを示す図。
【図４】実施例１、実施例１変形例１、実施例１変形例２の署名・検証システムの機能構成例を示す図。
【図５】実施例１、実施例１変形例１、実施例１変形例２の署名装置の処理フローを示す図。
【図６】本発明の検証装置の処理フローを示す図。
【図７】実施例２の署名・検証システムの機能構成例を示す図。
【図８】実施例２の署名装置の処理フローを示す図。
【発明を実施するための形態】
【００３０】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００３１】
図４に実施例１の署名・検証システムの機能構成例を、図５に実施例１の署名装置の処理フローを、図６に実施例１の検証装置の処理フローを示す。この署名・検証システムは、ネットワーク８００で接続された署名装置１００と検証装置２００で構成され、群要素の複数メッセージに対して署名生成と署名検証を行う。なお、署名装置１００で生成された署名を、記録媒体で検証装置２００に渡す場合には署名装置１００と検証装置２００はネットワーク８００で接続されている必要はない。
【００３２】
Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｐの群、ＧＴを位数ｐの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、Ｋを２以上の整数、＾をべき乗を示す記号とする。署名装置１００は、コミットメント群要素選択部１１０、コミットメント乱数生成部１１５、コミットメント計算部１２０、ＣＲＳ生成部１２５、鍵乱数生成部１３０、鍵計算部１３５、鍵群要素選択部１４０、鍵ランダマイズ部１４５、鍵生成部１５０、メッセージ取得部１５５、署名乱数生成部１６０、署名計算部１６５、署名ランダマイズ部１７０、署名出力部１７５、署名記録部１９０を備える。検証装置２００は、検証入力部２１０、検証確認部２２０、検証出力部２３０を備える。
【００３３】
署名記録部１９０は、あらかじめｐ，Ｇ１，Ｇ２，ＧＴ，eを記録しておく。コミットメント群要素選択部１１０は、群Ｇ２の生成元ｇ０，ｈ０をランダムに選択する（Ｓ１１０）。コミットメント乱数生成部１１５は、１以上ｐ−１以下のランダムな整数ｘ１，…，ｘＫと整数ｙ１，…，ｙＫを生成する（Ｓ１１５）。コミットメント計算部１２０は、
ｋ＝１，…，Ｋに対して、
ｇｋ＝ｇ０＾ｘｋ、
ｈｋ＝ｈ０＾ｙｋ、
を計算する（Ｓ１２０）。ＣＲＳ生成部１２５は、コミットメント鍵ｃｋ（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ０，ｈ０，…，ｇＫ，ｈＫ）をＣＲＳ（Common Reference String）として設定し、（ｘ１，ｙ１，…，ｘＫ，ｙＫ）をトラップドアτとする（Ｓ１２５）。鍵乱数生成部１３０は、１以上ｐ−１以下のランダムな整数αｚ，βｚと、ランダムな整数α０，…，αＫと整数β０，…，βＫを生成する（Ｓ１３０）。
【００３４】
鍵計算部１３５は、
ｇｚ＝ｇ０＾αｚ、
ｈｚ＝ｇ０＾βｚ、
を計算する（Ｓ１３５）。鍵群要素選択部１４０は、群Ｇ２の生成元ｇｓをランダムに選択する（Ｓ１４０）。鍵ランダマイズ部１４５は、
【００３５】
【数７】
【００３６】
となる（ｇｋ，ｇｓ＾αｋ）以外の組合せ（ａ１ｋ，ａ２ｋ）と、（ｈｋ，ｇｓ＾βｋ）以外の組合せ（ｂ１ｋ，ｂ２ｋ）を求める（Ｓ１４５）。鍵生成部１５０は、（ｇｓ，αｚ，βｚ，α０，β０，…，αＫ，βＫ）を秘密鍵ｓｋとし、（ｇｚ，ｈｚ，｛ａ１０，ａ２０，ｂ１０，ｂ２０｝，…，｛ａ１Ｋ，ａ２Ｋ，ｂ１Ｋ，ｂ２Ｋ｝）を検証鍵ｖｋとし、当該検証鍵ｖｋを公開する（Ｓ１５０）。
【００３７】
メッセージ取得部１５５は、群Ｇ２上の１以外の元であるメッセージｍ１，…，ｍＫを受け取る（Ｓ１５５）。なお、「メッセージｍ１，…，ｍＫを受け取る」とは、何らかの方法でメッセージｍ１，…，ｍＫが利用できる状態になることであり、外部から入力されたメッセージｍ１，…，ｍＫを受信することや、署名記録部１９０などにあらかじめ記録しておいたメッセージｍ１，…，ｍＫを読み出すことなどを含む意味である。署名乱数生成部１６０は、１以上ｐ−１以下のランダムな整数ζ，η１，…，ηＫ，ξ１，…，ξＫを生成する（Ｓ１６０）。署名計算部１６５は、
【００３８】
【数８】
【００３９】
を計算する（Ｓ１６５）。署名ランダマイズ部１７０は、
【００４０】
【数９】
【００４１】
となる（ｒ’ｋ，ｓ’ｋ）以外の組合せ（ｒｋ，ｓｋ）と、（ｕ’ｋ，ｖ’ｋ）以外の組合せ（ｕｋ，ｖｋ）を求める（Ｓ１７０）。署名出力部１７５は、（ｚ，ｔ，ｗ，｛ｒ１，ｓ１，ｕ１，ｖ１｝，…，｛ｒＫ，ｓＫ，ｕＫ，ｖＫ｝）を署名σとして出力する（Ｓ１７５）。
【００４２】
ここで、鍵ランダマイズ部１４５と署名ランダマイズ部１７０の具体例について説明する。ここでは、入力される数値の組合せを（ｘ１，ｙ１），（ｘ２，ｙ２），…，（ｘＫ，ｙＫ）、出力される数値の組合せを（ｘ’１，ｙ’１），（ｘ’２，ｙ’２），…，（ｘ’Ｋ，ｙ’Ｋ）とする。つまり、この説明では、鍵ランダマイズ部１４５と署名ランダマイズ部１７０は、ｅ（ｘ１，ｙ１）ｅ（ｘ２，ｙ２）…ｅ（ｘＫ，ｙＫ）＝ｅ（ｘ’１，ｙ’１）ｅ（ｘ’２，ｙ’２）…ｅ（ｘ’Ｋ，ｙ’Ｋ）となる（ｘｋ，ｙｋ）以外の組合せ（ｘ’ｋ，ｙ’ｋ）を求める。なお、この具体例ではｙ’１＝ｙ１，ｘ’Ｋ＝ｘＫである。鍵ランダマイズ部１４５と署名ランダマイズ部１７０は、ランダマイズ乱数生成手段１４６，１７１とランダマイズ実行手段１４７，１７２とを備える。ランダマイズ乱数生成手段１４６，１７１は、１以上ｐ−１以下のランダムな整数γ１，…，γＫ−１を生成する（Ｓ１４６，Ｓ１７１）。ランダマイズ実行手段１４７，１７２は、以下のような処理をｋ＝１からｋ＝Ｋ−１まで順番に行う。
【００４３】
（１）ｙ’ｋ≠１，ｘｋ＋１≠１であることを確認する。ｙ’ｋ＝１の場合は、（ｘｋ，ｙ’ｋ）を入れ替える処理などによって、処理後のｙ’ｋの値を１以外にする。また、ｘｋ＋１＝１の場合も、（ｘｋ＋１，ｙｋ＋１）を入れ替える処理などによって、処理後のｘｋ＋１の値を１以外にする。
【００４４】
（２）ｅ（ｘｋ，ｙ’ｋ）とｅ（ｘｋ＋１，ｙｋ＋１）の間にｅ（ｘｋ＋１＾−γｋ，ｙ’ｋ）ｅ（ｘｋ＋１，ｙ’ｋ＾γｋ）を挿入することで、
ｅ（ｘ’１，ｙ’１）…ｅ（ｘｋ，ｙ’ｋ）ｅ（ｘｋ＋１，ｙｋ＋１）…ｅ（ｘＫ，ｙＫ）を、
ｅ（ｘ’１，ｙ’１）…ｅ（ｘｋｘｋ＋１＾−γｋ，ｙ’ｋ）ｅ（ｘｋ＋１，（ｙ’ｋ＾γｋ）ｙｋ＋１）…ｅ（ｘＫ，ｙＫ）のように変換し、変換後を
ｅ（ｘ’１，ｙ’１）…ｅ（ｘ’ｋ，ｙ’ｋ）ｅ（ｘｋ＋１，ｙ’ｋ＋１）…ｅ（ｘＫ，ｙＫ）
とする。
【００４５】
このような処理によって、（ｘ１，ｙ１），（ｘ２，ｙ２），…，（ｘＫ，ｙＫ）を（ｘ’１，ｙ’１），（ｘ’２，ｙ’２），…，（ｘ’Ｋ，ｙ’Ｋ）にランダマイズする。なお、ランダマイズとは、演算結果が同一になるような別の数値の組合せに書き換えることである。ランダマイズ乱数生成手段１４６，１７１が整数γ１，…，γＫ−１を偏りがないようにランダムに生成（uniformに選択）することによって、ペアリングｅ（ｘ’ｋ，ｙ’ｋ）も群ＧＴ上にuniformに分布させることができる。
【００４６】
次に、検証装置２００について説明する。検証入力部２１０は、メッセージｍ１，…，ｍＫと署名σとを取得する（Ｓ２１０）。例えば、図４のようにネットワーク８００に接続されている場合であれば、検証入力部２１０は、メッセージｍ１，…，ｍＫと署名σとを受信する。ネットワークに接続されていない場合であれば、メッセージｍ１，…，ｍＫと署名σとを記録媒体から受け取る。検証確認部２２０は、
【００４７】
【数１０】
【００４８】
で得られる値Ａ，Ｂに対して、
【００４９】
【数１１】
【００５０】
であることを確認する（Ｓ２２０）。なお、式（１）の計算は、検証確認部２２０がステップＳ２２０の中で計算してもよいし、あらかじめ検証鍵ｖｋの要素を利用して計算しておいてもよい。もしくは、鍵生成部１５０がステップＳ１５０の中で式（１）を用いて値Ａ，Ｂを求め、検証鍵ｖｋの一部として値Ａ，Ｂを公開してもよい。検証出力部２３０は、検証確認部がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する（Ｓ２３０）。例えば、署名が正しいことを示す情報として“１”を出力し、署名が正しくないことを示す情報として“０”を出力すればよい。
【００５１】
実施例１の署名・検証システムは、異なる群（Ｇ１，Ｇ２）からなる双線形写像を利用し、群Ｇ１から群Ｇ２への写像が困難であることを仮定し、異なる生成元の指数部を求めることが難しい性質を利用し、２つの異なる群上でのメッセージを署名のアウトプットとしている。したがって、実施例１の署名・検証システムによれば、群要素の複数メッセージに対して、ここに署名を生成するよりも、署名長を短くでき、署名生成と署名検証に必要な計算量を少なくできる。
【００５２】
シミュレーション
鍵生成部１５０が、Ｋ個の“１”からなるデフォルトのメッセージｍ＝｛１，１，…，１｝に対する参照署名σ０を検証鍵ｖｋに含めておく。そして、検証鍵ｖｋから参照署名σ０を引き出し、（ｚ，ｔ，ｗ，｛ｒ１，ｓ１，ｕ１，ｖ１｝，…，｛ｒＫ，ｓＫ，ｕＫ，ｖＫ｝）のそれぞれの値とする。そして、
【００５３】
【数１２】
【００５４】
を計算し、（ｚ，ｔ’，ｗ’，｛ｒ１，ｓ１，ｕ１，ｖ１｝，…，｛ｒＫ，ｓＫ，ｕＫ，ｖＫ｝）をメッセージｍ１，…，ｍＫの署名σとして出力する。
【００５５】
このように、本発明の署名・検証システムであれば、より高い安全性証明を行う際に必要となる“シミュレーション”の実行も可能になるという効果が得られる。
【００５６】
［変形例１］
本変形例では、署名装置の処理を軽減する変更を行う。図４、５を参照して変更点についてのみ説明する。署名装置１００’は、鍵乱数生成部１３０’、鍵ランダマイズ部１４５’、鍵生成部１５０’が実施例１の署名装置１００と異なる。
【００５７】
鍵乱数生成部１３０’は、ランダムな整数α０，…，αＫと整数β０，…，βＫを生成する代わりに、ランダムな整数α１，β１と、αｋ＝βｋ＝０（ｋ＝０，２，…，Ｋ）を生成する（Ｓ１３０’）。鍵ランダマイズ部１４５’は、
【００５８】
【数１３】
【００５９】
となる（ａ１０，ａ２０），…，（ａ１Ｋ，ａ２Ｋ）と（ｂ１０，ｂ２０），…，（ｂ１Ｋ，ｂ２Ｋ）を求める（Ｓ１４５’）。鍵生成部１５０’は、秘密鍵ｓｋを（ｇｓ，αｚ，βｚ，α１，β１）とする（Ｓ１５０’）。その他の構成部と処理フローは実施例１と同じである。
【００６０】
本変形例の署名装置では、αｋ＝βｋ＝０（ｋ＝０，２，…，Ｋ）としたことによって、計算量を減らすことができる。したがって、本変形例の署名・検証システムも実施例１と同様の効果が得られ、かつ署名装置の処理を軽減できる。
【００６１】
［変形例２］
変形例１は、ランダムな整数α０，…，αＫと整数β０，…，βＫの中のα１，β１を０以外としたが、他の整数を０以外としてもよい。本変形例では、αｊ，βｊを０以外とし、αｋ＝βｋ＝０（ｋ＝０，…，Ｋ ただし、ｋ≠ｊ）とする。図４、５を参照して変更点についてのみ説明する。署名装置１００”は、鍵乱数生成部１３０”、鍵ランダマイズ部１４５”、鍵生成部１５０”が実施例１の署名装置１００と異なる。
【００６２】
鍵乱数生成部１３０”は、ランダムな整数α０，…，αＫと整数β０，…，βＫを生成する代わりに、ランダムな整数αｊ，βｊと、αｋ＝βｋ＝０（ｋ＝０，…，Ｋ ただし、ｋ≠ｊ）を生成する（Ｓ１３０”）。鍵ランダマイズ部１４５”は、
【００６３】
【数１４】
【００６４】
となる（ａ１０，ａ２０），…，（ａ１Ｋ，ａ２Ｋ）と（ｂ１０，ｂ２０），…，（ｂ１Ｋ，ｂ２Ｋ）を求める（Ｓ１４５”）。鍵生成部１５０”は、秘密鍵ｓｋを（ｇｓ，αｚ，βｚ，αｊ，βｊ）とする（Ｓ１５０”）。その他の構成部と処理フローは実施例１と同じである。
【００６５】
本変形例の署名装置では、αｋ＝βｋ＝０（ｋ＝０，…，Ｋ ただし、ｋ≠ｊ）としたことによって、計算量を減らすことができる。したがって、本変形例の署名・検証システムも実施例１と同様の効果が得られ、かつ署名装置の処理を軽減できる。
【実施例２】
【００６６】
図７に実施例２の署名・検証システムの機能構成例を、図８に実施例２の署名装置の処理フローを、図６に実施例２の検証装置の処理フローを示す。この署名・検証システムは、ネットワーク８００で接続された署名装置３００と検証装置４００で構成され、群要素の複数メッセージに対して署名生成と署名検証を行う。なお、署名装置３００で生成された署名を、記録媒体で検証装置４００に渡す場合には署名装置３００と検証装置４００はネットワーク８００で接続されている必要はない。
【００６７】
Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｐの群、ＧＴを位数ｐの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、Ｋを２以上の整数、＾をべき乗を示す記号とする。署名装置３００は、コミットメント群要素選択部１１０、コミットメント乱数生成部１１５、コミットメント計算部１２０、鍵乱数生成部３３０、鍵計算部１３５、鍵群要素選択部１４０、鍵ランダマイズ部３４５、鍵生成部３５０、メッセージ取得部１５５、署名乱数生成部３６０、署名計算部３６５、署名出力部３７５、署名記録部３９０を備える。検証装置４００は、検証入力部４１０、検証確認部４２０、検証出力部２３０を備える。
【００６８】
署名記録部３９０は、あらかじめｐ，Ｇ１，Ｇ２，ＧＴ，eを記録しておく。コミットメント群要素選択部１１０は、群Ｇ２の生成元ｇ０，ｈ０をランダムに選択する（Ｓ１１０）。コミットメント乱数生成部１１５は、１以上ｐ−１以下のランダムな整数ｘ１，…，ｘＫと整数ｙ１，…，ｙＫを生成する（Ｓ１１５）。コミットメント計算部１２０は、
ｋ＝１，…，Ｋに対して、
ｇｋ＝ｇ０＾ｘｋ、
ｈｋ＝ｈ０＾ｙｋ、
を計算する（Ｓ１２０）。鍵乱数生成部３３０は、
１以上ｐ−１以下のランダムな整数αｚ，βｚと、ランダムな整数α１，β１を生成する（Ｓ３３０）。鍵計算部１３５は、
ｇｚ＝ｇ０＾αｚ、
ｈｚ＝ｇ０＾βｚ、
を計算する（Ｓ１３５）。鍵群要素選択部１４０は、群Ｇ２の生成元ｇｓをランダムに選択する（Ｓ１３５）。鍵ランダマイズ部は３４５、
ｅ（ｇｋ，ｇｓ＾αｋ）＝ｅ（ａ１０，ａ２０）ｅ（ａ１１，ａ２１）
ｅ（ｈｋ，ｇｓ＾βｋ）＝ｅ（ｂ１０，ｂ２０）ｅ（ｂ１１，ｂ２１）
となる（ａ１０，ａ２０），（ａ１１，ａ２１）と、（ｂ１０，ｂ２０），（ｂ１１，ｂ２１）を求める（Ｓ３４５）。鍵生成部３５０は、（ｇｚ，ｈｚ，｛ｇ０，ｈ０｝，…，｛ｇＫ，ｈＫ｝，｛ａ１０，ａ２０，ｂ１０，ｂ２０｝，｛ａ１１，ａ２１，ｂ１１，ｂ２１｝）を検証鍵ｖｋとし、（ｖｋ，ｇｓ，αｚ，βｚ，α１，β１）を秘密鍵ｓｋとし、検証鍵ｖｋを公開する（Ｓ３５０）。
【００６９】
メッセージ取得部１５５は、群Ｇ２上の１以外の元であるメッセージｍ１，…，ｍＫを受け取る（Ｓ１５５）。なお、「メッセージｍ１，…，ｍＫを受け取る」とは、何らかの方法でメッセージｍ１，…，ｍＫが利用できる状態になることであり、外部から入力されたメッセージｍ１，…，ｍＫを受信することや、署名記録部３９０などにあらかじめ記録しておいたメッセージｍ１，…，ｍＫを読み出すことなどを含む意味である。署名乱数生成部３６０は、１以上ｐ−１以下のランダムな整数ζ，η，ξ，ρ，δを生成する（Ｓ３６０）。署名計算部３６５は、
【００７０】
【数１５】
【００７１】
を計算する（Ｓ３６５）。署名出力部３７５は、（ｚ，ｔ，ｗ，ｒ，ｓ，ｕ，ｖ）を署名σとして出力する。
【００７２】
次に、検証装置４００の処理について説明する。検証入力部４１０は、メッセージｍ１，…，ｍＫと署名σとを取得する（Ｓ４１０）。検証確認部４２０は、
【００７３】
【数１６】
【００７４】
であることを確認する（Ｓ４２０）。検証出力部２３０は、検証確認部がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する。例えば、署名が正しいことを示す情報として“１”を出力し、署名が正しくないことを示す情報として“０”を出力すればよい。
【００７５】
実施例２の署名・検証システムも、異なる群（Ｇ１，Ｇ２）からなる双線形写像を利用し、群Ｇ１から群Ｇ２への写像が困難であることを仮定し、異なる生成元の指数部を求めることが難しい性質を利用し、２つの異なる群上でのメッセージを署名のアウトプットとしている。したがって、実施例２の署名・検証システムによれば、群要素の複数メッセージに対して、ここに署名を生成するよりも、署名長を短くでき、署名生成と署名検証に必要な計算量を少なくできる。
【００７６】
プログラム、記録媒体
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００７７】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００７８】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００７９】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００８０】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００８１】
本発明は、電子データの正当性を証明するために利用することができる。
【符号の説明】
【００８２】
１００、１００’、１００”、３００、７００ 署名装置
１１０ コミットメント群要素選択部
１１５ コミットメント乱数生成部
１２０ コミットメント計算部 １２５ ＣＲＳ生成部
１３０、１３０’、１３０”、３３０ 鍵乱数生成部
１３５ 鍵計算部 １４０ 鍵群要素選択部
１４５、１４５’、１４５”、３４５ 鍵ランダマイズ部
１４６，１７１ ランダマイズ乱数生成手段
１４７，１７２ ランダマイズ実行手段
１５０、１５０’、１５０”、３５０ 鍵生成部
１５５ メッセージ取得部 １６０、３６０ 署名乱数生成部
１６５、３６５ 署名計算部 １７０ 署名ランダマイズ部
１７５、３７５ 署名出力部 １９０、３９０ 署名記録部
２００、４００、９００ 検証装置 ２１０、４１０ 検証入力部
２２０、４２０ 検証確認部 ２３０ 検証出力部
８００ ネットワーク
【技術分野】
【０００１】
本発明は、主に電気通信を介したメッセージの授受の際に用いる署名・検証システム、署名・検証方法、署名装置、検証装置、プログラム、記録媒体に関する。
【背景技術】
【０００２】
デジタル署名はメッセージｍに対して、公開鍵ｐｋに対応する秘密鍵ｓｋを知る署名者が、メッセージｍに対して秘密鍵ｓｋを正しく使ったときにのみ計算できる値ｓを算出し、これを電子的な署名として用いるものである。正しく計算された署名は誰でも公開鍵ｐｋを用いてその正当性を検証でき、秘密鍵ｓｋを知らないいかなる第三者も正当な署名ｓを算出することはできない。
【０００３】
デジタル署名は、電子現金やクレデンシャルシステムなど様々な暗号プロトコルにおいて基本的な構成要素として利用されている。特に、利用者のプライバシーを必要とする応用においては、ゼロ知識証明と組み合わせることにより署名ｓを明かさないまま、あるメッセージｍに対する正しい署名ｓを保持しているという事実を任意の第三者に納得させるなど、高度な利用形態がしばしば見受けられる。
【０００４】
近年のペアリング技術の進展によって、群の要素がある関係を満たすという事実を効率的に証明するゼロ知識証明が構成可能になった（非特許文献１）。これによって、署名ｓが効率的なペアリングを持つ群Ｇの要素である場合、即ちｓ∈Ｇである場合、前述のように署名ｓを明かさないまま、正しい署名ｓを保持しているという事実を証明することが可能である。例えば、非特許文献２に示されている、いわゆるCL-Signatureと呼ばれる方法では、メッセージｍ∈Ｚｑに対する署名ｓは３つの群要素（ａ，ｂ，ｃ）∈Ｇ３から構成されている。
【０００５】
しかしながら、CL-signatureのように、ランダムオラクル等の（実現不可能と知られている）理想化された構成要素を用いず、数論的な仮定のみによって安全性が証明できる既存の署名方法では、メッセージｍが群Ｇの要素ではない。そのため、メッセージを秘匿した状態で、その秘匿したメッセージに対する正しい署名を保持していることを証明するという応用には供さない。メッセージが群Ｇの要素である場合にも安全な署名方法として、上記のCL-Signatureを改良した方式が非特許文献３に示されており、ランダムメッセージ攻撃に対して安全であることが示されているが、より強い選択メッセージ攻撃に対する安全性は不明である。
【０００６】
メッセージが群要素であって、選択メッセージ攻撃に強いことが証明されている方法として、非特許文献４に示された方法がある。この方法を以下に説明する。図１は署名・検証システムの構成例を示す図であり、図２は署名装置の処理フローを示す図、図３は検証装置の処理フローを示す図である。署名・検証システムは、ネットワーク８００に接続された署名装置７００と検証装置９００で構成される。
【０００７】
ｖ＝（ｑ，Ｇ，ＧＴ，ｅ，ｇ）を公開パラメータとする。ｑは大きな素数、Ｇ，ＧＴは位数ｑの群、ｅはＧ×Ｇ→ＧＴの効率的な計算が可能なペアリング、ｇを群Ｇの任意の生成元、Ｆ，Ｈ，Ｋ，Ｔを群Ｇの生成元とする。また、メッセージは群要素の対（Ｍ，Ｎ）∈Ｇ２であって、ｅ（Ｍ，Ｈ）＝ｅ（ｇ，Ｎ）を満たすものに限られているとする。
【０００８】
署名装置７００は、１以上ｑ−１以下のランダムな整数ｘを生成する（Ｓ７１０）。そして、Ｘ＝ｘｇ、Ｙ＝ｘＨを計算し（Ｓ７２０）、（ｖ，ｘｇ，ｘＨ）を公開鍵ｐｋとし、ｘを秘密鍵ｓｋとする（Ｓ７３０）。
【０００９】
署名装置７００は、１以上ｑ−１以下の乱数ｃ，ｒを生成し（Ｓ７５０）、
【００１０】
【数１】
【００１１】
ａ２＝ｃｇ
ａ３＝ｃＦ
ａ４＝ｒｇ
ａ５＝ｒＨ
を計算する（Ｓ７６０）。そして、５つの組（ａ１，ａ２，ａ３，ａ４，ａ５）∈Ｇ５を署名σとする（Ｓ７７０）。
【００１２】
検証装置９００は、ネットワーク８００を介して署名σを受け取る（Ｓ９１０）。そして、メッセージ対（Ｍ，Ｎ）と署名σに対して、
ｅ（ａ１，Ｘ＋ａ２）＝ｅ（Ｋ＋Ｍ，ｇ）ｅ（Ｔ，ａ４）であること、
ｅ（ａ２，Ｆ）＝ｅ（ｇ，ａ３）であること、
ｅ（ａ４，Ｈ）＝ｅ（ｇ，ａ５）であること、
ｅ（Ｍ，Ｈ）＝ｅ（ｇ，Ｎ）であること、
ｅ（Ｘ，Ｈ）＝ｅ（ｇ，Ｙ）であること
を確認する（Ｓ９２０）。そして、すべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する（Ｓ９３０）。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】Jens Groth and AmitSahai, “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, “AutomorphicSignatures in Bilinear Groups”, IACR e-print 200/320 ［平成２２年２月５日検索］、インターネット<URL: http://eprint.iacr.org/2009/320.pdf>.
【発明の概要】
【発明が解決しようとする課題】
【００１４】
しかしながら、従来技術は署名・検証システムでは、署名が群Ｇの５つの要素からなり、また、検証においては５つのペアリングの等式を確認するため、効率が悪いという課題がある。また、メッセージは群要素の対（Ｍ，Ｎ）∈Ｇ２であって、ｅ（Ｍ，Ｈ）＝ｅ（ｇ，Ｎ）を満たさなければならないという制約がある。
【００１５】
そこで、本発明では、署名長が短く、署名生成と署名検証の計算量がより少な署名方法を提供することを目的とする。
【課題を解決するための手段】
【００１６】
本発明の署名・検証システムは、群要素の複数メッセージに対して署名生成と署名検証を行う。まず、Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｐの群、ＧＴを位数ｐの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、Ｋを２以上の整数、＾をべき乗を示す記号とする。本発明の署名・検証システムは、署名装置と検証装置で構成される。署名装置は、署名記録部、コミットメント群要素選択部、コミットメント乱数生成部、コミットメント計算部、ＣＲＳ生成部、鍵乱数生成部、鍵計算部、鍵群要素選択部、鍵ランダマイズ部、鍵生成部、メッセージ取得部、署名乱数生成部、署名計算部、署名ランダマイズ部、署名出力部を備える。検証装置は、検証入力部、検証確認部、検証出力部を備える。署名記録部は、ｐ，Ｇ１，Ｇ２，ＧＴ，eを記録する。コミットメント群要素選択部は、群Ｇ２の生成元ｇ０，ｈ０をランダムに選択する。コミットメント乱数生成部は、１以上ｐ−１以下のランダムな整数ｘ１，…，ｘＫと整数ｙ１，…，ｙＫを生成する。コミットメント計算部は、
ｋ＝１，…，Ｋに対して、
ｇｋ＝ｇ０＾ｘｋ、
ｈｋ＝ｈ０＾ｙｋ、
を計算する。ＣＲＳ生成部は、（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ０，ｈ０，…，ｇＫ，ｈＫ）をＣＲＳ（Common Reference String）として設定し、（ｘ１，ｙ１，…，ｘＫ，ｙＫ）をトラップドアτとする。鍵乱数生成部は、１以上ｐ−１以下のランダムな整数αｚ，βｚと、ランダムな整数α０，…，αＫと整数β０，…，βＫを生成する。鍵計算部は、
ｇｚ＝ｇ０＾αｚ、
ｈｚ＝ｇ０＾βｚ、
を計算する。鍵群要素選択部は、群Ｇ２の生成元ｇｓをランダムに選択する。鍵ランダマイズ部は、
【００１７】
【数２】
【００１８】
となる（ｇｋ，ｇｓ＾αｋ）以外の組合せ（ａ１ｋ，ａ２ｋ）と、（ｈｋ，ｇｓ＾βｋ）以外の組合せ（ｂ１ｋ，ｂ２ｋ）を求める。鍵生成部は、（ｇｓ，αｚ，βｚ，α０，β０，…，αＫ，βＫ）を秘密鍵ｓｋとし、（ｇｚ，ｈｚ，｛ａ１０，ａ２０，ｂ１０，ｂ２０｝，…，｛ａ１Ｋ，ａ２Ｋ，ｂ１Ｋ，ｂ２Ｋ｝）を検証鍵ｖｋとし、当該検証鍵ｖｋを公開する。メッセージ取得部は、群Ｇ２上の１以外の元であるメッセージｍ１，…，ｍＫを受け取る。署名乱数生成部は、１以上ｐ−１以下のランダムな整数ζ，η１，…，ηＫ，ξ１，…，ξＫを生成する。署名計算部は、
【００１９】
【数３】
【００２０】
を計算する。署名ランダマイズ部は、
【００２１】
【数４】
【００２２】
となる（ｒ’ｋ，ｓ’ｋ）以外の組合せ（ｒｋ，ｓｋ）と、（ｕ’ｋ，ｖ’ｋ）以外の組合せ（ｕｋ，ｖｋ）を求める。署名出力部は、（ｚ，ｔ，ｗ，｛ｒ１，ｓ１，ｕ１，ｖ１｝，…，｛ｒＫ，ｓＫ，ｕＫ，ｖＫ｝）を署名σとして出力する。検証装置の検証入力部は、メッセージｍ１，…，ｍＫと署名σとを受信する。検証確認部は、
【００２３】
【数５】
【００２４】
で得られるＡ，Ｂに対して、
【００２５】
【数６】
【００２６】
であることを確認する。検証出力部は、検証確認部がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する。
【発明の効果】
【００２７】
本発明の署名・検証システムは、異なる群（Ｇ１，Ｇ２）からなる双線形写像を利用し、群Ｇ１から群Ｇ２への写像が困難であることを仮定し、異なる生成元の指数部を求めることが難しい性質を利用し、２つの異なる群上でのメッセージを署名のアウトプットとしている。
【００２８】
したがって、本発明の署名・検証システムによれば、群要素の複数メッセージに対して、ここに署名を生成するよりも、署名長を短くでき、署名生成と署名検証に必要な計算量を少なくできる。
【図面の簡単な説明】
【００２９】
【図１】従来の署名・検証システムの構成例を示す図。
【図２】従来の署名装置の処理フローを示す図。
【図３】従来の検証装置の処理フローを示す図。
【図４】実施例１、実施例１変形例１、実施例１変形例２の署名・検証システムの機能構成例を示す図。
【図５】実施例１、実施例１変形例１、実施例１変形例２の署名装置の処理フローを示す図。
【図６】本発明の検証装置の処理フローを示す図。
【図７】実施例２の署名・検証システムの機能構成例を示す図。
【図８】実施例２の署名装置の処理フローを示す図。
【発明を実施するための形態】
【００３０】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００３１】
図４に実施例１の署名・検証システムの機能構成例を、図５に実施例１の署名装置の処理フローを、図６に実施例１の検証装置の処理フローを示す。この署名・検証システムは、ネットワーク８００で接続された署名装置１００と検証装置２００で構成され、群要素の複数メッセージに対して署名生成と署名検証を行う。なお、署名装置１００で生成された署名を、記録媒体で検証装置２００に渡す場合には署名装置１００と検証装置２００はネットワーク８００で接続されている必要はない。
【００３２】
Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｐの群、ＧＴを位数ｐの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、Ｋを２以上の整数、＾をべき乗を示す記号とする。署名装置１００は、コミットメント群要素選択部１１０、コミットメント乱数生成部１１５、コミットメント計算部１２０、ＣＲＳ生成部１２５、鍵乱数生成部１３０、鍵計算部１３５、鍵群要素選択部１４０、鍵ランダマイズ部１４５、鍵生成部１５０、メッセージ取得部１５５、署名乱数生成部１６０、署名計算部１６５、署名ランダマイズ部１７０、署名出力部１７５、署名記録部１９０を備える。検証装置２００は、検証入力部２１０、検証確認部２２０、検証出力部２３０を備える。
【００３３】
署名記録部１９０は、あらかじめｐ，Ｇ１，Ｇ２，ＧＴ，eを記録しておく。コミットメント群要素選択部１１０は、群Ｇ２の生成元ｇ０，ｈ０をランダムに選択する（Ｓ１１０）。コミットメント乱数生成部１１５は、１以上ｐ−１以下のランダムな整数ｘ１，…，ｘＫと整数ｙ１，…，ｙＫを生成する（Ｓ１１５）。コミットメント計算部１２０は、
ｋ＝１，…，Ｋに対して、
ｇｋ＝ｇ０＾ｘｋ、
ｈｋ＝ｈ０＾ｙｋ、
を計算する（Ｓ１２０）。ＣＲＳ生成部１２５は、コミットメント鍵ｃｋ（ｑ，Ｇ１，Ｇ２，ＧＴ，e，ｇ０，ｈ０，…，ｇＫ，ｈＫ）をＣＲＳ（Common Reference String）として設定し、（ｘ１，ｙ１，…，ｘＫ，ｙＫ）をトラップドアτとする（Ｓ１２５）。鍵乱数生成部１３０は、１以上ｐ−１以下のランダムな整数αｚ，βｚと、ランダムな整数α０，…，αＫと整数β０，…，βＫを生成する（Ｓ１３０）。
【００３４】
鍵計算部１３５は、
ｇｚ＝ｇ０＾αｚ、
ｈｚ＝ｇ０＾βｚ、
を計算する（Ｓ１３５）。鍵群要素選択部１４０は、群Ｇ２の生成元ｇｓをランダムに選択する（Ｓ１４０）。鍵ランダマイズ部１４５は、
【００３５】
【数７】
【００３６】
となる（ｇｋ，ｇｓ＾αｋ）以外の組合せ（ａ１ｋ，ａ２ｋ）と、（ｈｋ，ｇｓ＾βｋ）以外の組合せ（ｂ１ｋ，ｂ２ｋ）を求める（Ｓ１４５）。鍵生成部１５０は、（ｇｓ，αｚ，βｚ，α０，β０，…，αＫ，βＫ）を秘密鍵ｓｋとし、（ｇｚ，ｈｚ，｛ａ１０，ａ２０，ｂ１０，ｂ２０｝，…，｛ａ１Ｋ，ａ２Ｋ，ｂ１Ｋ，ｂ２Ｋ｝）を検証鍵ｖｋとし、当該検証鍵ｖｋを公開する（Ｓ１５０）。
【００３７】
メッセージ取得部１５５は、群Ｇ２上の１以外の元であるメッセージｍ１，…，ｍＫを受け取る（Ｓ１５５）。なお、「メッセージｍ１，…，ｍＫを受け取る」とは、何らかの方法でメッセージｍ１，…，ｍＫが利用できる状態になることであり、外部から入力されたメッセージｍ１，…，ｍＫを受信することや、署名記録部１９０などにあらかじめ記録しておいたメッセージｍ１，…，ｍＫを読み出すことなどを含む意味である。署名乱数生成部１６０は、１以上ｐ−１以下のランダムな整数ζ，η１，…，ηＫ，ξ１，…，ξＫを生成する（Ｓ１６０）。署名計算部１６５は、
【００３８】
【数８】
【００３９】
を計算する（Ｓ１６５）。署名ランダマイズ部１７０は、
【００４０】
【数９】
【００４１】
となる（ｒ’ｋ，ｓ’ｋ）以外の組合せ（ｒｋ，ｓｋ）と、（ｕ’ｋ，ｖ’ｋ）以外の組合せ（ｕｋ，ｖｋ）を求める（Ｓ１７０）。署名出力部１７５は、（ｚ，ｔ，ｗ，｛ｒ１，ｓ１，ｕ１，ｖ１｝，…，｛ｒＫ，ｓＫ，ｕＫ，ｖＫ｝）を署名σとして出力する（Ｓ１７５）。
【００４２】
ここで、鍵ランダマイズ部１４５と署名ランダマイズ部１７０の具体例について説明する。ここでは、入力される数値の組合せを（ｘ１，ｙ１），（ｘ２，ｙ２），…，（ｘＫ，ｙＫ）、出力される数値の組合せを（ｘ’１，ｙ’１），（ｘ’２，ｙ’２），…，（ｘ’Ｋ，ｙ’Ｋ）とする。つまり、この説明では、鍵ランダマイズ部１４５と署名ランダマイズ部１７０は、ｅ（ｘ１，ｙ１）ｅ（ｘ２，ｙ２）…ｅ（ｘＫ，ｙＫ）＝ｅ（ｘ’１，ｙ’１）ｅ（ｘ’２，ｙ’２）…ｅ（ｘ’Ｋ，ｙ’Ｋ）となる（ｘｋ，ｙｋ）以外の組合せ（ｘ’ｋ，ｙ’ｋ）を求める。なお、この具体例ではｙ’１＝ｙ１，ｘ’Ｋ＝ｘＫである。鍵ランダマイズ部１４５と署名ランダマイズ部１７０は、ランダマイズ乱数生成手段１４６，１７１とランダマイズ実行手段１４７，１７２とを備える。ランダマイズ乱数生成手段１４６，１７１は、１以上ｐ−１以下のランダムな整数γ１，…，γＫ−１を生成する（Ｓ１４６，Ｓ１７１）。ランダマイズ実行手段１４７，１７２は、以下のような処理をｋ＝１からｋ＝Ｋ−１まで順番に行う。
【００４３】
（１）ｙ’ｋ≠１，ｘｋ＋１≠１であることを確認する。ｙ’ｋ＝１の場合は、（ｘｋ，ｙ’ｋ）を入れ替える処理などによって、処理後のｙ’ｋの値を１以外にする。また、ｘｋ＋１＝１の場合も、（ｘｋ＋１，ｙｋ＋１）を入れ替える処理などによって、処理後のｘｋ＋１の値を１以外にする。
【００４４】
（２）ｅ（ｘｋ，ｙ’ｋ）とｅ（ｘｋ＋１，ｙｋ＋１）の間にｅ（ｘｋ＋１＾−γｋ，ｙ’ｋ）ｅ（ｘｋ＋１，ｙ’ｋ＾γｋ）を挿入することで、
ｅ（ｘ’１，ｙ’１）…ｅ（ｘｋ，ｙ’ｋ）ｅ（ｘｋ＋１，ｙｋ＋１）…ｅ（ｘＫ，ｙＫ）を、
ｅ（ｘ’１，ｙ’１）…ｅ（ｘｋｘｋ＋１＾−γｋ，ｙ’ｋ）ｅ（ｘｋ＋１，（ｙ’ｋ＾γｋ）ｙｋ＋１）…ｅ（ｘＫ，ｙＫ）のように変換し、変換後を
ｅ（ｘ’１，ｙ’１）…ｅ（ｘ’ｋ，ｙ’ｋ）ｅ（ｘｋ＋１，ｙ’ｋ＋１）…ｅ（ｘＫ，ｙＫ）
とする。
【００４５】
このような処理によって、（ｘ１，ｙ１），（ｘ２，ｙ２），…，（ｘＫ，ｙＫ）を（ｘ’１，ｙ’１），（ｘ’２，ｙ’２），…，（ｘ’Ｋ，ｙ’Ｋ）にランダマイズする。なお、ランダマイズとは、演算結果が同一になるような別の数値の組合せに書き換えることである。ランダマイズ乱数生成手段１４６，１７１が整数γ１，…，γＫ−１を偏りがないようにランダムに生成（uniformに選択）することによって、ペアリングｅ（ｘ’ｋ，ｙ’ｋ）も群ＧＴ上にuniformに分布させることができる。
【００４６】
次に、検証装置２００について説明する。検証入力部２１０は、メッセージｍ１，…，ｍＫと署名σとを取得する（Ｓ２１０）。例えば、図４のようにネットワーク８００に接続されている場合であれば、検証入力部２１０は、メッセージｍ１，…，ｍＫと署名σとを受信する。ネットワークに接続されていない場合であれば、メッセージｍ１，…，ｍＫと署名σとを記録媒体から受け取る。検証確認部２２０は、
【００４７】
【数１０】
【００４８】
で得られる値Ａ，Ｂに対して、
【００４９】
【数１１】
【００５０】
であることを確認する（Ｓ２２０）。なお、式（１）の計算は、検証確認部２２０がステップＳ２２０の中で計算してもよいし、あらかじめ検証鍵ｖｋの要素を利用して計算しておいてもよい。もしくは、鍵生成部１５０がステップＳ１５０の中で式（１）を用いて値Ａ，Ｂを求め、検証鍵ｖｋの一部として値Ａ，Ｂを公開してもよい。検証出力部２３０は、検証確認部がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する（Ｓ２３０）。例えば、署名が正しいことを示す情報として“１”を出力し、署名が正しくないことを示す情報として“０”を出力すればよい。
【００５１】
実施例１の署名・検証システムは、異なる群（Ｇ１，Ｇ２）からなる双線形写像を利用し、群Ｇ１から群Ｇ２への写像が困難であることを仮定し、異なる生成元の指数部を求めることが難しい性質を利用し、２つの異なる群上でのメッセージを署名のアウトプットとしている。したがって、実施例１の署名・検証システムによれば、群要素の複数メッセージに対して、ここに署名を生成するよりも、署名長を短くでき、署名生成と署名検証に必要な計算量を少なくできる。
【００５２】
シミュレーション
鍵生成部１５０が、Ｋ個の“１”からなるデフォルトのメッセージｍ＝｛１，１，…，１｝に対する参照署名σ０を検証鍵ｖｋに含めておく。そして、検証鍵ｖｋから参照署名σ０を引き出し、（ｚ，ｔ，ｗ，｛ｒ１，ｓ１，ｕ１，ｖ１｝，…，｛ｒＫ，ｓＫ，ｕＫ，ｖＫ｝）のそれぞれの値とする。そして、
【００５３】
【数１２】
【００５４】
を計算し、（ｚ，ｔ’，ｗ’，｛ｒ１，ｓ１，ｕ１，ｖ１｝，…，｛ｒＫ，ｓＫ，ｕＫ，ｖＫ｝）をメッセージｍ１，…，ｍＫの署名σとして出力する。
【００５５】
このように、本発明の署名・検証システムであれば、より高い安全性証明を行う際に必要となる“シミュレーション”の実行も可能になるという効果が得られる。
【００５６】
［変形例１］
本変形例では、署名装置の処理を軽減する変更を行う。図４、５を参照して変更点についてのみ説明する。署名装置１００’は、鍵乱数生成部１３０’、鍵ランダマイズ部１４５’、鍵生成部１５０’が実施例１の署名装置１００と異なる。
【００５７】
鍵乱数生成部１３０’は、ランダムな整数α０，…，αＫと整数β０，…，βＫを生成する代わりに、ランダムな整数α１，β１と、αｋ＝βｋ＝０（ｋ＝０，２，…，Ｋ）を生成する（Ｓ１３０’）。鍵ランダマイズ部１４５’は、
【００５８】
【数１３】
【００５９】
となる（ａ１０，ａ２０），…，（ａ１Ｋ，ａ２Ｋ）と（ｂ１０，ｂ２０），…，（ｂ１Ｋ，ｂ２Ｋ）を求める（Ｓ１４５’）。鍵生成部１５０’は、秘密鍵ｓｋを（ｇｓ，αｚ，βｚ，α１，β１）とする（Ｓ１５０’）。その他の構成部と処理フローは実施例１と同じである。
【００６０】
本変形例の署名装置では、αｋ＝βｋ＝０（ｋ＝０，２，…，Ｋ）としたことによって、計算量を減らすことができる。したがって、本変形例の署名・検証システムも実施例１と同様の効果が得られ、かつ署名装置の処理を軽減できる。
【００６１】
［変形例２］
変形例１は、ランダムな整数α０，…，αＫと整数β０，…，βＫの中のα１，β１を０以外としたが、他の整数を０以外としてもよい。本変形例では、αｊ，βｊを０以外とし、αｋ＝βｋ＝０（ｋ＝０，…，Ｋ ただし、ｋ≠ｊ）とする。図４、５を参照して変更点についてのみ説明する。署名装置１００”は、鍵乱数生成部１３０”、鍵ランダマイズ部１４５”、鍵生成部１５０”が実施例１の署名装置１００と異なる。
【００６２】
鍵乱数生成部１３０”は、ランダムな整数α０，…，αＫと整数β０，…，βＫを生成する代わりに、ランダムな整数αｊ，βｊと、αｋ＝βｋ＝０（ｋ＝０，…，Ｋ ただし、ｋ≠ｊ）を生成する（Ｓ１３０”）。鍵ランダマイズ部１４５”は、
【００６３】
【数１４】
【００６４】
となる（ａ１０，ａ２０），…，（ａ１Ｋ，ａ２Ｋ）と（ｂ１０，ｂ２０），…，（ｂ１Ｋ，ｂ２Ｋ）を求める（Ｓ１４５”）。鍵生成部１５０”は、秘密鍵ｓｋを（ｇｓ，αｚ，βｚ，αｊ，βｊ）とする（Ｓ１５０”）。その他の構成部と処理フローは実施例１と同じである。
【００６５】
本変形例の署名装置では、αｋ＝βｋ＝０（ｋ＝０，…，Ｋ ただし、ｋ≠ｊ）としたことによって、計算量を減らすことができる。したがって、本変形例の署名・検証システムも実施例１と同様の効果が得られ、かつ署名装置の処理を軽減できる。
【実施例２】
【００６６】
図７に実施例２の署名・検証システムの機能構成例を、図８に実施例２の署名装置の処理フローを、図６に実施例２の検証装置の処理フローを示す。この署名・検証システムは、ネットワーク８００で接続された署名装置３００と検証装置４００で構成され、群要素の複数メッセージに対して署名生成と署名検証を行う。なお、署名装置３００で生成された署名を、記録媒体で検証装置４００に渡す場合には署名装置３００と検証装置４００はネットワーク８００で接続されている必要はない。
【００６７】
Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｐの群、ＧＴを位数ｐの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、Ｋを２以上の整数、＾をべき乗を示す記号とする。署名装置３００は、コミットメント群要素選択部１１０、コミットメント乱数生成部１１５、コミットメント計算部１２０、鍵乱数生成部３３０、鍵計算部１３５、鍵群要素選択部１４０、鍵ランダマイズ部３４５、鍵生成部３５０、メッセージ取得部１５５、署名乱数生成部３６０、署名計算部３６５、署名出力部３７５、署名記録部３９０を備える。検証装置４００は、検証入力部４１０、検証確認部４２０、検証出力部２３０を備える。
【００６８】
署名記録部３９０は、あらかじめｐ，Ｇ１，Ｇ２，ＧＴ，eを記録しておく。コミットメント群要素選択部１１０は、群Ｇ２の生成元ｇ０，ｈ０をランダムに選択する（Ｓ１１０）。コミットメント乱数生成部１１５は、１以上ｐ−１以下のランダムな整数ｘ１，…，ｘＫと整数ｙ１，…，ｙＫを生成する（Ｓ１１５）。コミットメント計算部１２０は、
ｋ＝１，…，Ｋに対して、
ｇｋ＝ｇ０＾ｘｋ、
ｈｋ＝ｈ０＾ｙｋ、
を計算する（Ｓ１２０）。鍵乱数生成部３３０は、
１以上ｐ−１以下のランダムな整数αｚ，βｚと、ランダムな整数α１，β１を生成する（Ｓ３３０）。鍵計算部１３５は、
ｇｚ＝ｇ０＾αｚ、
ｈｚ＝ｇ０＾βｚ、
を計算する（Ｓ１３５）。鍵群要素選択部１４０は、群Ｇ２の生成元ｇｓをランダムに選択する（Ｓ１３５）。鍵ランダマイズ部は３４５、
ｅ（ｇｋ，ｇｓ＾αｋ）＝ｅ（ａ１０，ａ２０）ｅ（ａ１１，ａ２１）
ｅ（ｈｋ，ｇｓ＾βｋ）＝ｅ（ｂ１０，ｂ２０）ｅ（ｂ１１，ｂ２１）
となる（ａ１０，ａ２０），（ａ１１，ａ２１）と、（ｂ１０，ｂ２０），（ｂ１１，ｂ２１）を求める（Ｓ３４５）。鍵生成部３５０は、（ｇｚ，ｈｚ，｛ｇ０，ｈ０｝，…，｛ｇＫ，ｈＫ｝，｛ａ１０，ａ２０，ｂ１０，ｂ２０｝，｛ａ１１，ａ２１，ｂ１１，ｂ２１｝）を検証鍵ｖｋとし、（ｖｋ，ｇｓ，αｚ，βｚ，α１，β１）を秘密鍵ｓｋとし、検証鍵ｖｋを公開する（Ｓ３５０）。
【００６９】
メッセージ取得部１５５は、群Ｇ２上の１以外の元であるメッセージｍ１，…，ｍＫを受け取る（Ｓ１５５）。なお、「メッセージｍ１，…，ｍＫを受け取る」とは、何らかの方法でメッセージｍ１，…，ｍＫが利用できる状態になることであり、外部から入力されたメッセージｍ１，…，ｍＫを受信することや、署名記録部３９０などにあらかじめ記録しておいたメッセージｍ１，…，ｍＫを読み出すことなどを含む意味である。署名乱数生成部３６０は、１以上ｐ−１以下のランダムな整数ζ，η，ξ，ρ，δを生成する（Ｓ３６０）。署名計算部３６５は、
【００７０】
【数１５】
【００７１】
を計算する（Ｓ３６５）。署名出力部３７５は、（ｚ，ｔ，ｗ，ｒ，ｓ，ｕ，ｖ）を署名σとして出力する。
【００７２】
次に、検証装置４００の処理について説明する。検証入力部４１０は、メッセージｍ１，…，ｍＫと署名σとを取得する（Ｓ４１０）。検証確認部４２０は、
【００７３】
【数１６】
【００７４】
であることを確認する（Ｓ４２０）。検証出力部２３０は、検証確認部がすべての条件を満たすと確認した場合には署名が正しいことを示す情報を出力し、いずれかの条件を満たさないと確認した場合に署名が正しくないことを示す情報を出力する。例えば、署名が正しいことを示す情報として“１”を出力し、署名が正しくないことを示す情報として“０”を出力すればよい。
【００７５】
実施例２の署名・検証システムも、異なる群（Ｇ１，Ｇ２）からなる双線形写像を利用し、群Ｇ１から群Ｇ２への写像が困難であることを仮定し、異なる生成元の指数部を求めることが難しい性質を利用し、２つの異なる群上でのメッセージを署名のアウトプットとしている。したがって、実施例２の署名・検証システムによれば、群要素の複数メッセージに対して、ここに署名を生成するよりも、署名長を短くでき、署名生成と署名検証に必要な計算量を少なくできる。
【００７６】
プログラム、記録媒体
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００７７】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００７８】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００７９】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００８０】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００８１】
本発明は、電子データの正当性を証明するために利用することができる。
【符号の説明】
【００８２】
１００、１００’、１００”、３００、７００ 署名装置
１１０ コミットメント群要素選択部
１１５ コミットメント乱数生成部
１２０ コミットメント計算部 １２５ ＣＲＳ生成部
１３０、１３０’、１３０”、３３０ 鍵乱数生成部
１３５ 鍵計算部 １４０ 鍵群要素選択部
１４５、１４５’、１４５”、３４５ 鍵ランダマイズ部
１４６，１７１ ランダマイズ乱数生成手段
１４７，１７２ ランダマイズ実行手段
１５０、１５０’、１５０”、３５０ 鍵生成部
１５５ メッセージ取得部 １６０、３６０ 署名乱数生成部
１６５、３６５ 署名計算部 １７０ 署名ランダマイズ部
１７５、３７５ 署名出力部 １９０、３９０ 署名記録部
２００、４００、９００ 検証装置 ２１０、４１０ 検証入力部
２２０、４２０ 検証確認部 ２３０ 検証出力部
８００ ネットワーク
【特許請求の範囲】
【請求項１】
Ｇ１、Ｇ２をＧ１からＧ２への写像が困難な位数ｐの群、ＧＴを位数ｐの群、ｅをＧ１×Ｇ２→ＧＴの双線形写像、Ｋを２以上の整数、＾をべき乗を示す記号とし、
ｐ，Ｇ１，Ｇ２，ＧＴ，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 ]