ディジタル署名・検証システム、ディジタル署名・検証方法、署名装置、検証装置、及びそれらのプログラム
【課題】群要素メッセージに対するディジタル署名・検証システムにおいて、従来より公開鍵、署名の長さが短く、検証式の計算量が少なく、かつ、高い安全性が証明可能なディジタル署名・検証システムを提供する。
【解決手段】従来技術（ＡＨＯ方式）における２つの検証式で共通して使用される署名要素の個数が多くなるように検証式を構成することで、署名の偽造に対する安全性を損なうことなく、検証式の一方から公開鍵の一部を除去して検証式を簡略化する。
【解決手段】従来技術（ＡＨＯ方式）における２つの検証式で共通して使用される署名要素の個数が多くなるように検証式を構成することで、署名の偽造に対する安全性を損なうことなく、検証式の一方から公開鍵の一部を除去して検証式を簡略化する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電気通信システムに関し、暗号プロトコル中で利用しやすい効率的なディジタル署名・検証システム、ディジタル署名・検証方法、署名装置、検証装置、及びそれらのプログラムに関する。
【背景技術】
【０００２】
ディジタル署名はメッセージｍに対して、公開鍵pkに対応する秘密鍵skを知る署名者が、メッセージｍに対して秘密鍵skを正しく使ったときにのみ計算できる値ｓを算出し、これを電子的な署名として用いるものである。正しく計算された署名は誰でも公開鍵pkを用いてその正当性を検証することが可能であり、秘密鍵skを知らないいかなる第三者も正当な署名ｓを算出することはできない。
【０００３】
ディジタル署名は電子現金やクレデンシャルシステムなど、様々な暗号プロトコルにおいて基本的な構成要素として利用されている。特に、利用者のプライバシーを必要とする応用においては、ゼロ知識証明と組み合わせることにより、署名ｓを明かさないまま、あるメッセージｍに対する正しい署名ｓを保持しているという事実を任意の第三者に納得させるなど、高度な利用形態がしばしば見受けられる。
【０００４】
近年のペアリング技術の進展により、群の要素がある関係を満たすという事実を効率的に証明するゼロ知識証明が構成可能となった（非特許文献１参照）。これによって、署名ｓが効率的なペアリングを持つ群Ｇの要素である場合、すなわちｓ∈Ｇである場合に、前述のように署名ｓを明かさないまま正しい署名ｓを保持しているという事実を証明することが可能となった。
【０００５】
例えば、非特許文献２で開示されているCL-Signatureと呼ばれる方法では、メッセージｍ∈Ｚqに対する署名ｓは３つの群要素（ａ，ｂ，ｃ）∈Ｇ3から構成されている。
【０００６】
しかしながらCL-Signatureのように、ランダムオラクルモデル等の理想化された構成要素を用いず、数論的な仮定のみにより安全性が証明できる既存の署名方法では、メッセージｍが群Ｇの要素ではないため、メッセージｍを秘匿した状態でその秘匿したメッセージに対する正しい電子署名を保持していることを証明するという応用には適さない。
【０００７】
メッセージｍが群Ｇの要素である場合にも安全な署名方法として、CL-Signatureを改良した方法が非特許文献３で開示されている。この方法はランダムメッセージ攻撃に対しても安全である。ただし、より強い攻撃である選択メッセージ攻撃に対する安全性は不明である。
【０００８】
メッセージが群要素である場合に、選択メッセージ攻撃に強いことが保証されている方法（ＡＨＯ方式）が非特許文献４で開示されている。このＡＨＯ方式による従来のディジタル署名・検証システム２００について、以下、説明する。
【０００９】
図１にディジタル署名・検証システム２００の機能構成例を、図２にその処理フロー例（Ｓ１〜６）をそれぞれ示す。
ディジタル署名・検証システム２００は、署名装置１１０と検証装置１２０とからなる。署名装置１１０と検証装置１２０との間は、任意のネットワーク５０で結ばれる。
署名装置１１０は、生成元選択部１１１と公開情報生成部１１２と乱数生成部１１３と鍵生成部１１４と署名生成部１１５とを備える。
【００１０】
生成元選択部１１１は、Ｇ1、Ｇ2がそれぞれ位数ｐ（ｐは素数）の群であるとして、生成元g1とＧ1から、g2をＧ2から、ｇrとｈuを単位元を除くＧ1から、それぞれランダムに選択する（Ｓ１）。
公開情報生成部１１２は、公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する（Ｓ２）。ここで、ｅはバイリニアマップであり、ｅ：Ｇ1×Ｇ2→ＧTである。
【００１１】
乱数生成部１１３は、１以上ｐ−１以下のランダムな整数α、β、γz、δz、γi(ｉ＝１,・・・,ｋ、ｋはセキュリティパラメータで２以上の整数）、δi、ζ、ρ、τ、ψ及びωを生成する（Ｓ３）。
鍵生成部１１４は、(ｇr,g2α)をランダマイズしてａ00、ａ01、ａ10、ａ11を計算し、(ｈu,g2β)をランダマイズしてｂ00、ｂ01、ｂ10、ｂ11を計算し、更に、
【００１２】
【数１】
【００１３】
を計算して、公開鍵vk＝(ｇz,ｈz,ｇr,ｈu,ｇ1,・・・,ｇk,ｈ1,・・・,ｈk,ａ00,ａ01,ａ10,ａ11,ｂ00,ｂ01,ｂ10,ｂ11）及び秘密鍵sk＝(vk,α,β,γz,δz,γ1,・・・,γk,δ1,・・・,δk)を生成し、公開鍵vkを公開する（Ｓ４）。なお、秘密鍵skは署名装置内に安全に格納される。
署名生成部１１５は、Ｇ2の１以外の元であるメッセージｍ＝(ｍ1，・・・,ｍk)が入力され、
【００１４】
【数２】
【００１５】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ,ｖ,ｗ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk)とともに送信する（Ｓ５）。メッセージｍの長さは、セキュリティパラメータｋに依存して決定され、短いメッセージに対しては明示的に１でパディングされるものとする。
【００１６】
検証装置１２０は、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ,ｖ,ｗ)とメッセージｍ＝(ｍ1，・・・,ｍk)を受信し、公開鍵vk＝(ｇz,ｈz,ｇr,ｈu,ｇ1,・・・,ｇk,ｈ1,・・・,ｈk,ａ00,ａ01,ａ10,ａ11,ｂ00,ｂ01,ｂ10,ｂ11）を用いて、２つの検証式
【００１７】
【数３】
【００１８】
の成否を計算し、共に成立すれば署名は正しく、改ざんされていないとの検証結果（例えばそれを意味する数値である１）を出力し、それ以外の場合は署名は正しくないとの検証結果（例えばそれを意味する数値である０）を出力する（Ｓ６）。
【先行技術文献】
【非特許文献】
【００１９】
【非特許文献１】Jens Groth and Amit Sahai, "Efficient Non-interactive Proof Systems for Bilinear Groups", Eurocrypt2008, LNCS 2965, p.415-432
【非特許文献２】Jan Camenisch and Anna Lysyanskaya,"Signature Schemes and Anonymous Credentials from Bilinear Maps", Crypto 2004, LNCS 3152, p.56-72
【非特許文献３】Matthew Green and Susan Hohenberger,"Universally Composable Adaptive Oblivious Transfer", IACR e-Print archive, 2008, [2010年10月4日検索]、インターネット<URL: http://eprint.iacr.org/2008/163.pdf>
【非特許文献４】Masayuki Abe, Kristiyan Haralambiev, Miyako Ohkubo,"Signing on Elements in Bilinear Groups for Modular Protocol Design", IACR e-Print archive, 2010, [2010年10月4日検索]、インターネット<URL: http://eprint.iacr.org/2010/133.pdf>
【発明の概要】
【発明が解決しようとする課題】
【００２０】
従来技術（ＡＨＯ方式）では、署名が７つの群要素からなることに加え、検証時には１０＋２ｋ個のペアリング演算を要するため、署名長、演算量共に多い。
【００２１】
本発明の目的は、群要素メッセージに対するディジタル署名・検証方式において、従来より公開鍵、署名の長さが短く、検証式の計算量が少なく、かつ、高い安全性が証明可能なディジタル署名・検証システム、ディジタル署名・検証方法、署名装置、検証装置、及びそのプログラムを提供することにある。
【課題を解決するための手段】
【００２２】
本発明のディジタル署名・検証システムは、署名装置と検証装置とからなる。 署名装置は、生成元選択部と公開情報生成部と乱数生成部と鍵生成部と署名生成部とを備える。
生成元選択部は、Ｇ1、Ｇ2がそれぞれ位数ｐの群（ｐは素数）であるとして、生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する。
【００２３】
公開情報生成部は、公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する。ここで、ｅはバイリニアマップであり、ｅ：Ｇ1×Ｇ2→ＧTである。
乱数生成部は、１以上ｐ−１以下のランダムな整数δu、α、γz、δz、γi(ｉ＝１,・・・,ｋ、ｋは２以上の整数）、δi、ζ,ρ,及びτを生成する。
鍵生成部は、
【００２４】
【数４】
【００２５】
を計算し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk,ｈ1,・・・,ｈk）及び秘密鍵sk＝(vk,α,γz,δz,δu,γ1,・・・,γk,δ1,・・・,δk)を生成し、公開鍵vkを公開する。
署名生成部は、Ｇ2の１以外の元であるメッセージｍ＝(ｍ1，・・・,ｍk)が入力され、
【００２６】
【数５】
【００２７】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk)とともに送信する。
検証装置は、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)とメッセージｍ＝(ｍ1，・・・,ｍk)を受信し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk,ｈ1,・・・,ｈk）を用いて、２つの検証式
【００２８】
【数６】
【００２９】
の成否を計算し、共に成立すれば署名は正しいとの検証結果を出力し、それ以外の場合は署名は正しくないとの検証結果を出力する。
【発明の効果】
【００３０】
本発明のディジタル署名・検証システム、ディジタル署名・検証方法、署名装置、検証装置、及びそのプログラムによれば、群要素メッセージに対するディジタル署名・検証方式について、従来より公開鍵、署名の長さが短く、検証式の計算量が少なく、かつ、高い安全性が証明可能な、効率のよいディジタル署名・検証方式を提供することができる。
【図面の簡単な説明】
【００３１】
【図１】本発明のディジタル署名・検証システムの機能構成例を示す図。
【図２】本発明のディジタル署名・検証システムの処理フロー例を示す図。
【発明を実施するための形態】
【００３２】
以下、本発明の実施の形態について、詳細に説明する。
【実施例１】
【００３３】
本発明の特徴は、従来技術（ＡＨＯ方式）における２つの検証式で共通して使用される署名要素の個数が多くなるように検証式を構成する点にある。これにより、攻撃者が署名要素の一部を改ざんしても、両方の検証式を同時に満たすことが一層困難になるため、署名の偽造に対する安全性を損なうことなく、検証式の一方から公開鍵の一部を除去して検証式を簡略化することが可能となる。そして、検証式の簡略化により、公開鍵、署名ともに不必要な要素を除去することができ、従来より公開鍵、署名の長さを短くすることができる。
【００３４】
以下、具体的な構成例について説明する。
図１に本発明のディジタル署名・検証システム１００の機能構成例を、図２にその処理フロー例（Ｓ１〜６）をそれぞれ示す。
本発明のディジタル署名・検証システム１００は、署名装置１１０と検証装置１２０とからなる。署名装置１１０と検証装置１２０との間は、任意のネットワーク５０で結ばれる。
【００３５】
署名装置１１０は、生成元選択部１１１と公開情報生成部１１２と乱数生成部１１３と鍵生成部１１４と署名生成部１１５とを備える。
生成元選択部１１１は、Ｇ1、Ｇ2がそれぞれ位数ｐ（ｐは素数）の群であるとして、生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する（Ｓ１）。なお、Ｇ1とＧ2は同一の群でも異なる群でも構わない。
【００３６】
公開情報生成部１１２は、公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する（Ｓ２）。ここで、ｅはバイリニアマップであり、ｅ：Ｇ1×Ｇ2→ＧTである。
乱数生成部１１３は、１以上ｐ−１以下のランダムな整数δu、α、γz、δz、γi(ｉ＝１,・・・,ｋ、ｋはセキュリティパラメータで２以上の整数）、δi、ζ,ρ,及びτを生成する（Ｓ３）。
鍵生成部１１４は、
【００３７】
【数７】
【００３８】
を計算し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk,ｈ1,・・・,ｈk）及び秘密鍵sk＝(vk,α,γz,δz,δu,γ1,・・・,γk,δ1,・・・,δk)を生成し、公開鍵vkを公開する（Ｓ４）。なお、秘密鍵skは署名装置内に安全に格納される。
署名生成部１１５は、Ｇ2の１以外の元であるメッセージｍ＝(ｍ1，・・・,ｍk)が入力され、
【００３９】
【数８】
【００４０】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk)とともに送信する（Ｓ５）。メッセージｍの長さは、セキュリティパラメータｋに依存して決定され、短いメッセージに対しては明示的に１でパディングされるものとする。
【００４１】
検証装置１２０は、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)とメッセージｍ＝(ｍ1，・・・,ｍk)を受信し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk,ｈ1,・・・,ｈk）を用いて、２つの検証式
【００４２】
【数９】
【００４３】
の成否を計算し、共に成立すれば署名は正しく、改ざんされていないとの検証結果（例えばそれを意味する数値である１）を出力し、それ以外の場合は署名は正しくないとの検証結果（例えばそれを意味する数値である０）を出力する（Ｓ６）。
【００４４】
以上のように、本発明においては、２つの検証式で共通して使用される署名要素を増やしたため、攻撃者が署名要素の一部を改ざんしても、両方の検証式を同時に満たすことが一層困難となる。そのため、署名の偽造に対する安全性を損なうことなく、検証式の一方から公開鍵の一部を除去して検証式を簡略化できる。そして、この簡略化により、公開鍵、署名ともに不必要な要素を除去することができ、署名の群要素の数を７個から５個に、検証時のペアリング演算の個数を１０＋２ｋ個から６＋２ｋ個に減らすことができる。これにより、従来より公開鍵、署名の長さが短く、検証式の計算量が少なく、かつ、高い安全性が証明可能な、効率のよい署名方式を提供することができる。具体的には、署名長が短くなることで、通信帯域及びメモリを削減することができ、また、検証の計算量が少ないことにより、高速な署名検証が可能となる。
【００４５】
なお、検証式で用いるペアリング演算ｅ(ａ,g2)について、予め署名装置１１０の鍵生成部１１４でＡ＝ｅ(ａ,g2)と計算しておき、このＡをａの代わりに公開鍵vkに含め、これをそのまま検証式で用いてもよい。このように構成することで、検証時に行うペアリング演算をさらに１個減らすことができる。ただし、この場合、ａよりもＡの方が表現が長いため、公開鍵vkの長さが長くなる。また、この署名をゼロ知識証明と組み合わせる場合、検証式はＧ1、Ｇ2の要素のみから成り立っていることが望ましいため、Ａを直接検証式に使うことができず、ｅ(ａ,g2)のようにａとg2とをバラにして提供する必要が生じる。もっとも、ゼロ知識証明よりもやや弱い証明系であるWitness-Indistinguishable証明を組み合わせる場合には、検証式にＧTの要素が入っていても構わないため、その場合にはＡのまま利用が可能である。従って、公開鍵としてａを含めるかＡを含めるかは、ユーザが本発明の署名方式をどのように使いたいかにより任意に選択すればよい。
【実施例２】
【００４６】
実施例１は、２つの群Ｇ1、Ｇ2は同一の群である場合も異なる群である場合も適用可能な構成である。一方、実施例２は、Ｇ1、Ｇ2が異なる群である場合に限定することで、更に鍵長の短縮、検証式の計算量の低減を図った構成である。
【００４７】
以下、具体的な構成例について説明する。
図１に本発明のディジタル署名・検証システム１００' の機能構成例を、図２にその処理フロー例（Ｓ１〜６）をそれぞれ示す。
本発明のディジタル署名・検証システム１００' は、署名装置１１０と検証装置１２０とからなる。署名装置１１０と検証装置１２０との間は、任意のネットワーク５０で結ばれる。
【００４８】
署名装置１１０は、生成元選択部１１１と公開情報生成部１１２と乱数生成部１１３と鍵生成部１１４と署名生成部１１５とを備える。
生成元選択部１１１は、Ｇ1、Ｇ2がそれぞれ位数ｐ（ｐは素数）の異なる群であるとして、生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する（Ｓ１）。
【００４９】
公開情報生成部１１２は、公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する（Ｓ２）。ここで、ｅはバイリニアマップであり、ｅ：Ｇ1×Ｇ2→ＧTである。
乱数生成部１１３は、１以上ｐ−１以下のランダムな整数δu、α、γz、γi(ｉ＝１,・・・,ｋ、ｋはセキュリティパラメータで２以上の整数）、ζ,ρ,及びτを生成する（Ｓ３）。
鍵生成部１１４は、
【００５０】
【数１０】
【００５１】
を計算し、公開鍵vk＝(Λ,ｇz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk）及び秘密鍵sk＝(vk,α,γz,δu,γ1,・・・,γk)を生成し、公開鍵vkを公開する（Ｓ４）。なお、秘密鍵skは署名装置内に安全に格納される。
署名生成部１１５は、Ｇ2の１以外の元であるメッセージｍ＝(ｍ1，・・・,ｍk)が入力され、
【００５２】
【数１１】
【００５３】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk)とともに送信する（Ｓ５）。メッセージｍの長さは、セキュリティパラメータｋに依存して決定され、短いメッセージに対しては明示的に１でパディングされるものとする。
【００５４】
検証装置１２０は、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)とメッセージｍ＝(ｍ1，・・・,ｍk)を受信し、公開鍵vk＝(Λ,ｇz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk）を用いて、２つの検証式
【００５５】
【数１２】
【００５６】
の成否を計算し、共に成立すれば署名は正しく、改ざんされていないとの検証結果（例えばそれを意味する数値である１）を出力し、それ以外の場合は署名は正しくないとの検証結果（例えばそれを意味する数値である０）を出力する（Ｓ６）。
【００５７】
以上より、本発明によれば、実施例１より更に公開鍵、秘密鍵の長さの短縮（要素が各１＋ｋ個減）、及び検証式の計算量の低減（ペアリング演算の個数が１＋ｋ個減）を図ることができるため、より効率的なディジタル署名方式を提供することができる。なお、実施例２においても実施例１と同様に、検証式で用いるペアリング演算ｅ(ａ,g2)について、予め署名装置１１０の鍵生成部１１４でＡ＝ｅ(ａ,g2)と計算しておき、このＡをａの代わりに公開鍵vkに含め、これをそのまま検証式で用いてもよい。
【実施例３】
【００５８】
実施例１は、群要素メッセージｍがＧ2に属する要素のみから成るものに対して適用可能な構成である。一方、実施例３は、群要素メッセージｍがＧ1、Ｇ2の両方にまたがるものであっても適用可能な構成である。
【００５９】
以下、具体的な構成例について説明する。
図１に本発明のディジタル署名・検証システム１００'' の機能構成例を、図２にその処理フロー例（Ｓ１〜６）をそれぞれ示す。
【００６０】
本発明のディジタル署名・検証システム１００'' は、署名装置１１０と検証装置１２０とからなる。署名装置１１０と検証装置１２０との間は、任意のネットワーク５０で結ばれる。
署名装置１１０は、生成元選択部１１１と公開情報生成部１１２と乱数生成部１１３と鍵生成部１１４と署名生成部１１５とを備える。
生成元選択部１１１は、Ｇ1、Ｇ2がそれぞれ位数ｐ（ｐは素数）の異なる群であるとして、生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する（Ｓ１）。
【００６１】
公開情報生成部１１２は、公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する（Ｓ２）。ここで、ｅはバイリニアマップであり、ｅ：Ｇ1×Ｇ2→ＧTである。
乱数生成部１１３は、１以上ｐ−１以下のランダムな整数δu、α、γz、δz、γi(ｉ＝１,・・・,k1、k1は２以上の整数）、δj(ｊ＝k1＋１,・・・,k2、k2はセキュリティパラメータでk1より大きい整数）、ζ,ρ,τ，及びωを生成する（Ｓ３）。
鍵生成部１１４は、
【００６２】
【数１３】
【００６３】
を計算し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ｈv,ａ,ｇ1,・・・,ｇk1,ｈk1+1,・・・,ｈk2）及び秘密鍵sk＝(vk,α,γz,δz,δu,γ1,・・・,γk1,δk1+1,・・・,δk2)を生成し、公開鍵vkを公開する（Ｓ４）。なお、秘密鍵skは署名装置内に安全に格納される。
署名生成部１１５は、Ｇ2の１以外の元であるｍ1，・・・,ｍk1とＧ1の１以外の元であるｍk1+1，・・・,ｍk2とからなるメッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)が入力され、
【００６４】
【数１４】
【００６５】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ,ｖ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)とともに送信する（Ｓ５）。メッセージｍの長さは、セキュリティパラメータk2に依存して決定され、短いメッセージに対しては明示的に１でパディングされるものとする。
【００６６】
検証装置１２０は、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ,ｖ)とメッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)を受信し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ｈv,ａ,ｇ1,・・・,ｇk1,ｈk1+1,・・・,ｈk2）を用いて、２つの検証式
【００６７】
【数１５】
【００６８】
の成否を計算し、共に成立すれば署名は正しく、改ざんされていないとの検証結果（例えばそれを意味する数値である１）を出力し、それ以外の場合は署名は正しくないとの検証結果（例えばそれを意味する数値である０）を出力する（Ｓ６）。
【００６９】
以上より、本発明によれば、群要素メッセージｍがＧ1、Ｇ2の両方にまたがるものである場合においても、実施例１と同様に、従来より効率的なディジタル署名方式を提供することができる。なお、実施例３においても実施例１と同様に、検証式で用いるペアリング演算ｅ(ａ,g2)について、予め署名装置１１０の鍵生成部１１４でＡ＝ｅ(ａ,g2)と計算しておき、このＡをａの代わりに公開鍵vkに含め、これをそのまま検証式で用いてもよい。
【００７０】
上記各実施例のディジタル署名・検証システムにおける各処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、本発明のディジタル署名・検証システムの各機能は必要に応じ、併合・分割しても構わない。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【００７１】
本発明のディジタル署名・検証システムの署名装置と検証装置をコンピュータによって実現する場合、装置及びその各部が有す機能の処理内容はプログラムによって記述される。そのプログラムは、例えば、ハードディスク装置に格納されており、実行時には必要なプログラムやデータがＲＡＭ(Random Access Memory)に読み込まれる。その読み込まれたプログラムがＣＰＵにより実行されることにより、コンピュータ上で各処理内容が実現される。なお、処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【技術分野】
【０００１】
本発明は、電気通信システムに関し、暗号プロトコル中で利用しやすい効率的なディジタル署名・検証システム、ディジタル署名・検証方法、署名装置、検証装置、及びそれらのプログラムに関する。
【背景技術】
【０００２】
ディジタル署名はメッセージｍに対して、公開鍵pkに対応する秘密鍵skを知る署名者が、メッセージｍに対して秘密鍵skを正しく使ったときにのみ計算できる値ｓを算出し、これを電子的な署名として用いるものである。正しく計算された署名は誰でも公開鍵pkを用いてその正当性を検証することが可能であり、秘密鍵skを知らないいかなる第三者も正当な署名ｓを算出することはできない。
【０００３】
ディジタル署名は電子現金やクレデンシャルシステムなど、様々な暗号プロトコルにおいて基本的な構成要素として利用されている。特に、利用者のプライバシーを必要とする応用においては、ゼロ知識証明と組み合わせることにより、署名ｓを明かさないまま、あるメッセージｍに対する正しい署名ｓを保持しているという事実を任意の第三者に納得させるなど、高度な利用形態がしばしば見受けられる。
【０００４】
近年のペアリング技術の進展により、群の要素がある関係を満たすという事実を効率的に証明するゼロ知識証明が構成可能となった（非特許文献１参照）。これによって、署名ｓが効率的なペアリングを持つ群Ｇの要素である場合、すなわちｓ∈Ｇである場合に、前述のように署名ｓを明かさないまま正しい署名ｓを保持しているという事実を証明することが可能となった。
【０００５】
例えば、非特許文献２で開示されているCL-Signatureと呼ばれる方法では、メッセージｍ∈Ｚqに対する署名ｓは３つの群要素（ａ，ｂ，ｃ）∈Ｇ3から構成されている。
【０００６】
しかしながらCL-Signatureのように、ランダムオラクルモデル等の理想化された構成要素を用いず、数論的な仮定のみにより安全性が証明できる既存の署名方法では、メッセージｍが群Ｇの要素ではないため、メッセージｍを秘匿した状態でその秘匿したメッセージに対する正しい電子署名を保持していることを証明するという応用には適さない。
【０００７】
メッセージｍが群Ｇの要素である場合にも安全な署名方法として、CL-Signatureを改良した方法が非特許文献３で開示されている。この方法はランダムメッセージ攻撃に対しても安全である。ただし、より強い攻撃である選択メッセージ攻撃に対する安全性は不明である。
【０００８】
メッセージが群要素である場合に、選択メッセージ攻撃に強いことが保証されている方法（ＡＨＯ方式）が非特許文献４で開示されている。このＡＨＯ方式による従来のディジタル署名・検証システム２００について、以下、説明する。
【０００９】
図１にディジタル署名・検証システム２００の機能構成例を、図２にその処理フロー例（Ｓ１〜６）をそれぞれ示す。
ディジタル署名・検証システム２００は、署名装置１１０と検証装置１２０とからなる。署名装置１１０と検証装置１２０との間は、任意のネットワーク５０で結ばれる。
署名装置１１０は、生成元選択部１１１と公開情報生成部１１２と乱数生成部１１３と鍵生成部１１４と署名生成部１１５とを備える。
【００１０】
生成元選択部１１１は、Ｇ1、Ｇ2がそれぞれ位数ｐ（ｐは素数）の群であるとして、生成元g1とＧ1から、g2をＧ2から、ｇrとｈuを単位元を除くＧ1から、それぞれランダムに選択する（Ｓ１）。
公開情報生成部１１２は、公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する（Ｓ２）。ここで、ｅはバイリニアマップであり、ｅ：Ｇ1×Ｇ2→ＧTである。
【００１１】
乱数生成部１１３は、１以上ｐ−１以下のランダムな整数α、β、γz、δz、γi(ｉ＝１,・・・,ｋ、ｋはセキュリティパラメータで２以上の整数）、δi、ζ、ρ、τ、ψ及びωを生成する（Ｓ３）。
鍵生成部１１４は、(ｇr,g2α)をランダマイズしてａ00、ａ01、ａ10、ａ11を計算し、(ｈu,g2β)をランダマイズしてｂ00、ｂ01、ｂ10、ｂ11を計算し、更に、
【００１２】
【数１】
【００１３】
を計算して、公開鍵vk＝(ｇz,ｈz,ｇr,ｈu,ｇ1,・・・,ｇk,ｈ1,・・・,ｈk,ａ00,ａ01,ａ10,ａ11,ｂ00,ｂ01,ｂ10,ｂ11）及び秘密鍵sk＝(vk,α,β,γz,δz,γ1,・・・,γk,δ1,・・・,δk)を生成し、公開鍵vkを公開する（Ｓ４）。なお、秘密鍵skは署名装置内に安全に格納される。
署名生成部１１５は、Ｇ2の１以外の元であるメッセージｍ＝(ｍ1，・・・,ｍk)が入力され、
【００１４】
【数２】
【００１５】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ,ｖ,ｗ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk)とともに送信する（Ｓ５）。メッセージｍの長さは、セキュリティパラメータｋに依存して決定され、短いメッセージに対しては明示的に１でパディングされるものとする。
【００１６】
検証装置１２０は、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ,ｖ,ｗ)とメッセージｍ＝(ｍ1，・・・,ｍk)を受信し、公開鍵vk＝(ｇz,ｈz,ｇr,ｈu,ｇ1,・・・,ｇk,ｈ1,・・・,ｈk,ａ00,ａ01,ａ10,ａ11,ｂ00,ｂ01,ｂ10,ｂ11）を用いて、２つの検証式
【００１７】
【数３】
【００１８】
の成否を計算し、共に成立すれば署名は正しく、改ざんされていないとの検証結果（例えばそれを意味する数値である１）を出力し、それ以外の場合は署名は正しくないとの検証結果（例えばそれを意味する数値である０）を出力する（Ｓ６）。
【先行技術文献】
【非特許文献】
【００１９】
【非特許文献１】Jens Groth and Amit Sahai, "Efficient Non-interactive Proof Systems for Bilinear Groups", Eurocrypt2008, LNCS 2965, p.415-432
【非特許文献２】Jan Camenisch and Anna Lysyanskaya,"Signature Schemes and Anonymous Credentials from Bilinear Maps", Crypto 2004, LNCS 3152, p.56-72
【非特許文献３】Matthew Green and Susan Hohenberger,"Universally Composable Adaptive Oblivious Transfer", IACR e-Print archive, 2008, [2010年10月4日検索]、インターネット<URL: http://eprint.iacr.org/2008/163.pdf>
【非特許文献４】Masayuki Abe, Kristiyan Haralambiev, Miyako Ohkubo,"Signing on Elements in Bilinear Groups for Modular Protocol Design", IACR e-Print archive, 2010, [2010年10月4日検索]、インターネット<URL: http://eprint.iacr.org/2010/133.pdf>
【発明の概要】
【発明が解決しようとする課題】
【００２０】
従来技術（ＡＨＯ方式）では、署名が７つの群要素からなることに加え、検証時には１０＋２ｋ個のペアリング演算を要するため、署名長、演算量共に多い。
【００２１】
本発明の目的は、群要素メッセージに対するディジタル署名・検証方式において、従来より公開鍵、署名の長さが短く、検証式の計算量が少なく、かつ、高い安全性が証明可能なディジタル署名・検証システム、ディジタル署名・検証方法、署名装置、検証装置、及びそのプログラムを提供することにある。
【課題を解決するための手段】
【００２２】
本発明のディジタル署名・検証システムは、署名装置と検証装置とからなる。 署名装置は、生成元選択部と公開情報生成部と乱数生成部と鍵生成部と署名生成部とを備える。
生成元選択部は、Ｇ1、Ｇ2がそれぞれ位数ｐの群（ｐは素数）であるとして、生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する。
【００２３】
公開情報生成部は、公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する。ここで、ｅはバイリニアマップであり、ｅ：Ｇ1×Ｇ2→ＧTである。
乱数生成部は、１以上ｐ−１以下のランダムな整数δu、α、γz、δz、γi(ｉ＝１,・・・,ｋ、ｋは２以上の整数）、δi、ζ,ρ,及びτを生成する。
鍵生成部は、
【００２４】
【数４】
【００２５】
を計算し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk,ｈ1,・・・,ｈk）及び秘密鍵sk＝(vk,α,γz,δz,δu,γ1,・・・,γk,δ1,・・・,δk)を生成し、公開鍵vkを公開する。
署名生成部は、Ｇ2の１以外の元であるメッセージｍ＝(ｍ1，・・・,ｍk)が入力され、
【００２６】
【数５】
【００２７】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk)とともに送信する。
検証装置は、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)とメッセージｍ＝(ｍ1，・・・,ｍk)を受信し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk,ｈ1,・・・,ｈk）を用いて、２つの検証式
【００２８】
【数６】
【００２９】
の成否を計算し、共に成立すれば署名は正しいとの検証結果を出力し、それ以外の場合は署名は正しくないとの検証結果を出力する。
【発明の効果】
【００３０】
本発明のディジタル署名・検証システム、ディジタル署名・検証方法、署名装置、検証装置、及びそのプログラムによれば、群要素メッセージに対するディジタル署名・検証方式について、従来より公開鍵、署名の長さが短く、検証式の計算量が少なく、かつ、高い安全性が証明可能な、効率のよいディジタル署名・検証方式を提供することができる。
【図面の簡単な説明】
【００３１】
【図１】本発明のディジタル署名・検証システムの機能構成例を示す図。
【図２】本発明のディジタル署名・検証システムの処理フロー例を示す図。
【発明を実施するための形態】
【００３２】
以下、本発明の実施の形態について、詳細に説明する。
【実施例１】
【００３３】
本発明の特徴は、従来技術（ＡＨＯ方式）における２つの検証式で共通して使用される署名要素の個数が多くなるように検証式を構成する点にある。これにより、攻撃者が署名要素の一部を改ざんしても、両方の検証式を同時に満たすことが一層困難になるため、署名の偽造に対する安全性を損なうことなく、検証式の一方から公開鍵の一部を除去して検証式を簡略化することが可能となる。そして、検証式の簡略化により、公開鍵、署名ともに不必要な要素を除去することができ、従来より公開鍵、署名の長さを短くすることができる。
【００３４】
以下、具体的な構成例について説明する。
図１に本発明のディジタル署名・検証システム１００の機能構成例を、図２にその処理フロー例（Ｓ１〜６）をそれぞれ示す。
本発明のディジタル署名・検証システム１００は、署名装置１１０と検証装置１２０とからなる。署名装置１１０と検証装置１２０との間は、任意のネットワーク５０で結ばれる。
【００３５】
署名装置１１０は、生成元選択部１１１と公開情報生成部１１２と乱数生成部１１３と鍵生成部１１４と署名生成部１１５とを備える。
生成元選択部１１１は、Ｇ1、Ｇ2がそれぞれ位数ｐ（ｐは素数）の群であるとして、生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する（Ｓ１）。なお、Ｇ1とＧ2は同一の群でも異なる群でも構わない。
【００３６】
公開情報生成部１１２は、公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する（Ｓ２）。ここで、ｅはバイリニアマップであり、ｅ：Ｇ1×Ｇ2→ＧTである。
乱数生成部１１３は、１以上ｐ−１以下のランダムな整数δu、α、γz、δz、γi(ｉ＝１,・・・,ｋ、ｋはセキュリティパラメータで２以上の整数）、δi、ζ,ρ,及びτを生成する（Ｓ３）。
鍵生成部１１４は、
【００３７】
【数７】
【００３８】
を計算し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk,ｈ1,・・・,ｈk）及び秘密鍵sk＝(vk,α,γz,δz,δu,γ1,・・・,γk,δ1,・・・,δk)を生成し、公開鍵vkを公開する（Ｓ４）。なお、秘密鍵skは署名装置内に安全に格納される。
署名生成部１１５は、Ｇ2の１以外の元であるメッセージｍ＝(ｍ1，・・・,ｍk)が入力され、
【００３９】
【数８】
【００４０】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk)とともに送信する（Ｓ５）。メッセージｍの長さは、セキュリティパラメータｋに依存して決定され、短いメッセージに対しては明示的に１でパディングされるものとする。
【００４１】
検証装置１２０は、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)とメッセージｍ＝(ｍ1，・・・,ｍk)を受信し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk,ｈ1,・・・,ｈk）を用いて、２つの検証式
【００４２】
【数９】
【００４３】
の成否を計算し、共に成立すれば署名は正しく、改ざんされていないとの検証結果（例えばそれを意味する数値である１）を出力し、それ以外の場合は署名は正しくないとの検証結果（例えばそれを意味する数値である０）を出力する（Ｓ６）。
【００４４】
以上のように、本発明においては、２つの検証式で共通して使用される署名要素を増やしたため、攻撃者が署名要素の一部を改ざんしても、両方の検証式を同時に満たすことが一層困難となる。そのため、署名の偽造に対する安全性を損なうことなく、検証式の一方から公開鍵の一部を除去して検証式を簡略化できる。そして、この簡略化により、公開鍵、署名ともに不必要な要素を除去することができ、署名の群要素の数を７個から５個に、検証時のペアリング演算の個数を１０＋２ｋ個から６＋２ｋ個に減らすことができる。これにより、従来より公開鍵、署名の長さが短く、検証式の計算量が少なく、かつ、高い安全性が証明可能な、効率のよい署名方式を提供することができる。具体的には、署名長が短くなることで、通信帯域及びメモリを削減することができ、また、検証の計算量が少ないことにより、高速な署名検証が可能となる。
【００４５】
なお、検証式で用いるペアリング演算ｅ(ａ,g2)について、予め署名装置１１０の鍵生成部１１４でＡ＝ｅ(ａ,g2)と計算しておき、このＡをａの代わりに公開鍵vkに含め、これをそのまま検証式で用いてもよい。このように構成することで、検証時に行うペアリング演算をさらに１個減らすことができる。ただし、この場合、ａよりもＡの方が表現が長いため、公開鍵vkの長さが長くなる。また、この署名をゼロ知識証明と組み合わせる場合、検証式はＧ1、Ｇ2の要素のみから成り立っていることが望ましいため、Ａを直接検証式に使うことができず、ｅ(ａ,g2)のようにａとg2とをバラにして提供する必要が生じる。もっとも、ゼロ知識証明よりもやや弱い証明系であるWitness-Indistinguishable証明を組み合わせる場合には、検証式にＧTの要素が入っていても構わないため、その場合にはＡのまま利用が可能である。従って、公開鍵としてａを含めるかＡを含めるかは、ユーザが本発明の署名方式をどのように使いたいかにより任意に選択すればよい。
【実施例２】
【００４６】
実施例１は、２つの群Ｇ1、Ｇ2は同一の群である場合も異なる群である場合も適用可能な構成である。一方、実施例２は、Ｇ1、Ｇ2が異なる群である場合に限定することで、更に鍵長の短縮、検証式の計算量の低減を図った構成である。
【００４７】
以下、具体的な構成例について説明する。
図１に本発明のディジタル署名・検証システム１００' の機能構成例を、図２にその処理フロー例（Ｓ１〜６）をそれぞれ示す。
本発明のディジタル署名・検証システム１００' は、署名装置１１０と検証装置１２０とからなる。署名装置１１０と検証装置１２０との間は、任意のネットワーク５０で結ばれる。
【００４８】
署名装置１１０は、生成元選択部１１１と公開情報生成部１１２と乱数生成部１１３と鍵生成部１１４と署名生成部１１５とを備える。
生成元選択部１１１は、Ｇ1、Ｇ2がそれぞれ位数ｐ（ｐは素数）の異なる群であるとして、生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する（Ｓ１）。
【００４９】
公開情報生成部１１２は、公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する（Ｓ２）。ここで、ｅはバイリニアマップであり、ｅ：Ｇ1×Ｇ2→ＧTである。
乱数生成部１１３は、１以上ｐ−１以下のランダムな整数δu、α、γz、γi(ｉ＝１,・・・,ｋ、ｋはセキュリティパラメータで２以上の整数）、ζ,ρ,及びτを生成する（Ｓ３）。
鍵生成部１１４は、
【００５０】
【数１０】
【００５１】
を計算し、公開鍵vk＝(Λ,ｇz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk）及び秘密鍵sk＝(vk,α,γz,δu,γ1,・・・,γk)を生成し、公開鍵vkを公開する（Ｓ４）。なお、秘密鍵skは署名装置内に安全に格納される。
署名生成部１１５は、Ｇ2の１以外の元であるメッセージｍ＝(ｍ1，・・・,ｍk)が入力され、
【００５２】
【数１１】
【００５３】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk)とともに送信する（Ｓ５）。メッセージｍの長さは、セキュリティパラメータｋに依存して決定され、短いメッセージに対しては明示的に１でパディングされるものとする。
【００５４】
検証装置１２０は、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)とメッセージｍ＝(ｍ1，・・・,ｍk)を受信し、公開鍵vk＝(Λ,ｇz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk）を用いて、２つの検証式
【００５５】
【数１２】
【００５６】
の成否を計算し、共に成立すれば署名は正しく、改ざんされていないとの検証結果（例えばそれを意味する数値である１）を出力し、それ以外の場合は署名は正しくないとの検証結果（例えばそれを意味する数値である０）を出力する（Ｓ６）。
【００５７】
以上より、本発明によれば、実施例１より更に公開鍵、秘密鍵の長さの短縮（要素が各１＋ｋ個減）、及び検証式の計算量の低減（ペアリング演算の個数が１＋ｋ個減）を図ることができるため、より効率的なディジタル署名方式を提供することができる。なお、実施例２においても実施例１と同様に、検証式で用いるペアリング演算ｅ(ａ,g2)について、予め署名装置１１０の鍵生成部１１４でＡ＝ｅ(ａ,g2)と計算しておき、このＡをａの代わりに公開鍵vkに含め、これをそのまま検証式で用いてもよい。
【実施例３】
【００５８】
実施例１は、群要素メッセージｍがＧ2に属する要素のみから成るものに対して適用可能な構成である。一方、実施例３は、群要素メッセージｍがＧ1、Ｇ2の両方にまたがるものであっても適用可能な構成である。
【００５９】
以下、具体的な構成例について説明する。
図１に本発明のディジタル署名・検証システム１００'' の機能構成例を、図２にその処理フロー例（Ｓ１〜６）をそれぞれ示す。
【００６０】
本発明のディジタル署名・検証システム１００'' は、署名装置１１０と検証装置１２０とからなる。署名装置１１０と検証装置１２０との間は、任意のネットワーク５０で結ばれる。
署名装置１１０は、生成元選択部１１１と公開情報生成部１１２と乱数生成部１１３と鍵生成部１１４と署名生成部１１５とを備える。
生成元選択部１１１は、Ｇ1、Ｇ2がそれぞれ位数ｐ（ｐは素数）の異なる群であるとして、生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する（Ｓ１）。
【００６１】
公開情報生成部１１２は、公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する（Ｓ２）。ここで、ｅはバイリニアマップであり、ｅ：Ｇ1×Ｇ2→ＧTである。
乱数生成部１１３は、１以上ｐ−１以下のランダムな整数δu、α、γz、δz、γi(ｉ＝１,・・・,k1、k1は２以上の整数）、δj(ｊ＝k1＋１,・・・,k2、k2はセキュリティパラメータでk1より大きい整数）、ζ,ρ,τ，及びωを生成する（Ｓ３）。
鍵生成部１１４は、
【００６２】
【数１３】
【００６３】
を計算し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ｈv,ａ,ｇ1,・・・,ｇk1,ｈk1+1,・・・,ｈk2）及び秘密鍵sk＝(vk,α,γz,δz,δu,γ1,・・・,γk1,δk1+1,・・・,δk2)を生成し、公開鍵vkを公開する（Ｓ４）。なお、秘密鍵skは署名装置内に安全に格納される。
署名生成部１１５は、Ｇ2の１以外の元であるｍ1，・・・,ｍk1とＧ1の１以外の元であるｍk1+1，・・・,ｍk2とからなるメッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)が入力され、
【００６４】
【数１４】
【００６５】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ,ｖ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)とともに送信する（Ｓ５）。メッセージｍの長さは、セキュリティパラメータk2に依存して決定され、短いメッセージに対しては明示的に１でパディングされるものとする。
【００６６】
検証装置１２０は、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ,ｖ)とメッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)を受信し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ｈv,ａ,ｇ1,・・・,ｇk1,ｈk1+1,・・・,ｈk2）を用いて、２つの検証式
【００６７】
【数１５】
【００６８】
の成否を計算し、共に成立すれば署名は正しく、改ざんされていないとの検証結果（例えばそれを意味する数値である１）を出力し、それ以外の場合は署名は正しくないとの検証結果（例えばそれを意味する数値である０）を出力する（Ｓ６）。
【００６９】
以上より、本発明によれば、群要素メッセージｍがＧ1、Ｇ2の両方にまたがるものである場合においても、実施例１と同様に、従来より効率的なディジタル署名方式を提供することができる。なお、実施例３においても実施例１と同様に、検証式で用いるペアリング演算ｅ(ａ,g2)について、予め署名装置１１０の鍵生成部１１４でＡ＝ｅ(ａ,g2)と計算しておき、このＡをａの代わりに公開鍵vkに含め、これをそのまま検証式で用いてもよい。
【００７０】
上記各実施例のディジタル署名・検証システムにおける各処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、本発明のディジタル署名・検証システムの各機能は必要に応じ、併合・分割しても構わない。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【００７１】
本発明のディジタル署名・検証システムの署名装置と検証装置をコンピュータによって実現する場合、装置及びその各部が有す機能の処理内容はプログラムによって記述される。そのプログラムは、例えば、ハードディスク装置に格納されており、実行時には必要なプログラムやデータがＲＡＭ(Random Access Memory)に読み込まれる。その読み込まれたプログラムがＣＰＵにより実行されることにより、コンピュータ上で各処理内容が実現される。なお、処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【特許請求の範囲】
【請求項１】
Ｇ1、Ｇ2をそれぞれ位数ｐの群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する生成元選択部と、
公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する公開情報生成部と、
１以上ｐ−１以下のランダムな整数δu、α、γz、δz、γi(ｉ＝１,・・・,ｋ、ｋは２以上の整数）、δi、ζ,ρ,及びτを生成する乱数生成部と、
【数１６】
を計算し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk,ｈ1,・・・,ｈk）及び秘密鍵sk＝(vk,α,γz,δz,δu,γ1,・・・,γk,δ1,・・・,δk)を生成し、公開鍵vkを公開する鍵生成部と、
Ｇ2の１以外の元であるメッセージｍ＝(ｍ1，・・・,ｍk)が入力され、
【数１７】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk)とともに送信する署名生成部と、
を備える署名装置と、
署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)とメッセージｍ＝(ｍ1，・・・,ｍk)を受信し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk,ｈ1,・・・,ｈk）を用いて、２つの検証式
【数１８】
の成否を計算し、共に成立すれば署名は正しいとの検証結果を出力し、それ以外の場合は署名は正しくないとの検証結果を出力する検証装置と、
を備えるディジタル署名・検証システム。
【請求項２】
Ｇ1、Ｇ2をそれぞれ位数ｐの異なる群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する生成元選択部と、
公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する公開情報生成部と、
１以上ｐ−１以下のランダムな整数δu、α、γz、γi(ｉ＝１,・・・,ｋ、ｋは２以上の整数）、ζ,ρ,及びτを生成する乱数生成部と、
【数１９】
を計算し、公開鍵vk＝(Λ,ｇz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk）及び秘密鍵sk＝(vk,α,γz,δu,γ1,・・・,γk)を生成し、公開鍵vkを公開する鍵生成部と、
Ｇ2の１以外の元であるメッセージｍ＝(ｍ1，・・・,ｍk)が入力され、
【数２０】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk)とともに送信する署名生成部と、
を備える署名装置と、
署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)とメッセージｍ＝(ｍ1，・・・,ｍk)を受信し、公開鍵vk＝(Λ,ｇz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk）を用いて、２つの検証式
【数２１】
の成否を計算し、共に成立すれば署名は正しいとの検証結果を出力し、それ以外の場合は署名は正しくないとの検証結果を出力する検証装置と、
を備えるディジタル署名・検証システム。
【請求項３】
Ｇ1、Ｇ2をそれぞれ位数ｐの異なる群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する生成元選択部と、
公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する公開情報生成部と、
１以上ｐ−１以下のランダムな整数δu、α、γz、δz、γi(ｉ＝１,・・・,k1、k1は２以上の整数）、δj(ｊ＝k1＋１,・・・,k2、k2はk1より大きい整数）、ζ,ρ,τ，及びωを生成する乱数生成部と、
【数２２】
を計算し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ｈv,ａ,ｇ1,・・・,ｇk1,ｈk1+1,・・・,ｈk2）及び秘密鍵sk＝(vk,α,γz,δz,δu,γ1,・・・,γk1,δk1+1,・・・,δk2)を生成し、公開鍵vkを公開する鍵生成部と、
Ｇ2の１以外の元であるｍ1，・・・,ｍk1とＧ1の１以外の元であるｍk1+1，・・・,ｍk2とからなるメッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)が入力され、
【数２３】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ,ｖ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)とともに送信する署名生成部と、
を備える署名装置と、
署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ,ｖ)とメッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)を受信し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ｈv,ａ,ｇ1,・・・,ｇk1,ｈk1+1,・・・,ｈk2）を用いて、２つの検証式
【数２４】
の成否を計算し、共に成立すれば署名は正しいとの検証結果を出力し、それ以外の場合は署名は正しくないとの検証結果を出力する検証装置と、
を備えるディジタル署名・検証システム。
【請求項４】
Ｇ1、Ｇ2をそれぞれ位数ｐの群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
署名装置の生成元選択部が、生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する生成元選択ステップと、
署名装置の公開情報生成部が、公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する公開情報生成ステップと、
署名装置の乱数生成部が、１以上ｐ−１以下のランダムな整数δu、α、γz、δz、γi(ｉ＝１,・・・,ｋ、ｋは２以上の整数）、δi、ζ,ρ,及びτを生成する乱数生成ステップと、
署名装置の鍵生成部が、
【数２５】
を計算し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk,ｈ1,・・・,ｈk）及び秘密鍵sk＝(vk,α,γz,δz,δu,γ1,・・・,γk,δ1,・・・,δk)を生成し、公開鍵vkを公開する鍵生成ステップと、
署名装置の署名生成部が、入力されたＧ2の１以外の元であるメッセージｍ＝(ｍ1，・・・,ｍk)を用いて、
【数２６】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk)とともに送信する署名生成ステップと、
検証装置が、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)とメッセージｍ＝(ｍ1，・・・,ｍk)を受信し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk,ｈ1,・・・,ｈk）を用いて、２つの検証式
【数２７】
の成否を計算し、共に成立すれば署名は正しいとの検証結果を出力し、それ以外の場合は署名は正しくないとの検証結果を出力する検証ステップと、
を実効するディジタル署名・検証方法。
【請求項５】
Ｇ1、Ｇ2をそれぞれ位数ｐの異なる群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
署名装置の生成元選択部が、生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する生成元選択ステップと、
署名装置の公開情報生成部が、公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する公開情報生成ステップと、
署名装置の乱数生成部が、１以上ｐ−１以下のランダムな整数δu、α、γz、γi(ｉ＝１,・・・,ｋ、ｋは２以上の整数）、ζ,ρ,及びτを生成する乱数生成ステップと、
署名装置の鍵生成部が、
【数２８】
を計算し、公開鍵vk＝(Λ,ｇz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk）及び秘密鍵sk＝(vk,α,γz,δu,γ1,・・・,γk)を生成し、公開鍵vkを公開する鍵生成ステップと、
署名装置の署名生成部が、入力されたＧ2の１以外の元であるメッセージｍ＝(ｍ1，・・・,ｍk)を用いて、
【数２９】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk)とともに送信する署名生成ステップと、
検証装置が、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)とメッセージｍ＝(ｍ1，・・・,ｍk)を受信し、公開鍵vk＝(Λ,ｇz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk）を用いて、２つの検証式
【数３０】
の成否を計算し、共に成立すれば署名は正しいとの検証結果を出力し、それ以外の場合は署名は正しくないとの検証結果を出力する検証ステップと、
を実行するディジタル署名・検証方法。
【請求項６】
Ｇ1、Ｇ2をそれぞれ位数ｐの異なる群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
署名装置の生成元選択部が、生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する生成元選択ステップと、
署名装置の公開情報生成部が、公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する公開情報生成ステップと、
署名装置の乱数生成部が、１以上ｐ−１以下のランダムな整数δu、α、γz、δz、γi(ｉ＝１,・・・,k1、k1は２以上の整数）、δj(ｊ＝k1＋１,・・・,k2、k2はk1より大きい整数）、ζ,ρ,τ，及びωを生成する乱数生成ステップと、
署名装置の鍵生成部が、
【数３１】
を計算し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ｈv,ａ,ｇ1,・・・,ｇk1,ｈk1+1,・・・,ｈk2）及び秘密鍵sk＝(vk,α,γz,δz,δu,γ1,・・・,γk1,δk1+1,・・・,δk2)を生成し、公開鍵vkを公開する鍵生成ステップと、
署名装置の署名生成部が、入力されたＧ2の１以外の元であるｍ1，・・・,ｍk1とＧ1の１以外の元であるｍk1+1，・・・,ｍk2とからなるメッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)を用いて、
【数３２】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ,ｖ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)とともに送信する署名生成ステップと、
検証装置が、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ,ｖ)とメッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)を受信し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ｈv,ａ,ｇ1,・・・,ｇk1,ｈk1+1,・・・,ｈk2）を用いて、２つの検証式
【数３３】
の成否を計算し、共に成立すれば署名は正しいとの検証結果を出力し、それ以外の場合は署名は正しくないとの検証結果を出力する検証ステップと、
を実行するディジタル署名・検証方法。
【請求項７】
Ｇ1、Ｇ2をそれぞれ位数ｐの群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する生成元選択部と、
公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する公開情報生成部と、
１以上ｐ−１以下のランダムな整数δu、α、γz、δz、γi(ｉ＝１,・・・,ｋ、ｋは２以上の整数）、δi、ζ,ρ,及びτを生成する乱数生成部と、
【数３４】
を計算し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk,ｈ1,・・・,ｈk）及び秘密鍵sk＝(vk,α,γz,δz,δu,γ1,・・・,γk,δ1,・・・,δk)を生成し、公開鍵vkを公開する鍵生成部と、
Ｇ2の１以外の元であるメッセージｍ＝(ｍ1，・・・,ｍk)が入力され、
【数３５】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk)とともに送信する署名生成部と、
を備える署名装置。
【請求項８】
Ｇ1、Ｇ2をそれぞれ位数ｐの異なる群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する生成元選択部と、
公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する公開情報生成部と、
１以上ｐ−１以下のランダムな整数δu、α、γz、γi(ｉ＝１,・・・,ｋ、ｋは２以上の整数）、ζ,ρ,及びτを生成する乱数生成部と、
【数３６】
を計算し、公開鍵vk＝(Λ,ｇz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk）及び秘密鍵sk＝(vk,α,γz,δu,γ1,・・・,γk)を生成し、公開鍵vkを公開する鍵生成部と、
Ｇ2の１以外の元であるメッセージｍ＝(ｍ1，・・・,ｍk)が入力され、
【数３７】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk)とともに送信する署名生成部と、
を備える署名装置。
【請求項９】
Ｇ1、Ｇ2をそれぞれ位数ｐの異なる群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する生成元選択部と、
公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する公開情報生成部と、
１以上ｐ−１以下のランダムな整数δu、α、γz、δz、γi(ｉ＝１,・・・,k1、k1は２以上の整数）、δj(ｊ＝k1＋１,・・・,k2、k2はk1より大きい整数）、ζ,ρ,τ，及びωを生成する乱数生成部と、
【数３８】
を計算し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ｈv,ａ,ｇ1,・・・,ｇk1,ｈk1+1,・・・,ｈk2）及び秘密鍵sk＝(vk,α,γz,δz,δu,γ1,・・・,γk1,δk1+1,・・・,δk2)を生成し、公開鍵vkを公開する鍵生成部と、
Ｇ2の１以外の元であるｍ1，・・・,ｍk1とＧ1の１以外の元であるｍk1+1，・・・,ｍk2とからなるメッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)が入力され、
【数３９】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ,ｖ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)とともに送信する署名生成部と、
を備える署名装置。
【請求項１０】
Ｇ1、Ｇ2をそれぞれ位数ｐの群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)とメッセージｍ＝(ｍ1，・・・,ｍk)を受信し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk,ｈ1,・・・,ｈk）を用いて、２つの検証式
【数４０】
の成否を計算し、共に成立すれば署名は正しいとの検証結果を出力し、それ以外の場合は署名は正しくないとの検証結果を出力する検証装置。
【請求項１１】
Ｇ1、Ｇ2をそれぞれ位数ｐの異なる群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)とメッセージｍ＝(ｍ1，・・・,ｍk)を受信し、公開鍵vk＝(Λ,ｇz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk）を用いて、２つの検証式
【数４１】
の成否を計算し、共に成立すれば署名は正いとの検証結果を出力し、それ以外の場合は署名は正しくないとの検証結果を出力する検証装置。
【請求項１２】
Ｇ1、Ｇ2をそれぞれ位数ｐの異なる群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ,ｖ)とメッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)を受信し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ｈv,ａ,ｇ1,・・・,ｇk1,ｈk1+1,・・・,ｈk2）を用いて、２つの検証式
【数４２】
の成否を計算し、共に成立すれば署名は正しいとの検証結果を出力し、それ以外の場合は署名は正しくないとの検証結果を出力する検証装置。
【請求項１３】
請求項７乃至９のいずれかに記載の署名装置又は請求項１０乃至１２のいずれかに記載の検証装置としてコンピュータを機能させるためのプログラム。
【請求項１】
Ｇ1、Ｇ2をそれぞれ位数ｐの群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する生成元選択部と、
公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する公開情報生成部と、
１以上ｐ−１以下のランダムな整数δu、α、γz、δz、γi(ｉ＝１,・・・,ｋ、ｋは２以上の整数）、δi、ζ,ρ,及びτを生成する乱数生成部と、
【数１６】
を計算し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk,ｈ1,・・・,ｈk）及び秘密鍵sk＝(vk,α,γz,δz,δu,γ1,・・・,γk,δ1,・・・,δk)を生成し、公開鍵vkを公開する鍵生成部と、
Ｇ2の１以外の元であるメッセージｍ＝(ｍ1，・・・,ｍk)が入力され、
【数１７】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk)とともに送信する署名生成部と、
を備える署名装置と、
署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)とメッセージｍ＝(ｍ1，・・・,ｍk)を受信し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk,ｈ1,・・・,ｈk）を用いて、２つの検証式
【数１８】
の成否を計算し、共に成立すれば署名は正しいとの検証結果を出力し、それ以外の場合は署名は正しくないとの検証結果を出力する検証装置と、
を備えるディジタル署名・検証システム。
【請求項２】
Ｇ1、Ｇ2をそれぞれ位数ｐの異なる群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する生成元選択部と、
公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する公開情報生成部と、
１以上ｐ−１以下のランダムな整数δu、α、γz、γi(ｉ＝１,・・・,ｋ、ｋは２以上の整数）、ζ,ρ,及びτを生成する乱数生成部と、
【数１９】
を計算し、公開鍵vk＝(Λ,ｇz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk）及び秘密鍵sk＝(vk,α,γz,δu,γ1,・・・,γk)を生成し、公開鍵vkを公開する鍵生成部と、
Ｇ2の１以外の元であるメッセージｍ＝(ｍ1，・・・,ｍk)が入力され、
【数２０】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk)とともに送信する署名生成部と、
を備える署名装置と、
署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)とメッセージｍ＝(ｍ1，・・・,ｍk)を受信し、公開鍵vk＝(Λ,ｇz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk）を用いて、２つの検証式
【数２１】
の成否を計算し、共に成立すれば署名は正しいとの検証結果を出力し、それ以外の場合は署名は正しくないとの検証結果を出力する検証装置と、
を備えるディジタル署名・検証システム。
【請求項３】
Ｇ1、Ｇ2をそれぞれ位数ｐの異なる群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する生成元選択部と、
公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する公開情報生成部と、
１以上ｐ−１以下のランダムな整数δu、α、γz、δz、γi(ｉ＝１,・・・,k1、k1は２以上の整数）、δj(ｊ＝k1＋１,・・・,k2、k2はk1より大きい整数）、ζ,ρ,τ，及びωを生成する乱数生成部と、
【数２２】
を計算し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ｈv,ａ,ｇ1,・・・,ｇk1,ｈk1+1,・・・,ｈk2）及び秘密鍵sk＝(vk,α,γz,δz,δu,γ1,・・・,γk1,δk1+1,・・・,δk2)を生成し、公開鍵vkを公開する鍵生成部と、
Ｇ2の１以外の元であるｍ1，・・・,ｍk1とＧ1の１以外の元であるｍk1+1，・・・,ｍk2とからなるメッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)が入力され、
【数２３】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ,ｖ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)とともに送信する署名生成部と、
を備える署名装置と、
署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ,ｖ)とメッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)を受信し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ｈv,ａ,ｇ1,・・・,ｇk1,ｈk1+1,・・・,ｈk2）を用いて、２つの検証式
【数２４】
の成否を計算し、共に成立すれば署名は正しいとの検証結果を出力し、それ以外の場合は署名は正しくないとの検証結果を出力する検証装置と、
を備えるディジタル署名・検証システム。
【請求項４】
Ｇ1、Ｇ2をそれぞれ位数ｐの群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
署名装置の生成元選択部が、生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する生成元選択ステップと、
署名装置の公開情報生成部が、公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する公開情報生成ステップと、
署名装置の乱数生成部が、１以上ｐ−１以下のランダムな整数δu、α、γz、δz、γi(ｉ＝１,・・・,ｋ、ｋは２以上の整数）、δi、ζ,ρ,及びτを生成する乱数生成ステップと、
署名装置の鍵生成部が、
【数２５】
を計算し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk,ｈ1,・・・,ｈk）及び秘密鍵sk＝(vk,α,γz,δz,δu,γ1,・・・,γk,δ1,・・・,δk)を生成し、公開鍵vkを公開する鍵生成ステップと、
署名装置の署名生成部が、入力されたＧ2の１以外の元であるメッセージｍ＝(ｍ1，・・・,ｍk)を用いて、
【数２６】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk)とともに送信する署名生成ステップと、
検証装置が、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)とメッセージｍ＝(ｍ1，・・・,ｍk)を受信し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk,ｈ1,・・・,ｈk）を用いて、２つの検証式
【数２７】
の成否を計算し、共に成立すれば署名は正しいとの検証結果を出力し、それ以外の場合は署名は正しくないとの検証結果を出力する検証ステップと、
を実効するディジタル署名・検証方法。
【請求項５】
Ｇ1、Ｇ2をそれぞれ位数ｐの異なる群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
署名装置の生成元選択部が、生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する生成元選択ステップと、
署名装置の公開情報生成部が、公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する公開情報生成ステップと、
署名装置の乱数生成部が、１以上ｐ−１以下のランダムな整数δu、α、γz、γi(ｉ＝１,・・・,ｋ、ｋは２以上の整数）、ζ,ρ,及びτを生成する乱数生成ステップと、
署名装置の鍵生成部が、
【数２８】
を計算し、公開鍵vk＝(Λ,ｇz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk）及び秘密鍵sk＝(vk,α,γz,δu,γ1,・・・,γk)を生成し、公開鍵vkを公開する鍵生成ステップと、
署名装置の署名生成部が、入力されたＧ2の１以外の元であるメッセージｍ＝(ｍ1，・・・,ｍk)を用いて、
【数２９】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk)とともに送信する署名生成ステップと、
検証装置が、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)とメッセージｍ＝(ｍ1，・・・,ｍk)を受信し、公開鍵vk＝(Λ,ｇz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk）を用いて、２つの検証式
【数３０】
の成否を計算し、共に成立すれば署名は正しいとの検証結果を出力し、それ以外の場合は署名は正しくないとの検証結果を出力する検証ステップと、
を実行するディジタル署名・検証方法。
【請求項６】
Ｇ1、Ｇ2をそれぞれ位数ｐの異なる群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
署名装置の生成元選択部が、生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する生成元選択ステップと、
署名装置の公開情報生成部が、公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する公開情報生成ステップと、
署名装置の乱数生成部が、１以上ｐ−１以下のランダムな整数δu、α、γz、δz、γi(ｉ＝１,・・・,k1、k1は２以上の整数）、δj(ｊ＝k1＋１,・・・,k2、k2はk1より大きい整数）、ζ,ρ,τ，及びωを生成する乱数生成ステップと、
署名装置の鍵生成部が、
【数３１】
を計算し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ｈv,ａ,ｇ1,・・・,ｇk1,ｈk1+1,・・・,ｈk2）及び秘密鍵sk＝(vk,α,γz,δz,δu,γ1,・・・,γk1,δk1+1,・・・,δk2)を生成し、公開鍵vkを公開する鍵生成ステップと、
署名装置の署名生成部が、入力されたＧ2の１以外の元であるｍ1，・・・,ｍk1とＧ1の１以外の元であるｍk1+1，・・・,ｍk2とからなるメッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)を用いて、
【数３２】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ,ｖ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)とともに送信する署名生成ステップと、
検証装置が、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ,ｖ)とメッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)を受信し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ｈv,ａ,ｇ1,・・・,ｇk1,ｈk1+1,・・・,ｈk2）を用いて、２つの検証式
【数３３】
の成否を計算し、共に成立すれば署名は正しいとの検証結果を出力し、それ以外の場合は署名は正しくないとの検証結果を出力する検証ステップと、
を実行するディジタル署名・検証方法。
【請求項７】
Ｇ1、Ｇ2をそれぞれ位数ｐの群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する生成元選択部と、
公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する公開情報生成部と、
１以上ｐ−１以下のランダムな整数δu、α、γz、δz、γi(ｉ＝１,・・・,ｋ、ｋは２以上の整数）、δi、ζ,ρ,及びτを生成する乱数生成部と、
【数３４】
を計算し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk,ｈ1,・・・,ｈk）及び秘密鍵sk＝(vk,α,γz,δz,δu,γ1,・・・,γk,δ1,・・・,δk)を生成し、公開鍵vkを公開する鍵生成部と、
Ｇ2の１以外の元であるメッセージｍ＝(ｍ1，・・・,ｍk)が入力され、
【数３５】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk)とともに送信する署名生成部と、
を備える署名装置。
【請求項８】
Ｇ1、Ｇ2をそれぞれ位数ｐの異なる群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する生成元選択部と、
公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する公開情報生成部と、
１以上ｐ−１以下のランダムな整数δu、α、γz、γi(ｉ＝１,・・・,ｋ、ｋは２以上の整数）、ζ,ρ,及びτを生成する乱数生成部と、
【数３６】
を計算し、公開鍵vk＝(Λ,ｇz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk）及び秘密鍵sk＝(vk,α,γz,δu,γ1,・・・,γk)を生成し、公開鍵vkを公開する鍵生成部と、
Ｇ2の１以外の元であるメッセージｍ＝(ｍ1，・・・,ｍk)が入力され、
【数３７】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk)とともに送信する署名生成部と、
を備える署名装置。
【請求項９】
Ｇ1、Ｇ2をそれぞれ位数ｐの異なる群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する生成元選択部と、
公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する公開情報生成部と、
１以上ｐ−１以下のランダムな整数δu、α、γz、δz、γi(ｉ＝１,・・・,k1、k1は２以上の整数）、δj(ｊ＝k1＋１,・・・,k2、k2はk1より大きい整数）、ζ,ρ,τ，及びωを生成する乱数生成部と、
【数３８】
を計算し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ｈv,ａ,ｇ1,・・・,ｇk1,ｈk1+1,・・・,ｈk2）及び秘密鍵sk＝(vk,α,γz,δz,δu,γ1,・・・,γk1,δk1+1,・・・,δk2)を生成し、公開鍵vkを公開する鍵生成部と、
Ｇ2の１以外の元であるｍ1，・・・,ｍk1とＧ1の１以外の元であるｍk1+1，・・・,ｍk2とからなるメッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)が入力され、
【数３９】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ,ｖ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)とともに送信する署名生成部と、
を備える署名装置。
【請求項１０】
Ｇ1、Ｇ2をそれぞれ位数ｐの群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)とメッセージｍ＝(ｍ1，・・・,ｍk)を受信し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk,ｈ1,・・・,ｈk）を用いて、２つの検証式
【数４０】
の成否を計算し、共に成立すれば署名は正しいとの検証結果を出力し、それ以外の場合は署名は正しくないとの検証結果を出力する検証装置。
【請求項１１】
Ｇ1、Ｇ2をそれぞれ位数ｐの異なる群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)とメッセージｍ＝(ｍ1，・・・,ｍk)を受信し、公開鍵vk＝(Λ,ｇz,ｇr,ｈu,ａ,ｇ1,・・・,ｇk）を用いて、２つの検証式
【数４１】
の成否を計算し、共に成立すれば署名は正いとの検証結果を出力し、それ以外の場合は署名は正しくないとの検証結果を出力する検証装置。
【請求項１２】
Ｇ1、Ｇ2をそれぞれ位数ｐの異なる群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ,ｖ)とメッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)を受信し、公開鍵vk＝(Λ,ｇz,ｈz,ｇr,ｈu,ｈv,ａ,ｇ1,・・・,ｇk1,ｈk1+1,・・・,ｈk2）を用いて、２つの検証式
【数４２】
の成否を計算し、共に成立すれば署名は正しいとの検証結果を出力し、それ以外の場合は署名は正しくないとの検証結果を出力する検証装置。
【請求項１３】
請求項７乃至９のいずれかに記載の署名装置又は請求項１０乃至１２のいずれかに記載の検証装置としてコンピュータを機能させるためのプログラム。
【図１】
【図２】
【図２】
【公開番号】特開２０１２−９０１８１（Ｐ２０１２−９０１８１Ａ）
【公開日】平成２４年５月１０日（２０１２．５．１０）
【国際特許分類】
【出願番号】特願２０１０−２３６８０９（Ｐ２０１０−２３６８０９）
【出願日】平成２２年１０月２１日（２０１０．１０．２１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年５月１０日（２０１２．５．１０）
【国際特許分類】
【出願日】平成２２年１０月２１日（２０１０．１０．２１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]