(57)【特許請求の範囲】
【請求項１】
Ｇ1、Ｇ2をそれぞれ位数ｐの群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する生成元選択部と、
公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する公開情報生成部と、
１以上ｐ−１以下のランダムな整数δu、α、γz、δz、δs、δt、γi(ｉ＝１,・・・,ｋ、ｋは２以上の整数）、δi、ζ,ρ,及びτを生成する乱数生成部と、
【数１３】
0005457991.tif 000014
を計算し、公開鍵vk＝(Λ,ａ,ｇz,ｇr,ｇ1,・・・,ｇk,ｈz,ｈu,ｈt,ｈs,ｈ1,・・・,ｈk）及び秘密鍵sk＝(γz,α,γ1,・・・,γk,δz,δu,δs,δt,δ1,・・・,δk)を生成し、公開鍵vkを公開する鍵生成部と、
Ｇ2の１以外の元であるメッセージｍ＝(ｍ1，・・・,ｍk)が入力され、
【数１４】
0005457991.tif 000015
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk)とともに送信する署名生成部と、
を備える署名装置と、
署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)とメッセージｍ＝(ｍ1，・・・,ｍk)を受信し、公開鍵vk＝(Λ,ａ,ｇz,ｇr,ｇ1,・・・,ｇk,ｈz,ｈu,ｈt,ｈs,ｈ1,・・・,ｈk）を用いて、２つの検証式
【数１５】
0005457991.tif 000016
の成否を計算し、共に成立すれば署名は正しいとの検証結果を出力し、それ以外の場合は署名は正しくないとの検証結果を出力する検証装置と、
を備えるディジタル署名・検証システム。
【請求項２】
Ｇ1、Ｇ2をそれぞれ位数ｐの異なる群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する生成元選択部と、
公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する公開情報生成部と、
１以上ｐ−１以下のランダムな整数δu、δv、α、γz、δs、δt、γi(ｉ＝１,・・・,k1、k1は２以上の整数）、δj(ｊ＝k1＋１,・・・,k2、k2はk1より大きい整数）、ζ,ρ,τ，及びωを生成する乱数生成部と、
【数１６】
0005457991.tif 000017
を計算し、公開鍵vk＝(Λ,ｇz,ｇr,ｈu,ｈv,ｈs,ｈt,ａ,ｇ1,・・・,ｇk1,ｈk1+1,・・・,ｈk2）及び秘密鍵sk＝(vk,α,γz,δu,δv,δs,δt,γ1,・・・,γk1,δk1+1,・・・,δk2)を生成し、公開鍵vkを公開する鍵生成部と、
Ｇ2の１以外の元であるｍ1，・・・,ｍk1とＧ1の１以外の元であるｍk1+1，・・・,ｍk2とからなるメッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)が入力され、
【数１７】
0005457991.tif 000018
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ,ｖ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)とともに送信する署名生成部と、
を備える署名装置と、
署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ，ｖ)とメッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)を受信し、公開鍵vk＝(Λ,ｇz,ｇr,ｈu,ｈv,ｈs,ｈt,ａ,ｇ1,・・・,ｇk1,ｈk1+1,・・・,ｈk2）を用いて、２つの検証式
【数１８】
0005457991.tif 000019
の成否を計算し、共に成立すれば署名は正しいとの検証結果を出力し、それ以外の場合は署名は正しくないとの検証結果を出力する検証装置と、
を備えるディジタル署名・検証システム。
【請求項３】
Ｇ1、Ｇ2をそれぞれ位数ｐの群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
署名装置の生成元選択部が、生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する生成元選択ステップと、
署名装置の公開情報生成部が、公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する公開情報生成ステップと、
署名装置の乱数生成部が、１以上ｐ−１以下のランダムな整数δu、α、γz、δz、δs、δt、γi(ｉ＝１,・・・,ｋ、ｋは２以上の整数）、δi、ζ,ρ,及びτを生成する乱数生成ステップと、
署名装置の鍵生成部が、
【数１９】
0005457991.tif 000020
を計算し、公開鍵vk＝(Λ,ａ,ｇz,ｇr,ｇ1,・・・,ｇk,ｈz,ｈu,ｈt,ｈs,ｈ1,・・・,ｈk）及び秘密鍵sk＝(γz,α,γ1,・・・,γk,δz,δu,δs,δt,δ1,・・・,δk)を生成し、公開鍵vkを公開する鍵生成ステップと、
署名装置の署名生成部が、Ｇ2の１以外の元であるメッセージｍ＝(ｍ1，・・・,ｍk)が入力され、
【数２０】
0005457991.tif 000021
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk)とともに送信する署名生成ステップと、
検証装置が、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)とメッセージｍ＝(ｍ1，・・・,ｍk)を受信し、公開鍵vk＝(Λ,ａ,ｇz,ｇr,ｇ1,・・・,ｇk,ｈz,ｈu,ｈt,ｈs,ｈ1,・・・,ｈk）を用いて、２つの検証式
【数２１】
0005457991.tif 000022
の成否を計算し、共に成立すれば署名は正しいとの検証結果を出力し、それ以外の場合は署名は正しくないとの検証結果を出力する検証ステップと、
を実行するディジタル署名・検証方法。
【請求項４】
Ｇ1、Ｇ2をそれぞれ位数ｐの異なる群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
署名装置の生成元選択部が、生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する生成元選択ステップと、
署名装置の公開情報生成部が、公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する公開情報生成ステップと、
署名装置の乱数生成部が、１以上ｐ−１以下のランダムな整数δu、δv、α、γz、δs、δt、γi(ｉ＝１,・・・,k1、k1は２以上の整数）、δj(ｊ＝k1＋１,・・・,k2、k2はk1より大きい整数）、ζ,ρ,τ，及びωを生成する乱数生成ステップと、
署名装置の鍵生成部が、
【数２２】
0005457991.tif 000023
を計算し、公開鍵vk＝(Λ,ｇz,ｇr,ｈu,ｈv,ｈs,ｈt,ａ,ｇ1,・・・,ｇk1,ｈk1+1,・・・,ｈk2）及び秘密鍵sk＝(vk,α,γz,δu,δv,δs,δt,γ1,・・・,γk1,δk1+1,・・・,δk2)を生成し、公開鍵vkを公開する鍵生成ステップと、
署名装置の署名生成部が、Ｇ2の１以外の元であるｍ1，・・・,ｍk1とＧ1の１以外の元であるｍk1+1，・・・,ｍk2とからなるメッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)が入力され、
【数２３】
0005457991.tif 000024
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ,ｖ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)とともに送信する署名生成ステップと、
検証装置が、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ，ｖ)とメッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)を受信し、公開鍵vk＝(Λ,ｇz,ｇr,ｈu,ｈv,ｈs,ｈt,ａ,ｇ1,・・・,ｇk1,ｈk1+1,・・・,ｈk2）を用いて、２つの検証式
【数２４】
0005457991.tif 000025
の成否を計算し、共に成立すれば署名は正しいとの検証結果を出力し、それ以外の場合は署名は正しくないとの検証結果を出力する検証ステップと、
を実行するディジタル署名・検証方法。
【請求項５】
Ｇ1、Ｇ2をそれぞれ位数ｐの群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する生成元選択部と、
公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する公開情報生成部と、
１以上ｐ−１以下のランダムな整数δu、α、γz、δz、δs、δt、γi(ｉ＝１,・・・,ｋ、ｋは２以上の整数）、δi、ζ,ρ,及びτを生成する乱数生成部と、
【数２５】
0005457991.tif 000026
を計算し、公開鍵vk＝(Λ,ａ,ｇz,ｇr,ｇ1,・・・,ｇk,ｈz,ｈu,ｈt,ｈs,ｈ1,・・・,ｈk）及び秘密鍵sk＝(γz,α,γ1,・・・,γk,δz,δu,δs,δt,δ1,・・・,δk)を生成し、公開鍵vkを公開する鍵生成部と、
Ｇ2の１以外の元であるメッセージｍ＝(ｍ1，・・・,ｍk)が入力され、
【数２６】
0005457991.tif 000027
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk)とともに送信する署名生成部と、
を備える署名装置。
【請求項６】
Ｇ1、Ｇ2をそれぞれ位数ｐの異なる群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する生成元選択部と、
公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する公開情報生成部と、
１以上ｐ−１以下のランダムな整数δu、δv、α、γz、δs、δt、γi(ｉ＝１,・・・,k1、k1は２以上の整数）、δj(ｊ＝k1＋１,・・・,k2、k2はk1より大きい整数）、ζ,ρ,τ，及びωを生成する乱数生成部と、
【数２７】
0005457991.tif 000028
を計算し、公開鍵vk＝(Λ,ｇz,ｇr,ｈu,ｈv,ｈs,ｈt,ａ,ｇ1,・・・,ｇk1,ｈk1+1,・・・,ｈk2）及び秘密鍵sk＝(vk,α,γz,δu,δv,δs,δt,γ1,・・・,γk1,δk1+1,・・・,δk2)を生成し、公開鍵vkを公開する鍵生成部と、
Ｇ2の１以外の元であるｍ1，・・・,ｍk1とＧ1の１以外の元であるｍk1+1，・・・,ｍk2とからなるメッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)が入力され、
【数２８】
0005457991.tif 000029
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ,ｖ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)とともに送信する署名生成部と、
を備える署名装置。
【請求項７】
Ｇ1、Ｇ2をそれぞれ位数ｐの群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)とメッセージｍ＝(ｍ1，・・・,ｍk)を受信し、公開鍵vk＝(Λ,ａ,ｇz,ｇr,ｇ1,・・・,ｇk,ｈz,ｈu,ｈt,ｈs,ｈ1,・・・,ｈk）を用いて、２つの検証式
【数２９】
0005457991.tif 000030
の成否を計算し、共に成立すれば署名は正しいとの検証結果を出力し、それ以外の場合は署名は正しくないとの検証結果を出力する検証装置。
【請求項８】
Ｇ1、Ｇ2をそれぞれ位数ｐの異なる群（ｐは素数）、バイリニアマップｅをｅ：Ｇ1×Ｇ2→ＧTとし、
署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ，ｖ)とメッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)を受信し、公開鍵vk＝(Λ,ｇz,ｇr,ｈu,ｈv,ｈs,ｈt,ａ,ｇ1,・・・,ｇk1,ｈk1+1,・・・,ｈk2）を用いて、２つの検証式
【数３０】
0005457991.tif 000031
の成否を計算し、共に成立すれば署名は正しいとの検証結果を出力し、それ以外の場合は署名は正しくないとの検証結果を出力する検証装置。
【請求項９】
請求項５若しくは６に記載の署名装置又は請求項７若しくは８に記載の検証装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電気通信システムに関し、強偽造不可能性を持つ安全なディジタル署名・検証システム、ディジタル署名・検証方法、署名装置、検証装置、及びそれらのプログラムに関する。
【背景技術】
【０００２】
ディジタル署名はメッセージｍに対して、公開鍵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を計算し、更に、
【００１６】
【数１】
0005457991.tif 000002
【００１７】
を計算して、公開鍵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)が入力され、
【００１９】
【数２】
0005457991.tif 000003
【００２０】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ,ｖ,ｗ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk)とともに送信する（Ｓ５）。メッセージｍの長さは、セキュリティパラメータｋに依存して決定され、短いメッセージに対しては明示的に１でパディングされるものとする。
【００２１】
検証装置１２０は、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ,ｖ,ｗ)とメッセージｍ＝(ｍ1，・・・,ｍk)を受信し、公開鍵vk＝(ｇz,ｈz,ｇr,ｈu,ｇ1,・・・,ｇk,ｈ1,・・・,ｈk,ａ00,ａ01,ａ10,ａ11,ｂ00,ｂ01,ｂ10,ｂ11）を用いて、２つの検証式
【００２２】
【数３】
0005457991.tif 000004
【００２３】
の成否を計算し、共に成立すれば署名は正しく、改ざんされていないとの検証結果（例えばそれを意味する数値である１）を出力し、それ以外の場合は署名は正しくないとの検証結果（例えばそれを意味する数値である０）を出力する（Ｓ６）。
【先行技術文献】
【非特許文献】
【００２４】
【非特許文献１】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>
【発明の概要】
【発明が解決しようとする課題】
【００２５】
従来技術（ＡＨＯ方式）では、署名が群の要素７つからなり、また、検証においては１０＋２ｋ個のペアリング演算を要するため、署名長、演算量共に多い。また、あるメッセージに対する署名を入手すると、同じメッセージに対して別の署名を作り出すことが容易である。例えば、上記の検証式には署名要素ｓ，ｔのみからなるペアリング演算ｅ(ｓ,ｔ)が含まれており、この演算に対し攻撃者がｓ,ｔの両方を操作できる。そのため、攻撃者が一旦メッセージｍに対する署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ,ｖ,ｗ)を入手すると、例えば偽造署名σ'＝(ｚ,ｒ,ｓk,ｔ1/k,ｕ,ｖ,ｗ)を得ることができてしまう。この場合、ｅ(ｓ,ｔ)＝ｅ(ｓk,ｔ1/k)である結果、σ'も検証に合格してしまうため、ｍに対する正しい署名ということになる。すなわち、安全性のレベルについて、通常の偽造不可能性（existential unforgeability：新たなメッセージに対する署名を偽造できない）までしか満たすことができず、強偽造不可能性（strongly existential unforgeability：同一メッセージに対しても異なる署名を生成できない）はない。
【００２６】
本発明の目的は、群要素メッセージに対するディジタル署名・検証方式において、従来より公開鍵、署名の長さが短く、検証式の計算量が少なく、高い安全性が証明可能であり、かつ、強偽造不可能なディジタル署名・検証システム、ディジタル署名・検証方法、署名装置、検証装置、及びそのプログラムを提供することにある。
【課題を解決するための手段】
【００２７】
本発明のディジタル署名・検証システムは、署名装置と検証装置とからなる。  署名装置は、生成元選択部と公開情報生成部と乱数生成部と鍵生成部と署名生成部とを備える。
【００２８】
生成元選択部は、Ｇ1、Ｇ2がそれぞれ位数ｐの群（ｐは素数）であるとして、生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する。
【００２９】
公開情報生成部は、公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する。ここで、ｅはバイリニアマップであり、ｅ：Ｇ1×Ｇ2→ＧTである。
【００３０】
乱数生成部は、１以上ｐ−１以下のランダムな整数δu、α、γz、δz、δs、δt、γi(ｉ＝１,・・・,ｋ、ｋは２以上の整数）、δi、ζ,ρ,及びτを生成する。
【００３１】
鍵生成部は、
【００３２】
【数４】
0005457991.tif 000005
【００３３】
を計算し、公開鍵vk＝(Λ,ａ,ｇz,ｇr,ｇ1,・・・,ｇk,ｈz,ｈu,ｈt,ｈs,ｈ1,・・・,ｈk）及び秘密鍵sk＝(γz,α,γ1,・・・,γk,δz,δu,δs,δt,δ1,・・・,δk)を生成し、公開鍵vkを公開する。
【００３４】
署名生成部は、Ｇ2の１以外の元であるメッセージｍ＝(ｍ1，・・・,ｍk)が入力され、
【００３５】
【数５】
0005457991.tif 000006
【００３６】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk)とともに送信する。
【００３７】
検証装置は、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)とメッセージｍ＝(ｍ1，・・・,ｍk)を受信し、公開鍵vk＝(Λ,ａ,ｇz,ｇr,ｇ1,・・・,ｇk,ｈz,ｈu,ｈt,ｈs,ｈ1,・・・,ｈk）を用いて、２つの検証式
【００３８】
【数６】
0005457991.tif 000007
【００３９】
の成否を計算し、共に成立すれば署名は正しいとの検証結果を出力し、それ以外の場合は署名は正しくないとの検証結果を出力する。
【発明の効果】
【００４０】
本発明の本発明のディジタル署名・検証システム、ディジタル署名・検証方法、署名装置、検証装置、及びそのプログラムによれば、群要素メッセージに対するディジタル署名・検証方式について、従来より公開鍵、署名の長さが短く、検証式の計算量が少なく、高い安全性が証明可能であり、かつ強偽造不可能なディジタル署名・検証方式を提供することができる。
【図面の簡単な説明】
【００４１】
【図１】本発明のディジタル署名・検証システムの機能構成例を示す図。
【図２】本発明のディジタル署名・検証システムの処理フロー例を示す図。
【発明を実施するための形態】
【００４２】
以下、本発明の実施の形態について、詳細に説明する。
【実施例１】
【００４３】
本発明の特徴は、従来技術（ＡＨＯ方式）における２つの検証式において、両方の式で共通して使用される署名要素の個数が多くなるように、かつ、一方の検証式が署名要素のみからなるペアリングを持つときに他方の式でそれらの要素を別々のペアリング演算に入力するように、検証式を構成する点にある。共通して使用される署名要素の個数が増えることで、攻撃者が署名要素の一部を改ざんしても、両方の検証式を同時に満たすことが一層困難になるため、署名の偽造に対する安全性を損なうことなく、検証式の一方から公開鍵の一部を除去して検証式を簡略化することが可能となる。そして、検証式の簡略化により、公開鍵、署名ともに不必要な要素を除去することができ、従来より公開鍵、署名の長さを短くすることができる。また、一方の検証式が署名要素のみからなるペアリングを持つときに、他方の式でそれらの要素を別々のペアリング演算に入力するように検証式を構成することで、一方の検証式において署名要素のみからなるペアリングに入力されていた署名要素が乱数成分によりランダム化され、他方の検証式が満たされなくなる。これにより、強偽造不可能性が提供される。
【００４４】
以下、具体的な構成例について説明する。
【００４５】
図１に本発明のディジタル署名・検証システム１００の機能構成例を、図２にその処理フロー例（Ｓ１〜６）をそれぞれ示す。
【００４６】
本発明のディジタル署名・検証システム１００は、署名装置１１０と検証装置１２０とからなる。署名装置１１０と検証装置１２０との間は、任意のネットワーク５０で結ばれる。
【００４７】
署名装置１１０は、生成元選択部１１１と公開情報生成部１１２と乱数生成部１１３と鍵生成部１１４と署名生成部１１５とを備える。
【００４８】
生成元選択部１１１は、Ｇ1、Ｇ2がそれぞれ位数ｐの群（ｐは素数）であるとして、生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する（Ｓ１）。なお、Ｇ1とＧ2は同一の群でも異なる群でも構わない。
【００４９】
公開情報生成部１１２は、公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する（Ｓ２）。ここで、ｅはバイリニアマップであり、ｅ：Ｇ1×Ｇ2→ＧTである。
【００５０】
乱数生成部１１３は、１以上ｐ−１以下のランダムな整数δu、α、γz、δz、δs、δt、γi(ｉ＝１,・・・,ｋ、ｋはセキュリティパラメータで２以上の整数）、δi、ζ,ρ,及びτを生成する（Ｓ３）。
【００５１】
鍵生成部１１４は、
【００５２】
【数７】
0005457991.tif 000008
【００５３】
を計算し、公開鍵vk＝(Λ,ａ,ｇz,ｇr,ｇ1,・・・,ｇk,ｈz,ｈu,ｈt,ｈs,ｈ1,・・・,ｈk）及び秘密鍵sk＝(γz,α,γ1,・・・,γk,δz,δu,δs,δt,δ1,・・・,δk)を生成し、公開鍵vkを公開する（Ｓ４）。なお、秘密鍵skは署名装置内に安全に格納される。
【００５４】
署名生成部１１５は、Ｇ2の１以外の元であるメッセージｍ＝(ｍ1，・・・,ｍk)が入力され、
【００５５】
【数８】
0005457991.tif 000009
【００５６】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk)とともに送信する（Ｓ５）。メッセージｍの長さは、セキュリティパラメータｋに依存して決定され、短いメッセージに対しては明示的に１でパディングされるものとする。
【００５７】
検証装置１２０は、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ)とメッセージｍ＝(ｍ1，・・・,ｍk)を受信し、公開鍵vk＝(Λ,ａ,ｇz,ｇr,ｇ1,・・・,ｇk,ｈz,ｈu,ｈt,ｈs,ｈ1,・・・,ｈk）を用いて、２つの検証式
【００５８】
【数９】
0005457991.tif 000010
【００５９】
の成否を計算し、共に成立すれば署名は正しく、改ざんされていないとの検証結果（例えばそれを意味する数値である１）を出力し、それ以外の場合は署名は正しくないとの検証結果（例えばそれを意味する数値である０）を出力する（Ｓ６）。
【００６０】
以上のように、本発明においては、２つの検証式で共通して使用される署名要素を増やし、かつ、一方の検証式が署名要素のみからなるペアリングを持つときに、他方の式でそれらの要素を別々のペアリング演算に入力するように検証式を構成する。
【００６１】
これにより、攻撃者が署名要素の一部を改ざんしても両方の検証式を同時に満たすことが一層困難となり、署名の偽造に対する安全性を損なうことなく、検証式の一方から公開鍵の一部を除去して検証式を簡略化できる。そして、この簡略化により、公開鍵、署名ともに不必要な要素を除去することができ、署名の群要素の数を７個から５個に、検証時のペアリング演算の個数を１０＋２ｋ個から８＋２ｋ個に減らすことができる。これにより、従来より公開鍵、署名の長さが短く、検証式の計算量が少なく、かつ、高い安全性が証明可能な、効率のよい署名方式を提供することができる。具体的には、署名長が短くなることで、通信帯域及びメモリを削減することができ、検証の計算量が少ないことにより、高速な署名検証が可能となる。
【００６２】
また、一方の検証式が署名要素のみからなるペアリング演算ｅ(ｓ,ｔ)を含んでいるが、他方の検証式でそれらの要素を別々のペアリング演算ｅ(ｓ,ｈs)、ｅ(ｈt,ｔ)に入力するように検証式を構成することで、一方の検証式において署名要素のみからなるペアリング演算ｅ(ｓ,ｔ)に入力されていた署名要素ｓ,ｔが乱数成分によりランダム化され、他方の検証式が満たされなくなる。更に、ｈsとｈtは既に生成された公開鍵を構成する値であるため、ｅ(ｓ,ｈs)やｅ(ｈt,ｔ)を偽造することはより困難になる。以上により、強偽造不可能性が提供される。
【００６３】
なお、検証式で用いるペアリング演算ｅ(ａ,g2)について、予め署名装置１１０の鍵生成部１１４でＡ＝ｅ(ａ,g2)と計算しておき、このＡをａの代わりに公開鍵vkに含め、これをそのまま検証式で用いてもよい。このように構成することで、検証時に行うペアリング演算をさらに１個減らすことができる。ただし、この場合、ａよりもＡの方が表現が長いため、公開鍵vkの長さが長くなる。また、この署名をゼロ知識証明と組み合わせる場合、検証式はＧ1、Ｇ2の要素のみから成り立っていることが望ましいため、Ａを直接検証式に使うことができず、ｅ(ａ,g2)のようにａとg2とをバラにして提供する必要が生じる。もっとも、ゼロ知識証明よりもやや弱い証明系であるWitness-Indistinguishable証明を組み合わせる場合には、検証式にＧTの要素が入っていても構わないため、その場合にはＡのまま利用が可能である。従って、公開鍵としてａを含めるかＡを含めるかは、ユーザが本発明の署名方式をどのように使いたいかにより任意に選択すればよい。
【実施例２】
【００６４】
実施例１は、群要素メッセージｍがＧ2に属する要素のみから成るものに対して適用可能な構成である。一方、実施例２は、群要素メッセージｍがＧ1、Ｇ2の両方にまたがるものであっても適用可能な構成である。
【００６５】
以下、具体的な構成例について説明する。
【００６６】
図１に本発明のディジタル署名・検証システム１００' の機能構成例を、図２にその処理フロー例（Ｓ１〜６）をそれぞれ示す。
【００６７】
本発明のディジタル署名・検証システム１００' は、署名装置１１０と検証装置１２０とからなる。署名装置１１０と検証装置１２０との間は、任意のネットワーク５０で結ばれる。
【００６８】
署名装置１１０は、生成元選択部１１１と公開情報生成部１１２と乱数生成部１１３と鍵生成部１１４と署名生成部１１５とを備える。
【００６９】
生成元選択部１１１は、Ｇ1、Ｇ2がそれぞれ位数ｐ（ｐは素数）の異なる群であるとして、生成元g1をＧ1から、g2をＧ2から、それぞれランダムに選択する（Ｓ１）。
【００７０】
公開情報生成部１１２は、公開情報Λ＝（ｐ,Ｇ1,Ｇ2,ＧT,ｅ,g1,g2）を生成する（Ｓ２）。ここで、ｅはバイリニアマップであり、ｅ：Ｇ1×Ｇ2→ＧTである。
【００７１】
乱数生成部１１３は、１以上ｐ−１以下のランダムな整数δu、δv、α、γz、δs、δt、γi(ｉ＝１,・・・,k1、k1は２以上の整数）、δj(ｊ＝k1＋１,・・・,k2、k2はセキュリティパラメータでk1より大きい整数）、ζ,ρ,τ，及びωを生成する（Ｓ３）。
【００７２】
鍵生成部１１４は、
【００７３】
【数１０】
0005457991.tif 000011
【００７４】
を計算し、公開鍵vk＝(Λ,ｇz,ｇr,ｈu,ｈv,ｈs,ｈt,ａ,ｇ1,・・・,ｇk1,ｈk1+1,・・・,ｈk2）及び秘密鍵sk＝(vk,α,γz,δu,δv,δs,δt,γ1,・・・,γk1,δk1+1,・・・,δk2)を生成し、公開鍵vkを公開する（Ｓ４）。なお、秘密鍵skは署名装置内に安全に格納される。
【００７５】
署名生成部１１５は、Ｇ2の１以外の元であるｍ1，・・・,ｍk1とＧ1の１以外の元であるｍk1+1，・・・,ｍk2とからなるメッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)が入力され、
【００７６】
【数１１】
0005457991.tif 000012
【００７７】
を計算して、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ,ｖ)を生成し、メッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)とともに送信する（Ｓ５）。メッセージｍの長さは、セキュリティパラメータk2に依存して決定され、短いメッセージに対しては明示的に１でパディングされるものとする。
【００７８】
検証装置１２０は、署名σ＝(ｚ,ｒ,ｓ,ｔ,ｕ，ｖ)とメッセージｍ＝(ｍ1，・・・,ｍk1,ｍk1+1，・・・,ｍk2)を受信し、公開鍵vk＝(Λ,ｇz,ｇr,ｈu,ｈv,ｈs,ｈt,ａ,ｇ1,・・・,ｇk1,ｈk1+1,・・・,ｈk2）を用いて、２つの検証式
【００７９】
【数１２】
0005457991.tif 000013
【００８０】
の成否を計算し、共に成立すれば署名は正しく、改ざんされていないとの検証結果（例えばそれを意味する数値である１）を出力し、それ以外の場合は署名は正しくないとの検証結果（例えばそれを意味する数値である０）を出力する（Ｓ６）。
【００８１】
以上より、本発明によれば、群要素メッセージｍがＧ1、Ｇ2の両方にまたがるものである場合においても、実施例１と同様に、従来より効率的なディジタル署名方式を提供することができる。なお、実施例２においても実施例１と同様に、検証式で用いるペアリング演算ｅ(ａ,g2)について、予め署名装置１１０の鍵生成部１１４でＡ＝ｅ(ａ,g2)と計算しておき、このＡをａの代わりに公開鍵vkに含め、これをそのまま検証式で用いてもよい。
【００８２】
上記各実施例のディジタル署名・検証システムにおける各処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、本発明のディジタル署名・検証システムの各機能は必要に応じ、併合・分割しても構わない。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【００８３】
本発明のディジタル署名・検証システムの署名装置及び検証装置をコンピュータによって実現する場合、装置及びその各部が有す機能の処理内容はプログラムによって記述される。そのプログラムは、例えば、ハードディスク装置に格納されており、実行時には必要なプログラムやデータがＲＡＭ(Random Access Memory)に読み込まれる。その読み込まれたプログラムがＣＰＵにより実行されることにより、コンピュータ上で各処理内容が実現される。なお、処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
0005457991.tif 000032
【図２】
0005457991.tif 000033