電子署名検証システム、電子署名装置、検証装置、電子署名検証方法、電子署名方法、検証方法、電子署名プログラム、検証プログラム
【課題】本発明は、電子署名を構成する要素の数を少なくし、電子署名長が短く、情報量及び通信量が少なく、また、検証時の計算量の少ない電子署名検証方法及び装置を提供することを目的とする。
【解決手段】ｑを素数とし、Ｇ1，Ｇ2，ＧTを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ1×Ｇ2→ＧTとし、電子署名装置は、乱数ｘ及びｙとＧ1及びＧ2それぞれの生成元ｇ1及びｇ2を用いて、Ｘ'＝ｇ2x、Ｙ'＝ｇ2y、Ｙ＝ｇ1yを計算し、公開鍵pkを生成する。ｇ1、ｇ2、乱数ｒ、ｘ、ｙ及び平文ｍを用いて、ｂ1＝ｍryＹｒ、ｂ3＝ｍrxyＹrx、ｂ5＝ｇ2ryを計算して電子署名σ＝(ｂ1、ｂ3、ｂ5)を生成する。検証装置は、公開鍵pk、電子署名σ及び平文ｍを用いて、e(ｂ1、ｇ2)＝e(ｍｇ1、ｂ5)とe(ｂ3、ｇ2)＝e(ｂ1、Ｘ')が成立するか判定することにより改竄等が行われていないか検証する。
【解決手段】ｑを素数とし、Ｇ1，Ｇ2，ＧTを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ1×Ｇ2→ＧTとし、電子署名装置は、乱数ｘ及びｙとＧ1及びＧ2それぞれの生成元ｇ1及びｇ2を用いて、Ｘ'＝ｇ2x、Ｙ'＝ｇ2y、Ｙ＝ｇ1yを計算し、公開鍵pkを生成する。ｇ1、ｇ2、乱数ｒ、ｘ、ｙ及び平文ｍを用いて、ｂ1＝ｍryＹｒ、ｂ3＝ｍrxyＹrx、ｂ5＝ｇ2ryを計算して電子署名σ＝(ｂ1、ｂ3、ｂ5)を生成する。検証装置は、公開鍵pk、電子署名σ及び平文ｍを用いて、e(ｂ1、ｇ2)＝e(ｍｇ1、ｂ5)とe(ｂ3、ｇ2)＝e(ｂ1、Ｘ')が成立するか判定することにより改竄等が行われていないか検証する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電気通信システムで送信者の身元を確認する電子署名検証システム、電子署名装置、検証装置、その方法及びプログラムに関する。
【背景技術】
【０００２】
電子署名はメッセージｍに対して、公開鍵pkに対応する秘密鍵skを知る署名者が、メッセージｍに対して秘密鍵skを正しく使ったときにのみ計算できる値σを算出し、これを電子的な署名として用いるものである。正しく計算された電子署名は誰でも公開鍵pkを用いてその正当性を検証することが可能である。一方、秘密鍵skを知らないいかなる第三者も正当な電子署名σを算出することはできない。電子署名は電子現金やクレデンシャルシステムなど、様々な暗号プロトコルにおいて基本的な構成要素として利用されている。
【０００３】
電子署名は電子現金やクレデンシャルシステムなど、様々な暗号プロトコルにおいて基本的な構成要素として利用されている。特に、利用者のプライバシーを必要とする応用においては、ゼロ知識証明と組み合わせることにより、電子署名σを明かさないまま、あるメッセージに対する電子署名を保持しているという事実を任意の第三者に納得させるなど、高度な利用形態がある。例えば、非特許文献１のようにペアリング技術を用い、群の要素がある関係を満たすという事実を効率的に証明するゼロ知識証明が構成可能となった。これによって、電子署名σが効率的なバイリニアマップを持つ群の要素である、すなわち、σ∈Ｇである場合、前述のように、電子署名σを明かさないまま、正しい電子署名σを保持しているという事実を証明することが可能である。
【０００４】
例えば、非特許文献２記載の技術、いわゆる、CL-Signatureと言われる技術では、メッセージｍ∈Ｚqに対する電子署名σは３つの群要素(ａ，ｂ，ｃ)∈Ｇ３から構成されている。
【０００５】
しかしながら、CL-Signatureと言われる技術では、ランダムオラクルモデル等の理想化された構成要素を用いず、数論的な仮定のみによって安全性が証明できる既存の電子署名方法では、メッセージｍが群Ｇの要素ではないため、メッセージｍを秘匿した状態で、その秘匿したメッセージに対する正しい電子署名を保持していることを証明する、という応用には適さない。
メッセージｍが群Ｇの要素である場合にも、安全な電子署名方法として、上記のCL-Signatureを改良した方式が非特許文献３に示されている。それについて以下に簡単に説明する。
【０００６】
ｑを大きな素数とし、Ｇ１，Ｇ２，ＧＴをそれぞれ位数ｑの群とし、ｅを効率的に計算可能なバイリニアマップｅ：Ｇ１×Ｇ２→ＧＴとし、ｖ＝(ｑ，Ｇ１，Ｇ２，ＧＴ，ｅ)を公開パラメータとする。
【０００７】
署名者は、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択し、Ｚqに属する乱数ｒ、ｘ及びｙを生成し、Ｘ＝ｇ２ｘ、Ｙ＝ｇ２ｙとする。また、pk＝(ｖ、ｇ１、ｇ２、Ｘ、Ｙ）を公開鍵とし、sk＝(ｘ、ｙ)を秘密鍵とする。
【０００８】
メッセージｍ∈Ｇ１に対して、以下の５つの式
ａ１＝ｇ１ｒ (1)
ａ２＝ｍｒ (2)
ａ３＝ｇ１ｒｘｍｒｘｙ (3)
ａ４＝ｍｒｙ (4)
ａ５＝ｇ２ｒ (5)
を計算し、これら５つの値の組をメッセージｍに対する電子署名σ＝(ａ１，ａ２，ａ３，ａ４，ａ５)∈Ｇ１４×Ｇ２とする。
【０００９】
検証者は、与えられたメッセージ署名対(ｍ、σ)に対し、公開鍵pk及び電子署名σを用いて、以下の４つのペアリング等式が成り立つことを確認し、電子署名の真正性及び完全性を検証する。
【００１０】
e(ｇ１，ａ５)＝e(ａ１，ｇ２) (6)
e(ｍ，ａ５)＝e(ａ２，ｇ２) (7)
e(ａ２，Ｙ)＝e(ａ４，ｇ２) (8)
e(ａ３，ｇ２)＝e(ａ１ａ４，Ｘ) (9)
【００１１】
＜検証方法＞
式(6)は式(1)及び(5)を用いて、以下のように表すことができる。
e(ｇ１，ｇ２ｒ)＝e (ｇ１ｒ，ｇ２) (6)'
これが成立することにより、バイリニアマップの性質から、両辺中の検証装置に知らされていない乱数ｒが同一であることを確認することができる。同様に、式(7)は式(1)及び(2)を用いて、以下のように表すことができる。
e(ｍ，ｇ２ｒ)＝e(ｍｒ，ｇ２) (7)'
式(6)'でｒの同一性が確認されたので、式(7)'が成立することにより、受信したｍと署名の対象となったｍが同一であることを確認することができる。式(8)は式(2)、(4)、Ｙ＝ｇ２ｙを用いて、以下のように表すことができる。
e(ｍｒ，ｇ２ｙ)＝e(ｍｒｙ，ｇ２) (8)’
式(6)'と(7)'で乱数ｒの同一性とメッセージｍの同一性が確認されたので、式(8)'が成り立つ場合には、乱数ｙが正しいことが確認できる。式(9)は、式(1)、(3)、(4)、Ｘ＝ｇ２ｘを用いて、以下のように表すことができる。
e(ｇ１ｒｘｍｒｘｙ，ｇ２)＝e(ｇ１ｒｍｒｙ，ｇ２ｘ) (9)’
式(6)', (7)', (8)'で乱数ｒ、メッセージｍ、及び乱数ｙが正しいことが確認できたので、式(9)'が成り立つ場合には、乱数ｘが正しいことが確認できる。これらの処理により、電子署名σを作成できるのは、秘密鍵sk＝(ｘ，ｙ)を知っている署名者のみであることが確認できる。
【先行技術文献】
【非特許文献】
【００１２】
【非特許文献１】Jens Groth, Amit Sahai, "Efficient Non-interactive Proof Systems for Bilinear Groups", Advances in Cryptology - EUROCRYPT 2008, Springer Berlin / Heidelberg, June 3,2008, Volume 4965/2008, p415-432
【非特許文献２】Jan Camenisch, Anna Lysyanskaya, " Signature Schemes and Anonymous Credentials from Bilinear Maps", Advances in Cryptology - CRYPTO 2004, Springer Berlin / Heidelberg, 2004, Volume 3152/2004, p.56-72
【非特許文献３】Matthew Green, Susan Hohenberger, "Universally Composable Adaptive Oblivious Transfer", [online], The Johns Hoｐｋins University Information Security Institute, ［平成20年11月19日］, インターネット<URL:http://eprint.iacr.org/cgi-bin/getfile.pl?entry=2008/163&version=20080806:150034&file=163.pdf>
【発明の概要】
【発明が解決しようとする課題】
【００１３】
非特許文献３記載の電子署名検証方法及び装置では、電子署名を構成する要素の数が多く、電子署名長が長くなり、情報量及び通信量が多くなるという問題があった。また、検証時の計算量が多いという問題があった。本発明は、電子署名を構成する要素の数を少なくし、電子署名長が短く、情報量及び通信量が少ない電子署名検証方法及び装置を提供することを目的とし、また、検証時の計算量の少ない電子署名検証方法及び装置を提供することを目的とする。
【課題を解決するための手段】
【００１４】
この発明の第１の観点による電子署名検証システムにおいては、
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）とし、
前記電子署名装置は、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択部と、
Ｚqに属する乱数ｒ、ｘ及びｙを生成する乱数生成部と、
前記ｘ、ｙ、ｇ１及びｇ２が入力され、Ｘ'＝ｇ２ｘ、Ｙ'＝ｇ２ｙ、Ｙ＝ｇ１ｙを計算し、公開鍵pkをpk＝(ｖ，ｇ１，ｇ２，Ｘ'，Ｙ'，Ｙ)として生成する公開鍵生成部と、
前記ｇ１、ｇ２、ｒ、ｘ、ｙ及び平文ｍが入力され、
ｂ１＝ｍｒｙＹｒ、
ｂ３＝ｍｒｘｙＹｒｘ、
ｂ５＝ｇ２ｒｙ
を計算し、電子署名σ＝(ｂ１，ｂ３，ｂ５)を生成する電子署名生成部とを有す。
前記検証装置は、前記電子署名装置から前記電子署名σ及び平文ｍを受け、前記公開鍵pk、電子署名σ及び平文ｍを使って、
式(1)： e(ｂ１，ｇ２)＝e(ｍｇ１，ｂ５)
式(2)： e(ｂ３，ｇ２)＝e(ｂ１，Ｘ')
を計算し、式(1)と(2)の等式全てが成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定部を有する。
この発明の第２の観点による電子署名検証システムにおいては、
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）とし、
前記電子署名装置は、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択部と、
Ｚqに属するｎ個の乱数ｒi, 但し、i=1,…, n、と乱数ｘ及びｙを生成する乱数生成部と、
前記ｘ、ｙ、ｇ1及びｇ2が入力され、Ｘ'＝ｇ2x、Ｙ'＝ｇ2y、Ｙ＝ｇ1yを計算し、公開鍵pk＝(ｖ，ｇ1，ｇ2，Ｘ'，Ｙ'，Ｙ)を生成する公開鍵生成部と、
前記ｇ1、ｇ2、ｎ個のｒi、ｘ、ｙ及びｎ個の平文ｍiが入力され、i=1,…,nについて
ｂ1i＝ｍiriｙＹri、
ｂ3＝(Πni=1ｍiri)ｘｙ(Πni=1Ｙri)ｘ、
ｂ5i＝ｇ２riｙ
を計算し、電子署名σ＝(ｂ1i，ｂ３，ｂ5i)を生成する電子署名生成部とを有す。
前記検証装置は、前記電子署名装置から前記電子署名σ及びｎ個の平文ｍｉを受け、前記公開鍵pk、電子署名σ及びｎ個の平文ｍiを使って、
式(1)： e(ｂ1i，ｇ２)＝e(ｍiｇ１，ｂ5i)
式(2)： e(ｂ3，ｇ2)＝e(Πni=1ｂ1i，Ｘ')
を計算し、式(1)と(2)の等式全てが成立するか否かをi=1,…,nについて判定し、成立する場合には受理し、成立しない場合には拒否する判定部を有する。
この発明の第３の観点による電子署名検証システムにおいては、
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝(ｑ，Ｇ１，Ｇ２，ＧT，ｅ)とし、
前記電子署名装置は、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択部と、
Ｚqに属する乱数ｒ、ｘ及びｎ個の乱数ｙi、但し、i=1,…,n、を生成する乱数生成部と、
前記ｘ、ｙｉ、ｇ１及びｇ２が入力され、Ｘ'＝ｇ２ｘ、Ｙ'ｉ＝ｇ２ｙｉ、Ｙi＝ｇ1yiを計算し、公開鍵pk＝(ｖ，ｇ1，ｇ2，Ｘ'，Ｙ'i，Ｙi)を生成する公開鍵生成部と、
前記ｇ１、ｇ２、ｒ、ｘ、ｙｉ及びｎ個の平文ｍｉが入力され、
ｂ1i＝ｍiryiＹir、
ｂ3＝(Πni=1ｍiyi)rx(Πni=1Ｙi)rx、
ｂ5i＝ｇ2ryi
を計算し、電子署名σ＝(ｂ1i，ｂ３，ｂ5i)を生成する電子署名生成部とを有する。
前記検証装置は、前記電子署名装置から前記電子署名σ及びｎ個の平文ｍｉを受け、前記公開鍵pk、電子署名σ及びｎ個の平文ｍiを使って
式(1)： e(ｂ1i，ｇ2)＝e(ｍiｇ１，ｂ5i)
式(2)： e(ｂ3，ｇ2)＝e(Πni=1ｂ1i，Ｘ')
を計算し、式(1), (2)の等式全てがi=1,…,nについて成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定部を有する。
【発明の効果】
【００１５】
本発明の電子署名検証方法及び装置によれば、従来技術同様、真正性及び完全性を担保しながら、群の元を用いて電子署名を構成することができ、かつ、電子署名を構成する要素の数を少なくすることにより、電子署名長が短く、通信量が少なくすることができる。また、検証時の計算式の少なくすることにより、計算量を少なくすることができる。
【図面の簡単な説明】
【００１６】
【図１】実施例１における電子署名検証システムの構成例を示す図。
【図２】電子署名検証システム１のシーケンス図の一例を示す図。
【図３】電子署名装置１００の構成例を示す図。
【図４】電子署名装置１００の処理フローの一例を示す図。
【図５】検証装置２００の構成例を示す図。
【図６】検証装置２００の処理フローの一例を示す図。
【図７】この発明の実施例２による電子署名検証システムの構成例を示す図。
【図８】実施例２における電子署名装置の構成例を示す図。
【図９】実施例２における検証装置の構成例を示す図。
【図１０】実施例３における電子署名検証システムの構成例を示す図。
【図１１】実施例３における電子署名装置の構成例を示す図。
【図１２】実施例３における検証装置の構成例を示す図。
【図１３】実施例１における電子署名装置のハードウェア構成を例示したブロック図。
【発明を実施するための形態】
【００１７】
［発明の原理］
前述の非特許文献３の技術において、この発明では公開鍵として新たにＹ＝ｇ１ｙを加えpk＝(ｖ、ｇ１、ｇ２、Ｘ'，Ｙ'，Ｙ)とする。ＳＸＤＨ(asymmetric XDH)仮定を前提とし、その仮定の下ではＹ'＝ｇ２ｙとＹ＝ｇ１ｙとが公開されていたとしても互いに独立であり、互いの情報を一切漏らさない。更に、この発明では３つ要素の組(ｂ１、ｂ２、ｂ３) ∈Ｇ１２×Ｇ２、ただし、
ｂ１＝ｍｒｙＹｒ
ｂ３＝ｍｒｘｙＹｒｘ
ｂ５＝ｇ２ｒｙ
をメッセージｍに対する署名σとする。即ち署名σは
σ＝(ｍｒｙＹｒ，ｍｒｙｘＹｒｘ、ｇ２ｒｙ)
である。メッセージ署名対(ｍ、σ)に対する検証は、次の２つのペアリング等式、
e(ｂ１，ｇ２)＝e(ｍｇ１，ｂ５)
e(ｂ３、ｇ２)＝e(ｂ１、Ｘ')
が成立するかの判定による。
なお、ＳＸＤＨ仮定について述べる前にまずＸＤＨについて述べる。ＸＤＨはThe External Diffie-Hellman (XDH) assumptionの略であり、いわゆる楕円のペアリングなどが存在する場合に、以下の３つの性質を持つことを想定した仮定である。
・The discrete logarithm problem (DLP)→離散対数問題
・The computational Diffie-Hellman problem (CDH)→いわゆるＤＨ問題
・The computational co-Diffie-Hellman problem (co-DH)
上記のうち、co-DHとは以下のように双対の片方のグループの情報を与えられて、与えられたのとは別のグループのＤＨを計算する問題であり、これを解くのが難しいことを仮定している。具体的には、以下の通りである。
(G1; G2)上のThe co-Diffie-Hellman (co-DH) problemは：
G1, G2をそれぞれP1, P2により生成した位数Ｌの巡回群とする。(G1,G2)上のco-DH問題は(P1; aP1; P2)が与えられaP2を計算することである。
これを、ペアリングの双方のグループに対して仮定しているのがＳＸＤＨである。
【実施例１】
【００１８】
［電子署名検証システム１］
図１は、電子署名検証システム１の構成例を示す図である。図２は、電子署名検証システム１のシーケンス図の一例を示す図である。電子署名検証システム１は、登録装置３００と、電子署名装置１００と、検証装置２００からなる。
【００１９】
ｑを大きな素数とし、Ｇ１，Ｇ２，ＧＴを位数ｑの群とし、ｅを効率的に計算可能なバイリニアマップｅ：Ｇ１×Ｇ２→ＧＴとし、ｖ＝（ｑ，Ｇ１，Ｇ２，ＧＴ，ｅ）を公開パラメータとする。なお、ｇａとは、ｇ∈Ｇに対し、群Ｇで定義される演算をａ回行うことを意味する。バイリニアマップとしては、例えば、WeilペアリングやTateペアリング等が考えられる。
【００２０】
電子署名装置１００は、登録装置３００に対して、公開パラメータｖを要求する（Ｓ１０）。登録装置３００は、ｖを電子署名装置１００へ送る（Ｓ１２）。電子署名装置１００は、公開パラメータｖから公開鍵pkを生成し、登録装置３００へ送る（Ｓ１４）。登録装置３００は、公開鍵pkを登録及び公開する（Ｓ１６）。なお、署名の生成ごとに公開パラメータを要求しなくとも、記憶している公開パラメータを利用して公開鍵を生成してもよい。さらに、メッセージ（以下、平文とも呼ぶ）ｍ、公開鍵pk及び秘密鍵skを用いて、電子署名σを生成する。電子署名装置１００は、電子署名σ及び平文ｍを検証装置へ送る（Ｓ１８）。
【００２１】
検証装置２００は、電子署名σに対応する公開鍵pkを登録装置３００へ要求する（Ｓ２０）。登録装置３００は、公開鍵pkを検証装置２００へ送る（Ｓ２２）。検証装置２００は、電子署名σ、平文ｍ、公開鍵pkを用いて、改竄及び成りすまし等が行われていないか検証する（Ｓ２４）。以下、各装置及び各処理について詳細を説明する。
【００２２】
［登録装置３００］
登録装置３００は、公開パラメータｖ＝(ｑ、Ｇ１，Ｇ２，ＧＴ，ｅ)を登録及び公開している。例えば、登録装置３００は、信頼できる第三者等が管理し、図示してない通信部と、記憶部と、制御部を有する。登録装置３００は、通信部を介して、電子署名装置及び検証装置と通信する。通信部は、例えば、ＬＡＮアダプタ等により構成され、ＬＡＮやインターネット等からなる通信回線と接続される。但し、必ずしも通信部を有さずともよく、例えば、キーボード等の入力装置から公開パラメータを入力してもよいし、また、ＵＳＢメモリ等の可搬媒体に公開パラメータを記憶し、それを入力してもよい。以下、同様に各装置（電子署名装置及び検証装置）は送信部を有さずともよく、装置間のデータの入出力は、通信以外の方法であってもよい。記憶部は、公開パラメータ、公開鍵等を記憶する。なお、上記「登録」とは、記憶部に記憶することを意味してもよい。また、「公開」とは、利用者の求めに応じて、情報（例えば、公開パラメータ）を閲覧可能、または、取得可能とすることを意味する。制御部は、各処理を制御する。
【００２３】
［電子署名装置１００］
図３は、電子署名装置１００の構成例を示す図である。図４は、電子署名装置１００の処理フローの一例を示す図である。電子署名装置１００は、通信部１０１と、記憶部１０３と、制御部１０５と、生成元選択部１２０と、乱数生成部１３０と、公開鍵生成部１４０と、電子署名生成部１５０を有する。
【００２４】
＜制御部１０５及び通信部１０１＞
本実施例の電子署名装置１００は、制御部１０５の制御のもと各処理を実行する。電子署名装置１００は、登録装置３００から公開パラメータｖを受け取る。例えば、通信部１０１は、登録装置３００及び検証装置２００と通信を行い、登録装置３００から公開パラメータｖを受信する（Ｓ１０１）。以下、特に記述しなくとも、登録装置３００及び検証装置２００と通信する際には、通信部１０１を介して行われるものとする。
【００２５】
受信した公開パラメータｖを記憶部１０３に記憶する（Ｓ１０３）。また、特に示さない限り、入出力される各データや演算過程の各データは、逐一、記憶部１０３に格納・読み出され、各演算処理が進められる。但し、必ずしも記憶部１０３に記憶しなければならないわけではなく、各部間で直接データを受け渡してもよい。
【００２６】
＜生成元選択部１２０、乱数生成部１３０及び記憶部１０３＞
生成元選択部１２０は、公開パラメータｖ中の群Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する（Ｓ１２０）。生成元選択部１２０は、通信部１０１を介して、または、通信部１０１及び記憶部１０３を介して、公開パラメータｖを入力され、生成元ｇ１及びｇ２を公開鍵生成部１４０及び電子署名生成部１５０へ、出力する。乱数生成部１３０は、Ｚqに属する乱数ｒ、ｘ及びｙを生成して出力する（Ｓ１３０）。乱数生成部１３０は、乱数ｘ、ｙを公開鍵生成部１４０へ、乱数ｒ、ｘ、ｙを電子署名生成部１５０へ出力する。記憶部１０３は、乱数ｒ、ｘ及びｙが記憶され、特にｘ、ｙは秘密鍵sk＝(ｘ，ｙ)として秘密に記憶される（Ｓ１３３）。なお、秘密鍵skには、対応する公開鍵pkを含め、sk＝(pk，ｘ，ｙ)としてもよい。他の実施例においても同様である。公開鍵pkについての詳細は後述する。
【００２７】
＜公開鍵生成部１４０＞
公開鍵生成部１４０は、ｘ、ｙ、ｇ１及びｇ２が入力され、Ｘ'＝ｇ２ｘ、Ｙ'＝ｇ２ｙ、Ｙ＝ｇ１ｙを計算し、公開鍵pk＝（ｖ，ｇ１，ｇ２，Ｘ'，Ｙ'，Ｙ）を生成する（Ｓ１４０）。公開鍵pkは、通信部１０１を介して、登録装置３００へ送られる。なお、公開鍵pkには、利用した公開パラメータｖの代わりに、それを表す鍵情報ｉを含めpk＝(ｉ，ｇ１，ｇ２，Ｘ'，Ｙ'，Ｙ)としてもよい。この場合には、以下で説明する検証装置２００は、鍵情報ｉに基づいて、登録装置３００に対応する公開パラメータｖｉを要求する。また、登録装置３００の記憶している公開パラメータの中から対応する公開パラメータｖを特定することができる場合には、公開鍵pkに公開パラメータｖや、公開パラメータを表示する鍵情報ｉ等を含まなくともよく、検証装置２００は、平文ｍ及び電子署名σを受け付けた際に、登録装置３００に公開パラメータｖを要求する。
【００２８】
＜電子署名生成部１５０＞
電子署名生成部１５０は、ｇ１、ｇ２、ｒ、ｘ、ｙ及び平文ｍ∈Ｇ１が入力され、
ｂ１＝ｍｒｙＹｒ (11)
ｂ３＝Ｙｒｘｍｒｘｙ (12)
ｂ５＝ｇ２ｒｙ (13)
を計算し、平文ｍに対する電子署名σ＝(ｂ１，ｂ３，ｂ５)を生成する（Ｓ１５０）。なお、平文ｍ∈Ｚqであり、補助記憶装置やメモリ上のデータ等、もしくは、入力インターフェース、キーボード、マウス等から入力されるデータである。
【００２９】
電子署名装置１００は、公開鍵pkを登録装置３００へ、電子署名σ及び平文ｍを検証装置２００へ、送る。例えば、通信部１０１を介して、送信する（Ｓ１５３）。
【００３０】
このような構成とすることで、電子署名σを構成する要素の数を５つから３つに少なくすることができる。これにより、例えば、電子署名σの各要素を生成する演算量が同一の場合には、演算量を４０％軽減できる。また、例えば、電子署名σの各要素が同一の情報量を有している場合には、電子署名長を４０％短く作成することができる。これにより電子署名σに要する通信量を軽減することもできる。
【００３１】
［検証装置２００］
図５は、検証装置２００の構成例を示す。図６は、検証装置１００の処理フローの一例を示す図である。検証装置２００は、通信部２０１と、記憶部２０３と、制御部２０５と、判定部２２０を有する。
＜制御部２０５、通信部２０１及び記憶部２０３＞
本実施例の検証装置２００は、制御部２０５の制御のもと各処理を実行する。検証装置は、登録装置から公開鍵pkを、電子署名装置から電子署名σ及び平文ｍを、受け取る。例えば、通信部２０１は、登録装置３００及び検証装置１００と通信を行う。登録装置３００から公開鍵pkを受信する（Ｓ２０１）。電子署名装置１００から電子署名σ及び平文ｍを受信する（Ｓ２０２）。機能、構成等は、通信部１０１と同様である。記憶部２０３は、公開鍵pk、電子署名σ及び平文ｍが記憶される（Ｓ２０３）。
【００３２】
＜判定部２２０＞
判定部２２０は、以下の２つの等式が成立するか否かを判定する（Ｓ２２０）。成立する場合には受理し（Ｓ２２３）、成立しない場合には拒否する（Ｓ２２５）。
【００３３】
e(ｂ１，ｇ２)＝e(ｍｇ１，ｂ５) (14)
e(ｂ３，ｇ２)＝e(ｂ１，Ｘ') (15)
判定部２２０は、通信部２０１を介して、または、通信部２０１及び記憶部２０３を介して、公開鍵pk、署名σ及び平文ｍが入力される。以下、上記の式(15), (16)による検証について説明する。
【００３４】
＜検証方法の妥当性＞
式(14)は式(11)及び(13)、Ｙ＝ｇ１ｙを用いて、以下のように表すことができる。
e((ｍｇ１)ｒｙ，ｇ２)＝e(ｍｇ１，ｇ２ｒｙ) (14)’
これはバイリニアマップｅの性質を示しているので、式(14)が成立する場合には、署名者が署名生成時に使用した乱数ｒ及びｙと、検証者が受信した署名の生成に使用されたであろう乱数ｒ及びｙが同一であることを確認できる。
式(15)は式(12), (11)、及びＹ＝ｇ１ｙ，Ｘ'＝ｇ２ｘを用いて、以下のように表すことができる。
e((ｍｒｙＹｒ)ｘ，ｇ２)＝e(ｍｒｙＹｒ，ｇ２ｘ) (15)’
これもバイリニアマップｅの性質を示している。従って、式(14)の成立により乱数ｒとｙの正当性が確認できていれば、式(15)が成立することにより平文ｍと乱数ｘの正当性が確認できる。即ち、前述の従来技術と同様に、電子署名σを作成できるのは、秘密鍵sk＝(ｘ，ｙ)を知っている署名者のみであることが確認できる。このような構成とすることで、従来技術同様、真正性及び完全性を担保しながら、群の元を用いて電子署名を構成することができる。また、検証時の計算式を４つから２つに少なくすることにより、各計算式の計算量が同一の場合には、計算量を５０％軽減することができる。
【実施例２】
【００３５】
図７はこの発明の実施例２による電子署名検証システムの構成例を示し、図８はその電子署名装置の構成例を示し、図９は検証装置の構成例を示す。実施例２は実施例１における署名対象である平文ｍが複数の場合にも対処可能にしたものであり、実施例１と異なる部分についてのみ説明する。平文ｍｉ(ｉ＝1, …, ｎ)の数ｎは１以上の整数である。ｎ＝１のときは実質的に実施例１と同じになるが、実施例２ではｎが１のみならず２以上の値にも対応できるように構成されている。
【００３６】
［電子署名検証システム１０００］
図７に示す量に、電子署名検証システム１０００は、登録装置３００と、電子署名装置１１００と、検証装置１２００からなる。電子署名装置１１００は、ｎ個の平文ｍｉに対し電子署名を生成するために、まず登録装置３００に対して、公開パラメータｖ＝(ｑ、Ｇ１，Ｇ２，ＧＴ，ｅ)を要求する。登録装置３００は、ｖを電子署名装置１００へ送る。電子署名装置１１００は、公開パラメータｖから公開鍵pk＝(ｖ、ｇ１，ｇ２，Ｘ'，Ｙ'，Ｙ)を生成し、登録装置３００へ送る。さらに、ｎ個の平文ｍｉ、公開鍵pk及び秘密鍵skを用いて、電子署名σを生成する。電子署名装置１１００は、電子署名σ及び平文ｍｉを検証装置１２００へ送る。
【００３７】
検証装置１２００は、電子署名σに対応する公開鍵pkを登録装置３００へ要求する。登録装置３００は、ｐｋを検証装置１２００へ送る。検証装置１２００は、電子署名σ、平文ｍｉ、公開鍵pkを用いて、改竄及び成りすまし等が行われていないか検証する。以下、電子署名装置１１００及び検証装置１２００について詳細を説明する。
【００３８】
［電子署名装置１１００］
図８に示すように、電子署名装置１１００は、通信部１０１と、記憶部１０３と、制御部１０５と、生成元選択部１２０と、乱数生成部１１３０と、公開鍵生成部１４０と、電子署名生成部１１５０を有する。
【００３９】
＜乱数生成部１１３０及び記憶部１０３＞
乱数生成部１１３０は、Ｚqに属するｎ個の乱数ｒｉ(ｉ=1, …, ｎ)、ｘ及びｙを生成して出力する。つまり、本実施例においては、ｎ個の平文ｍｉに対応するｎ個の乱数ｒｉを生成する。乱数生成部１１３０は、乱数ｘ、ｙを公開鍵生成部１４０へ、ｎ個の乱数ｒｉとｘ、ｙを電子署名生成部１１５０へ出力する。記憶部１０３は、乱数ｒｉ、ｘ及びｙが記憶される。
＜公開鍵生成部１４０＞
公開鍵生成部１４０はＸ'＝ｇ２ｘ、Ｙ'＝ｇ２ｙ、Ｙ＝ｇ１ｙを計算し、公開鍵pk＝(ｖ、ｇ１、ｇ２、Ｘ'、Ｙ'、Ｙ)を生成する。
【００４０】
＜電子署名生成部１１５０＞
電子署名生成部１１５０は、ｇ１、ｇ２、ｒｉ、ｘ、ｙ及び平文ｍｉ∈Ｇ１が入力され、
ｂ1i＝ｍiriｙＹri (16)
ｂ3＝(Πni=1ｍiri)ｘｙ(Πni=1Ｙri)ｘ (17)
ｂ5i＝ｇ2riｙ (18)
を計算し、電子署名σ＝(ｂ1i，ｂ3，ｂ5i)(i=1, …, n)を生成する。なお、式(16), (17), (18)において、riとは、上記乱数ｒｉのことを意味する。電子署名生成部１１５０は、生成元選択部１２０から生成元ｇ１、ｇ２を、乱数生成部１１３０から乱数ｒｉ、ｘ、ｙを、さらに平文ｍｉを入力され、電子署名σを出力する。
【００４１】
電子署名装置１１００は、公開鍵pkを登録装置３００へ、電子署名σ及び平文ｍｉを検証装置１２００へ、送る。例えば、通信部１０１を介して、送信する。
【００４２】
このような構成とすることで、実施例１同様、電子署名σを構成する要素の数を５つから３つに少なくすることができ、実施例１と同様の効果を得ることができる。さらに、１個又は複数の平文ｍｉ(ｉ＝１，…，ｎ)に対して電子署名σを生成することができるため、実施例１の方法により複数の平文に対し、複数の電子署名を作成するのに比べ、処理を軽減することができる。また、電子署名の情報量、通信量を小さくすることができる。
【００４３】
［検証装置１２００］
図９に示すように、検証装置１２００は、通信部２０１と、記憶部２０３と、制御部２０５と、判定部１２２０を有する。
【００４４】
＜判定部１２２０＞
判定部１２２０は、以下の等式全てがｉ＝１，…，ｎの全てについて成立するか否かを判定する。成立する場合には受理し、成立しない場合には拒否する。
e(ｂ1i，ｇ２)＝e(ｍiｇ１，ｂ5i) (19)
e(ｂ３，ｇ２)＝e(Πni=1ｂ1i，Ｘ') (20)
判定部１２２０は、通信部２０１を介して、または、通信部２０１及び記憶部２０３を介して、公開鍵pk、署名σ及び平文ｍｉが入力される。
【００４５】
このような構成とすることによって、検証時の計算式を４つから２つに少なくし、実施例１同様の効果が得られる。さらに、等式の両辺を乗算にてまとめることにより、実施例１の方法により複数の電子署名を検証するのに比べ、処理を軽減することができる。
式(19), (20)による検証の妥当性は実施例１の場合と同様に示すことができる。
【実施例３】
【００４６】
図１０はこの発明の第３実施例による電子署名検証システムの構成例を示し、図１１はその電子署名装置の構成例を示し、図１２は検証装置の構成例を示す。上述の実施例２ではｎ個の平文ｍi(i=1,…,n、ｎは１以上の整数)に対応してｎ個の乱数ｒiを使用したが、以下に説明するこの実施例３では、実施例１と同様に乱数ｒは１つとし、ｎ個の平文に対応してｎ個の乱数ｙiを使用する。ｎ＝１の場合は実質的に実施例１と同じになるが、実施例３ではｎ＝１の場合のみならず、ｎが２以上の場合にも対応できるように構成されている。
【００４７】
［電子署名検証システム２０００］
図１０に示すように、実施例３による電子署名検証システム２０００は、登録装置３００と、電子署名装置２１００と、検証装置２２００からなる。電子署名装置２１００は、複数の平文ｍｉを検証装置２２００に送る際に、電子署名σを添付するために、登録装置３００に対して、公開パラメータｖを要求する。登録装置３００は、ｖを電子署名装置１００へ送る。電子署名装置２１００は、公開パラメータｖから公開鍵pkを生成し、登録装置３００へ送る。さらに、平文ｍｉ、公開鍵pk及び秘密鍵skを用いて、電子署名σを生成する。電子署名装置２１００は、電子署名σ及び平文ｍｉを検証装置２２００へ送る。
【００４８】
検証装置２２００は、電子署名σに対応する公開鍵pkを登録装置３００へ要求する。登録装置３００は、pkを検証装置２２００へ送る。検証装置２２００は、電子署名σ、平文ｍｉ、公開鍵pkを用いて、改竄及び成りすまし等が行われていないか検証する。以下、電子署名装置２１００及び検証装置２２００について詳細を説明する。
【００４９】
［電子署名装置２１００］
図１１に示すように、電子署名装置２１００は、通信部１０１と、記憶部２１０３と、制御部１０５と、生成元選択部１２０と、乱数生成部２１３０と、公開鍵生成部２１４０と、電子署名生成部２１５０を有する。
【００５０】
＜乱数生成部２１３０及び記憶部２１０３＞
乱数生成部２１３０は、Ｚqに属する乱数ｒ、ｘ及びｙｉを生成して出力する。つまり、本実施例においては、複数の平文ｍｉに対応する複数の乱数ｙｉを生成する。乱数生成部２１３０は、乱数ｘ、ｙｉを公開鍵生成部２１４０へ、乱数ｒ、ｘ、ｙｉを電子署名生成部２１５０へ出力する。記憶部２１０３は、乱数ｒ、ｘ及びｙｉが記憶され、特にｘ、ｙｉは秘密鍵sk＝(ｘ，ｙi)として秘密に記憶される。
【００５１】
＜公開鍵生成部２１４０＞
公開鍵生成部２１４０は、ｘ、ｙｉ、及びｇ２が入力され、Ｘ'＝ｇ２ｘ、Ｙｉ'＝ｇ２ｙi、Ｙi＝ｇ1yi(但し、yiは、ｙｉを表す）を計算し、公開鍵pk＝(ｖ，ｇ１，ｇ２，Ｘ'，Ｙi'，Ｙｉ)を生成する。
【００５２】
＜電子署名生成部２１５０＞
電子署名生成部２１５０は、ｇ１、ｇ２、ｒ、ｘ、ｙｉ及び平文ｍｉ∈Ｇ１が入力され、
ｂ1i＝ｍiｒyiＹiｒ (21)
ｂ３＝(Πni=1ｍiyi)ｒｘ(Πni=1Ｙi)ｒｘ (22)
ｂ5i＝ｇ2ｒyi (23)
を計算し、電子署名σ＝(ｂ1i，ｂ３，ｂ5i)を生成する。なお、式(21)〜(23)において、yiとは、上記乱数ｙｉのことを意味する。電子署名生成部２１５０は、生成元選択部１２０から生成元ｇ１、ｇ２を、乱数生成部２１３０から乱数ｒ、ｘ、ｙｉを、さらに平文ｍｉを入力され、電子署名σを出力する。
このような構成とすることで、実施例２と同様の効果が得られる。
【００５３】
［検証装置２２００］
図１２に示すように、検証装置２２００は、通信部２０１と、記憶部２０３と、制御部２０５と、判定部２２２０を有する。
【００５４】
＜判定部２２２０＞
判定部２２２０は、以下の等式全てが成立するか否かを判定する。成立する場合には受理し、成立しない場合には拒否する。
【００５５】
e(ｂ1i，ｇ２)＝e(ｍiｇ１，ｂ5i) (24)
e(ｂ３，ｇ２)＝e(Πni=1ｂ1i，Ｘ'） (25)
式(24), (25)による検証の妥当性は実施例１の場合と同様に示すことができる。
このような構成とすることによって、実施例２と同様の効果が得られる。
【００５６】
＜ハードウェア構成＞
図１３は、図１に示した実施例１における電子署名装置１００のハードウェア構成を例示したブロック図である。検証装置２００及び登録装置３００も同様の構成を有する。
【００５７】
図１３に例示するように、この例の電子署名装置１００、検証装置２００、登録装置３００は、それぞれＣＰＵ（Central Processing Unit）１１、入力部１２、出力部１３、補助記憶装置１４、ＲＯＭ（Read Only Memory）１５、ＲＡＭ（Random Access Memory）１６及びバス１７を有している。
【００５８】
この例のＣＰＵ１１は、制御部１１ａ、演算部１１ｂ及びレジスタ１１ｃを有し、レジスタ１１ｃに読み込まれた各種プログラムに従って様々な演算処理を実行する。また、入力部１２は、データが入力される入力インターフェース、キーボード、マウス等であり、出力部１３は、データが出力される出力インターフェース等である。補助記憶装置１４は、例えば、ハードディスク、ＭＯ（Magneto-Optical disc）、半導体メモリ等であり、電子署名装置１００、検証装置２００及び登録装置３００としてコンピュータを機能させるためのプログラムが格納されるプログラム領域１４ａ及び各種データが格納されるデータ領域１４ｂを有している。また、ＲＡＭ１６は、ＳＲＡＭ (Static Random Access Memory)、ＤＲＡＭ (Dynamic Random Access Memory)等であり、上記のプログラムが格納されるプログラム領域１６ａ及び各種データが格納されるデータ領域１６ｂを有している。また、バス１７は、ＣＰＵ１１、入力部１２、出力部１３、補助記憶装置１４、ＲＯＭ１５及びＲＡＭ１６を通信可能に接続する。
【００５９】
なお、このようなハードウェアの具体例としては、例えば、パーソナルコンピュータの他、サーバ装置やワークステーション等を例示できる。
【００６０】
＜プログラム構成＞
上述のように、プログラム領域１４ａ，１６ａには、本実施例の電子署名装置１００、検証装置２００、登録装置３００の各処理を実行するための各プログラムが格納される。電子署名プログラム、検証プログラム及び登録プログラムを構成する各プログラムは、単一のプログラム列として記載されていてもよく、また、少なくとも一部のプログラムが別個のモジュールとしてライブラリに格納されていてもよい。また、各プログラムが単体でそれぞれの機能を実現してもよいし、各プログラムがさらに他のライブラリを読み出して各機能を実現するものでもよい。
【００６１】
＜ハードウェアとプログラムとの協働＞
ＣＰＵ１１（図１３）は、読み込まれたＯＳ（Operating System）プログラムに従い、補助記憶装置１４のプログラム領域１４ａに格納されている上述のプログラムをＲＡＭ１６のプログラム領域１６ａに書き込む。同様にＣＰＵ１１は、補助記憶装置１４のデータ領域１４ｂに格納されている各種データを、ＲＡＭ１６のデータ領域１６ｂに書き込む。そして、このプログラムやデータが書き込まれたＲＡＭ１６上のアドレスがＣＰＵ１１のレジスタ１１ｃに格納される。ＣＰＵ１１の制御部１１ａは、レジスタ１１ｃに格納されたこれらのアドレスを順次読み出し、読み出したアドレスが示すＲＡＭ１６上の領域からプログラムやデータを読み出し、そのプログラムが示す演算を演算部１１ｂに順次実行させ、その演算結果をレジスタ１１ｃに格納していく。
【００６２】
前述の図３、５は、このようにＣＰＵ１１に上述のプログラムが読み込まれて実行されることにより構成される電子署名装置１００、検証装置２００の機能構成を例示したブロック図である。
【００６３】
ここで、記憶部１０３及び２０３は、補助記憶装置１４、ＲＡＭ１６、レジスタ１１ｃ、その他のバッファメモリやキャッシュメモリ等の何れか、あるいはこれらを併用した記憶領域に相当する。また、通信部１０１と、記憶部１０３と、制御部１０５と、生成元選択部１２０と、乱数生成部１３０と、公開鍵生成部１４０と、電子署名生成部１５０は、ＣＰＵ１１に電子署名プログラムを実行させることにより構成されるものである。また、通信部２０１と、記憶部２０３と、制御部２０５と、判定部２２０は、ＣＰＵ１１に検証プログラムを実行させることにより構成されるものである。
【００６４】
また、本形態の電子署名装置１００、検証装置２００及び登録装置３００は、各制御部１０５及び２０５の制御のもと各処理を実行する。
図１３を参照性説明したこの発明をコンピュータで実施する構成は、実施例２及び３にも適用できる。
【技術分野】
【０００１】
本発明は、電気通信システムで送信者の身元を確認する電子署名検証システム、電子署名装置、検証装置、その方法及びプログラムに関する。
【背景技術】
【０００２】
電子署名はメッセージｍに対して、公開鍵pkに対応する秘密鍵skを知る署名者が、メッセージｍに対して秘密鍵skを正しく使ったときにのみ計算できる値σを算出し、これを電子的な署名として用いるものである。正しく計算された電子署名は誰でも公開鍵pkを用いてその正当性を検証することが可能である。一方、秘密鍵skを知らないいかなる第三者も正当な電子署名σを算出することはできない。電子署名は電子現金やクレデンシャルシステムなど、様々な暗号プロトコルにおいて基本的な構成要素として利用されている。
【０００３】
電子署名は電子現金やクレデンシャルシステムなど、様々な暗号プロトコルにおいて基本的な構成要素として利用されている。特に、利用者のプライバシーを必要とする応用においては、ゼロ知識証明と組み合わせることにより、電子署名σを明かさないまま、あるメッセージに対する電子署名を保持しているという事実を任意の第三者に納得させるなど、高度な利用形態がある。例えば、非特許文献１のようにペアリング技術を用い、群の要素がある関係を満たすという事実を効率的に証明するゼロ知識証明が構成可能となった。これによって、電子署名σが効率的なバイリニアマップを持つ群の要素である、すなわち、σ∈Ｇである場合、前述のように、電子署名σを明かさないまま、正しい電子署名σを保持しているという事実を証明することが可能である。
【０００４】
例えば、非特許文献２記載の技術、いわゆる、CL-Signatureと言われる技術では、メッセージｍ∈Ｚqに対する電子署名σは３つの群要素(ａ，ｂ，ｃ)∈Ｇ３から構成されている。
【０００５】
しかしながら、CL-Signatureと言われる技術では、ランダムオラクルモデル等の理想化された構成要素を用いず、数論的な仮定のみによって安全性が証明できる既存の電子署名方法では、メッセージｍが群Ｇの要素ではないため、メッセージｍを秘匿した状態で、その秘匿したメッセージに対する正しい電子署名を保持していることを証明する、という応用には適さない。
メッセージｍが群Ｇの要素である場合にも、安全な電子署名方法として、上記のCL-Signatureを改良した方式が非特許文献３に示されている。それについて以下に簡単に説明する。
【０００６】
ｑを大きな素数とし、Ｇ１，Ｇ２，ＧＴをそれぞれ位数ｑの群とし、ｅを効率的に計算可能なバイリニアマップｅ：Ｇ１×Ｇ２→ＧＴとし、ｖ＝(ｑ，Ｇ１，Ｇ２，ＧＴ，ｅ)を公開パラメータとする。
【０００７】
署名者は、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択し、Ｚqに属する乱数ｒ、ｘ及びｙを生成し、Ｘ＝ｇ２ｘ、Ｙ＝ｇ２ｙとする。また、pk＝(ｖ、ｇ１、ｇ２、Ｘ、Ｙ）を公開鍵とし、sk＝(ｘ、ｙ)を秘密鍵とする。
【０００８】
メッセージｍ∈Ｇ１に対して、以下の５つの式
ａ１＝ｇ１ｒ (1)
ａ２＝ｍｒ (2)
ａ３＝ｇ１ｒｘｍｒｘｙ (3)
ａ４＝ｍｒｙ (4)
ａ５＝ｇ２ｒ (5)
を計算し、これら５つの値の組をメッセージｍに対する電子署名σ＝(ａ１，ａ２，ａ３，ａ４，ａ５)∈Ｇ１４×Ｇ２とする。
【０００９】
検証者は、与えられたメッセージ署名対(ｍ、σ)に対し、公開鍵pk及び電子署名σを用いて、以下の４つのペアリング等式が成り立つことを確認し、電子署名の真正性及び完全性を検証する。
【００１０】
e(ｇ１，ａ５)＝e(ａ１，ｇ２) (6)
e(ｍ，ａ５)＝e(ａ２，ｇ２) (7)
e(ａ２，Ｙ)＝e(ａ４，ｇ２) (8)
e(ａ３，ｇ２)＝e(ａ１ａ４，Ｘ) (9)
【００１１】
＜検証方法＞
式(6)は式(1)及び(5)を用いて、以下のように表すことができる。
e(ｇ１，ｇ２ｒ)＝e (ｇ１ｒ，ｇ２) (6)'
これが成立することにより、バイリニアマップの性質から、両辺中の検証装置に知らされていない乱数ｒが同一であることを確認することができる。同様に、式(7)は式(1)及び(2)を用いて、以下のように表すことができる。
e(ｍ，ｇ２ｒ)＝e(ｍｒ，ｇ２) (7)'
式(6)'でｒの同一性が確認されたので、式(7)'が成立することにより、受信したｍと署名の対象となったｍが同一であることを確認することができる。式(8)は式(2)、(4)、Ｙ＝ｇ２ｙを用いて、以下のように表すことができる。
e(ｍｒ，ｇ２ｙ)＝e(ｍｒｙ，ｇ２) (8)’
式(6)'と(7)'で乱数ｒの同一性とメッセージｍの同一性が確認されたので、式(8)'が成り立つ場合には、乱数ｙが正しいことが確認できる。式(9)は、式(1)、(3)、(4)、Ｘ＝ｇ２ｘを用いて、以下のように表すことができる。
e(ｇ１ｒｘｍｒｘｙ，ｇ２)＝e(ｇ１ｒｍｒｙ，ｇ２ｘ) (9)’
式(6)', (7)', (8)'で乱数ｒ、メッセージｍ、及び乱数ｙが正しいことが確認できたので、式(9)'が成り立つ場合には、乱数ｘが正しいことが確認できる。これらの処理により、電子署名σを作成できるのは、秘密鍵sk＝(ｘ，ｙ)を知っている署名者のみであることが確認できる。
【先行技術文献】
【非特許文献】
【００１２】
【非特許文献１】Jens Groth, Amit Sahai, "Efficient Non-interactive Proof Systems for Bilinear Groups", Advances in Cryptology - EUROCRYPT 2008, Springer Berlin / Heidelberg, June 3,2008, Volume 4965/2008, p415-432
【非特許文献２】Jan Camenisch, Anna Lysyanskaya, " Signature Schemes and Anonymous Credentials from Bilinear Maps", Advances in Cryptology - CRYPTO 2004, Springer Berlin / Heidelberg, 2004, Volume 3152/2004, p.56-72
【非特許文献３】Matthew Green, Susan Hohenberger, "Universally Composable Adaptive Oblivious Transfer", [online], The Johns Hoｐｋins University Information Security Institute, ［平成20年11月19日］, インターネット<URL:http://eprint.iacr.org/cgi-bin/getfile.pl?entry=2008/163&version=20080806:150034&file=163.pdf>
【発明の概要】
【発明が解決しようとする課題】
【００１３】
非特許文献３記載の電子署名検証方法及び装置では、電子署名を構成する要素の数が多く、電子署名長が長くなり、情報量及び通信量が多くなるという問題があった。また、検証時の計算量が多いという問題があった。本発明は、電子署名を構成する要素の数を少なくし、電子署名長が短く、情報量及び通信量が少ない電子署名検証方法及び装置を提供することを目的とし、また、検証時の計算量の少ない電子署名検証方法及び装置を提供することを目的とする。
【課題を解決するための手段】
【００１４】
この発明の第１の観点による電子署名検証システムにおいては、
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）とし、
前記電子署名装置は、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択部と、
Ｚqに属する乱数ｒ、ｘ及びｙを生成する乱数生成部と、
前記ｘ、ｙ、ｇ１及びｇ２が入力され、Ｘ'＝ｇ２ｘ、Ｙ'＝ｇ２ｙ、Ｙ＝ｇ１ｙを計算し、公開鍵pkをpk＝(ｖ，ｇ１，ｇ２，Ｘ'，Ｙ'，Ｙ)として生成する公開鍵生成部と、
前記ｇ１、ｇ２、ｒ、ｘ、ｙ及び平文ｍが入力され、
ｂ１＝ｍｒｙＹｒ、
ｂ３＝ｍｒｘｙＹｒｘ、
ｂ５＝ｇ２ｒｙ
を計算し、電子署名σ＝(ｂ１，ｂ３，ｂ５)を生成する電子署名生成部とを有す。
前記検証装置は、前記電子署名装置から前記電子署名σ及び平文ｍを受け、前記公開鍵pk、電子署名σ及び平文ｍを使って、
式(1)： e(ｂ１，ｇ２)＝e(ｍｇ１，ｂ５)
式(2)： e(ｂ３，ｇ２)＝e(ｂ１，Ｘ')
を計算し、式(1)と(2)の等式全てが成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定部を有する。
この発明の第２の観点による電子署名検証システムにおいては、
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）とし、
前記電子署名装置は、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択部と、
Ｚqに属するｎ個の乱数ｒi, 但し、i=1,…, n、と乱数ｘ及びｙを生成する乱数生成部と、
前記ｘ、ｙ、ｇ1及びｇ2が入力され、Ｘ'＝ｇ2x、Ｙ'＝ｇ2y、Ｙ＝ｇ1yを計算し、公開鍵pk＝(ｖ，ｇ1，ｇ2，Ｘ'，Ｙ'，Ｙ)を生成する公開鍵生成部と、
前記ｇ1、ｇ2、ｎ個のｒi、ｘ、ｙ及びｎ個の平文ｍiが入力され、i=1,…,nについて
ｂ1i＝ｍiriｙＹri、
ｂ3＝(Πni=1ｍiri)ｘｙ(Πni=1Ｙri)ｘ、
ｂ5i＝ｇ２riｙ
を計算し、電子署名σ＝(ｂ1i，ｂ３，ｂ5i)を生成する電子署名生成部とを有す。
前記検証装置は、前記電子署名装置から前記電子署名σ及びｎ個の平文ｍｉを受け、前記公開鍵pk、電子署名σ及びｎ個の平文ｍiを使って、
式(1)： e(ｂ1i，ｇ２)＝e(ｍiｇ１，ｂ5i)
式(2)： e(ｂ3，ｇ2)＝e(Πni=1ｂ1i，Ｘ')
を計算し、式(1)と(2)の等式全てが成立するか否かをi=1,…,nについて判定し、成立する場合には受理し、成立しない場合には拒否する判定部を有する。
この発明の第３の観点による電子署名検証システムにおいては、
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝(ｑ，Ｇ１，Ｇ２，ＧT，ｅ)とし、
前記電子署名装置は、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択部と、
Ｚqに属する乱数ｒ、ｘ及びｎ個の乱数ｙi、但し、i=1,…,n、を生成する乱数生成部と、
前記ｘ、ｙｉ、ｇ１及びｇ２が入力され、Ｘ'＝ｇ２ｘ、Ｙ'ｉ＝ｇ２ｙｉ、Ｙi＝ｇ1yiを計算し、公開鍵pk＝(ｖ，ｇ1，ｇ2，Ｘ'，Ｙ'i，Ｙi)を生成する公開鍵生成部と、
前記ｇ１、ｇ２、ｒ、ｘ、ｙｉ及びｎ個の平文ｍｉが入力され、
ｂ1i＝ｍiryiＹir、
ｂ3＝(Πni=1ｍiyi)rx(Πni=1Ｙi)rx、
ｂ5i＝ｇ2ryi
を計算し、電子署名σ＝(ｂ1i，ｂ３，ｂ5i)を生成する電子署名生成部とを有する。
前記検証装置は、前記電子署名装置から前記電子署名σ及びｎ個の平文ｍｉを受け、前記公開鍵pk、電子署名σ及びｎ個の平文ｍiを使って
式(1)： e(ｂ1i，ｇ2)＝e(ｍiｇ１，ｂ5i)
式(2)： e(ｂ3，ｇ2)＝e(Πni=1ｂ1i，Ｘ')
を計算し、式(1), (2)の等式全てがi=1,…,nについて成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定部を有する。
【発明の効果】
【００１５】
本発明の電子署名検証方法及び装置によれば、従来技術同様、真正性及び完全性を担保しながら、群の元を用いて電子署名を構成することができ、かつ、電子署名を構成する要素の数を少なくすることにより、電子署名長が短く、通信量が少なくすることができる。また、検証時の計算式の少なくすることにより、計算量を少なくすることができる。
【図面の簡単な説明】
【００１６】
【図１】実施例１における電子署名検証システムの構成例を示す図。
【図２】電子署名検証システム１のシーケンス図の一例を示す図。
【図３】電子署名装置１００の構成例を示す図。
【図４】電子署名装置１００の処理フローの一例を示す図。
【図５】検証装置２００の構成例を示す図。
【図６】検証装置２００の処理フローの一例を示す図。
【図７】この発明の実施例２による電子署名検証システムの構成例を示す図。
【図８】実施例２における電子署名装置の構成例を示す図。
【図９】実施例２における検証装置の構成例を示す図。
【図１０】実施例３における電子署名検証システムの構成例を示す図。
【図１１】実施例３における電子署名装置の構成例を示す図。
【図１２】実施例３における検証装置の構成例を示す図。
【図１３】実施例１における電子署名装置のハードウェア構成を例示したブロック図。
【発明を実施するための形態】
【００１７】
［発明の原理］
前述の非特許文献３の技術において、この発明では公開鍵として新たにＹ＝ｇ１ｙを加えpk＝(ｖ、ｇ１、ｇ２、Ｘ'，Ｙ'，Ｙ)とする。ＳＸＤＨ(asymmetric XDH)仮定を前提とし、その仮定の下ではＹ'＝ｇ２ｙとＹ＝ｇ１ｙとが公開されていたとしても互いに独立であり、互いの情報を一切漏らさない。更に、この発明では３つ要素の組(ｂ１、ｂ２、ｂ３) ∈Ｇ１２×Ｇ２、ただし、
ｂ１＝ｍｒｙＹｒ
ｂ３＝ｍｒｘｙＹｒｘ
ｂ５＝ｇ２ｒｙ
をメッセージｍに対する署名σとする。即ち署名σは
σ＝(ｍｒｙＹｒ，ｍｒｙｘＹｒｘ、ｇ２ｒｙ)
である。メッセージ署名対(ｍ、σ)に対する検証は、次の２つのペアリング等式、
e(ｂ１，ｇ２)＝e(ｍｇ１，ｂ５)
e(ｂ３、ｇ２)＝e(ｂ１、Ｘ')
が成立するかの判定による。
なお、ＳＸＤＨ仮定について述べる前にまずＸＤＨについて述べる。ＸＤＨはThe External Diffie-Hellman (XDH) assumptionの略であり、いわゆる楕円のペアリングなどが存在する場合に、以下の３つの性質を持つことを想定した仮定である。
・The discrete logarithm problem (DLP)→離散対数問題
・The computational Diffie-Hellman problem (CDH)→いわゆるＤＨ問題
・The computational co-Diffie-Hellman problem (co-DH)
上記のうち、co-DHとは以下のように双対の片方のグループの情報を与えられて、与えられたのとは別のグループのＤＨを計算する問題であり、これを解くのが難しいことを仮定している。具体的には、以下の通りである。
(G1; G2)上のThe co-Diffie-Hellman (co-DH) problemは：
G1, G2をそれぞれP1, P2により生成した位数Ｌの巡回群とする。(G1,G2)上のco-DH問題は(P1; aP1; P2)が与えられaP2を計算することである。
これを、ペアリングの双方のグループに対して仮定しているのがＳＸＤＨである。
【実施例１】
【００１８】
［電子署名検証システム１］
図１は、電子署名検証システム１の構成例を示す図である。図２は、電子署名検証システム１のシーケンス図の一例を示す図である。電子署名検証システム１は、登録装置３００と、電子署名装置１００と、検証装置２００からなる。
【００１９】
ｑを大きな素数とし、Ｇ１，Ｇ２，ＧＴを位数ｑの群とし、ｅを効率的に計算可能なバイリニアマップｅ：Ｇ１×Ｇ２→ＧＴとし、ｖ＝（ｑ，Ｇ１，Ｇ２，ＧＴ，ｅ）を公開パラメータとする。なお、ｇａとは、ｇ∈Ｇに対し、群Ｇで定義される演算をａ回行うことを意味する。バイリニアマップとしては、例えば、WeilペアリングやTateペアリング等が考えられる。
【００２０】
電子署名装置１００は、登録装置３００に対して、公開パラメータｖを要求する（Ｓ１０）。登録装置３００は、ｖを電子署名装置１００へ送る（Ｓ１２）。電子署名装置１００は、公開パラメータｖから公開鍵pkを生成し、登録装置３００へ送る（Ｓ１４）。登録装置３００は、公開鍵pkを登録及び公開する（Ｓ１６）。なお、署名の生成ごとに公開パラメータを要求しなくとも、記憶している公開パラメータを利用して公開鍵を生成してもよい。さらに、メッセージ（以下、平文とも呼ぶ）ｍ、公開鍵pk及び秘密鍵skを用いて、電子署名σを生成する。電子署名装置１００は、電子署名σ及び平文ｍを検証装置へ送る（Ｓ１８）。
【００２１】
検証装置２００は、電子署名σに対応する公開鍵pkを登録装置３００へ要求する（Ｓ２０）。登録装置３００は、公開鍵pkを検証装置２００へ送る（Ｓ２２）。検証装置２００は、電子署名σ、平文ｍ、公開鍵pkを用いて、改竄及び成りすまし等が行われていないか検証する（Ｓ２４）。以下、各装置及び各処理について詳細を説明する。
【００２２】
［登録装置３００］
登録装置３００は、公開パラメータｖ＝(ｑ、Ｇ１，Ｇ２，ＧＴ，ｅ)を登録及び公開している。例えば、登録装置３００は、信頼できる第三者等が管理し、図示してない通信部と、記憶部と、制御部を有する。登録装置３００は、通信部を介して、電子署名装置及び検証装置と通信する。通信部は、例えば、ＬＡＮアダプタ等により構成され、ＬＡＮやインターネット等からなる通信回線と接続される。但し、必ずしも通信部を有さずともよく、例えば、キーボード等の入力装置から公開パラメータを入力してもよいし、また、ＵＳＢメモリ等の可搬媒体に公開パラメータを記憶し、それを入力してもよい。以下、同様に各装置（電子署名装置及び検証装置）は送信部を有さずともよく、装置間のデータの入出力は、通信以外の方法であってもよい。記憶部は、公開パラメータ、公開鍵等を記憶する。なお、上記「登録」とは、記憶部に記憶することを意味してもよい。また、「公開」とは、利用者の求めに応じて、情報（例えば、公開パラメータ）を閲覧可能、または、取得可能とすることを意味する。制御部は、各処理を制御する。
【００２３】
［電子署名装置１００］
図３は、電子署名装置１００の構成例を示す図である。図４は、電子署名装置１００の処理フローの一例を示す図である。電子署名装置１００は、通信部１０１と、記憶部１０３と、制御部１０５と、生成元選択部１２０と、乱数生成部１３０と、公開鍵生成部１４０と、電子署名生成部１５０を有する。
【００２４】
＜制御部１０５及び通信部１０１＞
本実施例の電子署名装置１００は、制御部１０５の制御のもと各処理を実行する。電子署名装置１００は、登録装置３００から公開パラメータｖを受け取る。例えば、通信部１０１は、登録装置３００及び検証装置２００と通信を行い、登録装置３００から公開パラメータｖを受信する（Ｓ１０１）。以下、特に記述しなくとも、登録装置３００及び検証装置２００と通信する際には、通信部１０１を介して行われるものとする。
【００２５】
受信した公開パラメータｖを記憶部１０３に記憶する（Ｓ１０３）。また、特に示さない限り、入出力される各データや演算過程の各データは、逐一、記憶部１０３に格納・読み出され、各演算処理が進められる。但し、必ずしも記憶部１０３に記憶しなければならないわけではなく、各部間で直接データを受け渡してもよい。
【００２６】
＜生成元選択部１２０、乱数生成部１３０及び記憶部１０３＞
生成元選択部１２０は、公開パラメータｖ中の群Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する（Ｓ１２０）。生成元選択部１２０は、通信部１０１を介して、または、通信部１０１及び記憶部１０３を介して、公開パラメータｖを入力され、生成元ｇ１及びｇ２を公開鍵生成部１４０及び電子署名生成部１５０へ、出力する。乱数生成部１３０は、Ｚqに属する乱数ｒ、ｘ及びｙを生成して出力する（Ｓ１３０）。乱数生成部１３０は、乱数ｘ、ｙを公開鍵生成部１４０へ、乱数ｒ、ｘ、ｙを電子署名生成部１５０へ出力する。記憶部１０３は、乱数ｒ、ｘ及びｙが記憶され、特にｘ、ｙは秘密鍵sk＝(ｘ，ｙ)として秘密に記憶される（Ｓ１３３）。なお、秘密鍵skには、対応する公開鍵pkを含め、sk＝(pk，ｘ，ｙ)としてもよい。他の実施例においても同様である。公開鍵pkについての詳細は後述する。
【００２７】
＜公開鍵生成部１４０＞
公開鍵生成部１４０は、ｘ、ｙ、ｇ１及びｇ２が入力され、Ｘ'＝ｇ２ｘ、Ｙ'＝ｇ２ｙ、Ｙ＝ｇ１ｙを計算し、公開鍵pk＝（ｖ，ｇ１，ｇ２，Ｘ'，Ｙ'，Ｙ）を生成する（Ｓ１４０）。公開鍵pkは、通信部１０１を介して、登録装置３００へ送られる。なお、公開鍵pkには、利用した公開パラメータｖの代わりに、それを表す鍵情報ｉを含めpk＝(ｉ，ｇ１，ｇ２，Ｘ'，Ｙ'，Ｙ)としてもよい。この場合には、以下で説明する検証装置２００は、鍵情報ｉに基づいて、登録装置３００に対応する公開パラメータｖｉを要求する。また、登録装置３００の記憶している公開パラメータの中から対応する公開パラメータｖを特定することができる場合には、公開鍵pkに公開パラメータｖや、公開パラメータを表示する鍵情報ｉ等を含まなくともよく、検証装置２００は、平文ｍ及び電子署名σを受け付けた際に、登録装置３００に公開パラメータｖを要求する。
【００２８】
＜電子署名生成部１５０＞
電子署名生成部１５０は、ｇ１、ｇ２、ｒ、ｘ、ｙ及び平文ｍ∈Ｇ１が入力され、
ｂ１＝ｍｒｙＹｒ (11)
ｂ３＝Ｙｒｘｍｒｘｙ (12)
ｂ５＝ｇ２ｒｙ (13)
を計算し、平文ｍに対する電子署名σ＝(ｂ１，ｂ３，ｂ５)を生成する（Ｓ１５０）。なお、平文ｍ∈Ｚqであり、補助記憶装置やメモリ上のデータ等、もしくは、入力インターフェース、キーボード、マウス等から入力されるデータである。
【００２９】
電子署名装置１００は、公開鍵pkを登録装置３００へ、電子署名σ及び平文ｍを検証装置２００へ、送る。例えば、通信部１０１を介して、送信する（Ｓ１５３）。
【００３０】
このような構成とすることで、電子署名σを構成する要素の数を５つから３つに少なくすることができる。これにより、例えば、電子署名σの各要素を生成する演算量が同一の場合には、演算量を４０％軽減できる。また、例えば、電子署名σの各要素が同一の情報量を有している場合には、電子署名長を４０％短く作成することができる。これにより電子署名σに要する通信量を軽減することもできる。
【００３１】
［検証装置２００］
図５は、検証装置２００の構成例を示す。図６は、検証装置１００の処理フローの一例を示す図である。検証装置２００は、通信部２０１と、記憶部２０３と、制御部２０５と、判定部２２０を有する。
＜制御部２０５、通信部２０１及び記憶部２０３＞
本実施例の検証装置２００は、制御部２０５の制御のもと各処理を実行する。検証装置は、登録装置から公開鍵pkを、電子署名装置から電子署名σ及び平文ｍを、受け取る。例えば、通信部２０１は、登録装置３００及び検証装置１００と通信を行う。登録装置３００から公開鍵pkを受信する（Ｓ２０１）。電子署名装置１００から電子署名σ及び平文ｍを受信する（Ｓ２０２）。機能、構成等は、通信部１０１と同様である。記憶部２０３は、公開鍵pk、電子署名σ及び平文ｍが記憶される（Ｓ２０３）。
【００３２】
＜判定部２２０＞
判定部２２０は、以下の２つの等式が成立するか否かを判定する（Ｓ２２０）。成立する場合には受理し（Ｓ２２３）、成立しない場合には拒否する（Ｓ２２５）。
【００３３】
e(ｂ１，ｇ２)＝e(ｍｇ１，ｂ５) (14)
e(ｂ３，ｇ２)＝e(ｂ１，Ｘ') (15)
判定部２２０は、通信部２０１を介して、または、通信部２０１及び記憶部２０３を介して、公開鍵pk、署名σ及び平文ｍが入力される。以下、上記の式(15), (16)による検証について説明する。
【００３４】
＜検証方法の妥当性＞
式(14)は式(11)及び(13)、Ｙ＝ｇ１ｙを用いて、以下のように表すことができる。
e((ｍｇ１)ｒｙ，ｇ２)＝e(ｍｇ１，ｇ２ｒｙ) (14)’
これはバイリニアマップｅの性質を示しているので、式(14)が成立する場合には、署名者が署名生成時に使用した乱数ｒ及びｙと、検証者が受信した署名の生成に使用されたであろう乱数ｒ及びｙが同一であることを確認できる。
式(15)は式(12), (11)、及びＹ＝ｇ１ｙ，Ｘ'＝ｇ２ｘを用いて、以下のように表すことができる。
e((ｍｒｙＹｒ)ｘ，ｇ２)＝e(ｍｒｙＹｒ，ｇ２ｘ) (15)’
これもバイリニアマップｅの性質を示している。従って、式(14)の成立により乱数ｒとｙの正当性が確認できていれば、式(15)が成立することにより平文ｍと乱数ｘの正当性が確認できる。即ち、前述の従来技術と同様に、電子署名σを作成できるのは、秘密鍵sk＝(ｘ，ｙ)を知っている署名者のみであることが確認できる。このような構成とすることで、従来技術同様、真正性及び完全性を担保しながら、群の元を用いて電子署名を構成することができる。また、検証時の計算式を４つから２つに少なくすることにより、各計算式の計算量が同一の場合には、計算量を５０％軽減することができる。
【実施例２】
【００３５】
図７はこの発明の実施例２による電子署名検証システムの構成例を示し、図８はその電子署名装置の構成例を示し、図９は検証装置の構成例を示す。実施例２は実施例１における署名対象である平文ｍが複数の場合にも対処可能にしたものであり、実施例１と異なる部分についてのみ説明する。平文ｍｉ(ｉ＝1, …, ｎ)の数ｎは１以上の整数である。ｎ＝１のときは実質的に実施例１と同じになるが、実施例２ではｎが１のみならず２以上の値にも対応できるように構成されている。
【００３６】
［電子署名検証システム１０００］
図７に示す量に、電子署名検証システム１０００は、登録装置３００と、電子署名装置１１００と、検証装置１２００からなる。電子署名装置１１００は、ｎ個の平文ｍｉに対し電子署名を生成するために、まず登録装置３００に対して、公開パラメータｖ＝(ｑ、Ｇ１，Ｇ２，ＧＴ，ｅ)を要求する。登録装置３００は、ｖを電子署名装置１００へ送る。電子署名装置１１００は、公開パラメータｖから公開鍵pk＝(ｖ、ｇ１，ｇ２，Ｘ'，Ｙ'，Ｙ)を生成し、登録装置３００へ送る。さらに、ｎ個の平文ｍｉ、公開鍵pk及び秘密鍵skを用いて、電子署名σを生成する。電子署名装置１１００は、電子署名σ及び平文ｍｉを検証装置１２００へ送る。
【００３７】
検証装置１２００は、電子署名σに対応する公開鍵pkを登録装置３００へ要求する。登録装置３００は、ｐｋを検証装置１２００へ送る。検証装置１２００は、電子署名σ、平文ｍｉ、公開鍵pkを用いて、改竄及び成りすまし等が行われていないか検証する。以下、電子署名装置１１００及び検証装置１２００について詳細を説明する。
【００３８】
［電子署名装置１１００］
図８に示すように、電子署名装置１１００は、通信部１０１と、記憶部１０３と、制御部１０５と、生成元選択部１２０と、乱数生成部１１３０と、公開鍵生成部１４０と、電子署名生成部１１５０を有する。
【００３９】
＜乱数生成部１１３０及び記憶部１０３＞
乱数生成部１１３０は、Ｚqに属するｎ個の乱数ｒｉ(ｉ=1, …, ｎ)、ｘ及びｙを生成して出力する。つまり、本実施例においては、ｎ個の平文ｍｉに対応するｎ個の乱数ｒｉを生成する。乱数生成部１１３０は、乱数ｘ、ｙを公開鍵生成部１４０へ、ｎ個の乱数ｒｉとｘ、ｙを電子署名生成部１１５０へ出力する。記憶部１０３は、乱数ｒｉ、ｘ及びｙが記憶される。
＜公開鍵生成部１４０＞
公開鍵生成部１４０はＸ'＝ｇ２ｘ、Ｙ'＝ｇ２ｙ、Ｙ＝ｇ１ｙを計算し、公開鍵pk＝(ｖ、ｇ１、ｇ２、Ｘ'、Ｙ'、Ｙ)を生成する。
【００４０】
＜電子署名生成部１１５０＞
電子署名生成部１１５０は、ｇ１、ｇ２、ｒｉ、ｘ、ｙ及び平文ｍｉ∈Ｇ１が入力され、
ｂ1i＝ｍiriｙＹri (16)
ｂ3＝(Πni=1ｍiri)ｘｙ(Πni=1Ｙri)ｘ (17)
ｂ5i＝ｇ2riｙ (18)
を計算し、電子署名σ＝(ｂ1i，ｂ3，ｂ5i)(i=1, …, n)を生成する。なお、式(16), (17), (18)において、riとは、上記乱数ｒｉのことを意味する。電子署名生成部１１５０は、生成元選択部１２０から生成元ｇ１、ｇ２を、乱数生成部１１３０から乱数ｒｉ、ｘ、ｙを、さらに平文ｍｉを入力され、電子署名σを出力する。
【００４１】
電子署名装置１１００は、公開鍵pkを登録装置３００へ、電子署名σ及び平文ｍｉを検証装置１２００へ、送る。例えば、通信部１０１を介して、送信する。
【００４２】
このような構成とすることで、実施例１同様、電子署名σを構成する要素の数を５つから３つに少なくすることができ、実施例１と同様の効果を得ることができる。さらに、１個又は複数の平文ｍｉ(ｉ＝１，…，ｎ)に対して電子署名σを生成することができるため、実施例１の方法により複数の平文に対し、複数の電子署名を作成するのに比べ、処理を軽減することができる。また、電子署名の情報量、通信量を小さくすることができる。
【００４３】
［検証装置１２００］
図９に示すように、検証装置１２００は、通信部２０１と、記憶部２０３と、制御部２０５と、判定部１２２０を有する。
【００４４】
＜判定部１２２０＞
判定部１２２０は、以下の等式全てがｉ＝１，…，ｎの全てについて成立するか否かを判定する。成立する場合には受理し、成立しない場合には拒否する。
e(ｂ1i，ｇ２)＝e(ｍiｇ１，ｂ5i) (19)
e(ｂ３，ｇ２)＝e(Πni=1ｂ1i，Ｘ') (20)
判定部１２２０は、通信部２０１を介して、または、通信部２０１及び記憶部２０３を介して、公開鍵pk、署名σ及び平文ｍｉが入力される。
【００４５】
このような構成とすることによって、検証時の計算式を４つから２つに少なくし、実施例１同様の効果が得られる。さらに、等式の両辺を乗算にてまとめることにより、実施例１の方法により複数の電子署名を検証するのに比べ、処理を軽減することができる。
式(19), (20)による検証の妥当性は実施例１の場合と同様に示すことができる。
【実施例３】
【００４６】
図１０はこの発明の第３実施例による電子署名検証システムの構成例を示し、図１１はその電子署名装置の構成例を示し、図１２は検証装置の構成例を示す。上述の実施例２ではｎ個の平文ｍi(i=1,…,n、ｎは１以上の整数)に対応してｎ個の乱数ｒiを使用したが、以下に説明するこの実施例３では、実施例１と同様に乱数ｒは１つとし、ｎ個の平文に対応してｎ個の乱数ｙiを使用する。ｎ＝１の場合は実質的に実施例１と同じになるが、実施例３ではｎ＝１の場合のみならず、ｎが２以上の場合にも対応できるように構成されている。
【００４７】
［電子署名検証システム２０００］
図１０に示すように、実施例３による電子署名検証システム２０００は、登録装置３００と、電子署名装置２１００と、検証装置２２００からなる。電子署名装置２１００は、複数の平文ｍｉを検証装置２２００に送る際に、電子署名σを添付するために、登録装置３００に対して、公開パラメータｖを要求する。登録装置３００は、ｖを電子署名装置１００へ送る。電子署名装置２１００は、公開パラメータｖから公開鍵pkを生成し、登録装置３００へ送る。さらに、平文ｍｉ、公開鍵pk及び秘密鍵skを用いて、電子署名σを生成する。電子署名装置２１００は、電子署名σ及び平文ｍｉを検証装置２２００へ送る。
【００４８】
検証装置２２００は、電子署名σに対応する公開鍵pkを登録装置３００へ要求する。登録装置３００は、pkを検証装置２２００へ送る。検証装置２２００は、電子署名σ、平文ｍｉ、公開鍵pkを用いて、改竄及び成りすまし等が行われていないか検証する。以下、電子署名装置２１００及び検証装置２２００について詳細を説明する。
【００４９】
［電子署名装置２１００］
図１１に示すように、電子署名装置２１００は、通信部１０１と、記憶部２１０３と、制御部１０５と、生成元選択部１２０と、乱数生成部２１３０と、公開鍵生成部２１４０と、電子署名生成部２１５０を有する。
【００５０】
＜乱数生成部２１３０及び記憶部２１０３＞
乱数生成部２１３０は、Ｚqに属する乱数ｒ、ｘ及びｙｉを生成して出力する。つまり、本実施例においては、複数の平文ｍｉに対応する複数の乱数ｙｉを生成する。乱数生成部２１３０は、乱数ｘ、ｙｉを公開鍵生成部２１４０へ、乱数ｒ、ｘ、ｙｉを電子署名生成部２１５０へ出力する。記憶部２１０３は、乱数ｒ、ｘ及びｙｉが記憶され、特にｘ、ｙｉは秘密鍵sk＝(ｘ，ｙi)として秘密に記憶される。
【００５１】
＜公開鍵生成部２１４０＞
公開鍵生成部２１４０は、ｘ、ｙｉ、及びｇ２が入力され、Ｘ'＝ｇ２ｘ、Ｙｉ'＝ｇ２ｙi、Ｙi＝ｇ1yi(但し、yiは、ｙｉを表す）を計算し、公開鍵pk＝(ｖ，ｇ１，ｇ２，Ｘ'，Ｙi'，Ｙｉ)を生成する。
【００５２】
＜電子署名生成部２１５０＞
電子署名生成部２１５０は、ｇ１、ｇ２、ｒ、ｘ、ｙｉ及び平文ｍｉ∈Ｇ１が入力され、
ｂ1i＝ｍiｒyiＹiｒ (21)
ｂ３＝(Πni=1ｍiyi)ｒｘ(Πni=1Ｙi)ｒｘ (22)
ｂ5i＝ｇ2ｒyi (23)
を計算し、電子署名σ＝(ｂ1i，ｂ３，ｂ5i)を生成する。なお、式(21)〜(23)において、yiとは、上記乱数ｙｉのことを意味する。電子署名生成部２１５０は、生成元選択部１２０から生成元ｇ１、ｇ２を、乱数生成部２１３０から乱数ｒ、ｘ、ｙｉを、さらに平文ｍｉを入力され、電子署名σを出力する。
このような構成とすることで、実施例２と同様の効果が得られる。
【００５３】
［検証装置２２００］
図１２に示すように、検証装置２２００は、通信部２０１と、記憶部２０３と、制御部２０５と、判定部２２２０を有する。
【００５４】
＜判定部２２２０＞
判定部２２２０は、以下の等式全てが成立するか否かを判定する。成立する場合には受理し、成立しない場合には拒否する。
【００５５】
e(ｂ1i，ｇ２)＝e(ｍiｇ１，ｂ5i) (24)
e(ｂ３，ｇ２)＝e(Πni=1ｂ1i，Ｘ'） (25)
式(24), (25)による検証の妥当性は実施例１の場合と同様に示すことができる。
このような構成とすることによって、実施例２と同様の効果が得られる。
【００５６】
＜ハードウェア構成＞
図１３は、図１に示した実施例１における電子署名装置１００のハードウェア構成を例示したブロック図である。検証装置２００及び登録装置３００も同様の構成を有する。
【００５７】
図１３に例示するように、この例の電子署名装置１００、検証装置２００、登録装置３００は、それぞれＣＰＵ（Central Processing Unit）１１、入力部１２、出力部１３、補助記憶装置１４、ＲＯＭ（Read Only Memory）１５、ＲＡＭ（Random Access Memory）１６及びバス１７を有している。
【００５８】
この例のＣＰＵ１１は、制御部１１ａ、演算部１１ｂ及びレジスタ１１ｃを有し、レジスタ１１ｃに読み込まれた各種プログラムに従って様々な演算処理を実行する。また、入力部１２は、データが入力される入力インターフェース、キーボード、マウス等であり、出力部１３は、データが出力される出力インターフェース等である。補助記憶装置１４は、例えば、ハードディスク、ＭＯ（Magneto-Optical disc）、半導体メモリ等であり、電子署名装置１００、検証装置２００及び登録装置３００としてコンピュータを機能させるためのプログラムが格納されるプログラム領域１４ａ及び各種データが格納されるデータ領域１４ｂを有している。また、ＲＡＭ１６は、ＳＲＡＭ (Static Random Access Memory)、ＤＲＡＭ (Dynamic Random Access Memory)等であり、上記のプログラムが格納されるプログラム領域１６ａ及び各種データが格納されるデータ領域１６ｂを有している。また、バス１７は、ＣＰＵ１１、入力部１２、出力部１３、補助記憶装置１４、ＲＯＭ１５及びＲＡＭ１６を通信可能に接続する。
【００５９】
なお、このようなハードウェアの具体例としては、例えば、パーソナルコンピュータの他、サーバ装置やワークステーション等を例示できる。
【００６０】
＜プログラム構成＞
上述のように、プログラム領域１４ａ，１６ａには、本実施例の電子署名装置１００、検証装置２００、登録装置３００の各処理を実行するための各プログラムが格納される。電子署名プログラム、検証プログラム及び登録プログラムを構成する各プログラムは、単一のプログラム列として記載されていてもよく、また、少なくとも一部のプログラムが別個のモジュールとしてライブラリに格納されていてもよい。また、各プログラムが単体でそれぞれの機能を実現してもよいし、各プログラムがさらに他のライブラリを読み出して各機能を実現するものでもよい。
【００６１】
＜ハードウェアとプログラムとの協働＞
ＣＰＵ１１（図１３）は、読み込まれたＯＳ（Operating System）プログラムに従い、補助記憶装置１４のプログラム領域１４ａに格納されている上述のプログラムをＲＡＭ１６のプログラム領域１６ａに書き込む。同様にＣＰＵ１１は、補助記憶装置１４のデータ領域１４ｂに格納されている各種データを、ＲＡＭ１６のデータ領域１６ｂに書き込む。そして、このプログラムやデータが書き込まれたＲＡＭ１６上のアドレスがＣＰＵ１１のレジスタ１１ｃに格納される。ＣＰＵ１１の制御部１１ａは、レジスタ１１ｃに格納されたこれらのアドレスを順次読み出し、読み出したアドレスが示すＲＡＭ１６上の領域からプログラムやデータを読み出し、そのプログラムが示す演算を演算部１１ｂに順次実行させ、その演算結果をレジスタ１１ｃに格納していく。
【００６２】
前述の図３、５は、このようにＣＰＵ１１に上述のプログラムが読み込まれて実行されることにより構成される電子署名装置１００、検証装置２００の機能構成を例示したブロック図である。
【００６３】
ここで、記憶部１０３及び２０３は、補助記憶装置１４、ＲＡＭ１６、レジスタ１１ｃ、その他のバッファメモリやキャッシュメモリ等の何れか、あるいはこれらを併用した記憶領域に相当する。また、通信部１０１と、記憶部１０３と、制御部１０５と、生成元選択部１２０と、乱数生成部１３０と、公開鍵生成部１４０と、電子署名生成部１５０は、ＣＰＵ１１に電子署名プログラムを実行させることにより構成されるものである。また、通信部２０１と、記憶部２０３と、制御部２０５と、判定部２２０は、ＣＰＵ１１に検証プログラムを実行させることにより構成されるものである。
【００６４】
また、本形態の電子署名装置１００、検証装置２００及び登録装置３００は、各制御部１０５及び２０５の制御のもと各処理を実行する。
図１３を参照性説明したこの発明をコンピュータで実施する構成は、実施例２及び３にも適用できる。
【特許請求の範囲】
【請求項１】
電子署名装置と、検証装置とを含む電子署名検証システムにおいて、
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）とし、
前記電子署名装置は、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択部と、
Ｚqに属する乱数ｒ、ｘ及びｙを生成する乱数生成部と、
前記ｘ、ｙ、ｇ１及びｇ２が入力され、Ｘ'＝ｇ２ｘ、Ｙ'＝ｇ２ｙ、Ｙ＝ｇ１ｙを計算し、公開鍵pkをpk＝(ｖ，ｇ１，ｇ２，Ｘ'，Ｙ'，Ｙ)として生成する公開鍵生成部と、
前記ｇ１、ｇ２、ｒ、ｘ、ｙ及び平文ｍが入力され、
ｂ１＝ｍｒｙＹｒ、
ｂ３＝ｍｒｘｙＹｒｘ、
ｂ５＝ｇ２ｒｙ
を計算し、電子署名σ＝(ｂ１，ｂ３，ｂ５)を生成する電子署名生成部と、を有し、
前記検証装置は、前記電子署名装置から前記電子署名σ及び平文ｍを受け、前記公開鍵pk、電子署名σ及び平文ｍを使って、
式(1)： e(ｂ１，ｇ２)＝e(ｍｇ１，ｂ５)
式(2)： e(ｂ３，ｇ２)＝e(ｂ１，Ｘ')
を計算し、式(1)と(2)の等式全てが成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定部を有することを特徴とする電子署名検証システム。
【請求項２】
電子署名装置と、検証装置とを含む電子署名検証システムにおいて、
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）とし、
前記電子署名装置は、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択部と、
Ｚqに属する１以上のｎ個の乱数ｒi, 但し、i=1,…, n、と乱数ｘ及びｙを生成する乱数生成部と、
前記ｘ、ｙ、ｇ1及びｇ2が入力され、Ｘ'＝ｇ2x、Ｙ'＝ｇ2y、Ｙ＝ｇ1yを計算し、公開鍵pk＝(ｖ，ｇ1，ｇ2，Ｘ'，Ｙ'，Ｙ)を生成する公開鍵生成部と、
前記ｇ1、ｇ2、ｎ個のｒi、ｘ、ｙ及びｎ個の平文ｍiが入力され、i=1,…,nについて
ｂ1i＝ｍiriｙＹri、
ｂ3＝(Πni=1ｍiri)ｘｙ(Πni=1Ｙri)ｘ、
ｂ5i＝ｇ２riｙ
を計算し、電子署名σ＝(ｂ1i，ｂ３，ｂ5i)を生成する電子署名生成部と、を有し、
前記検証装置は、前記電子署名装置から前記電子署名σ及びｎ個の平文ｍｉを受け、前記公開鍵pk、電子署名σ及びｎ個の平文ｍiを使って、
式(1)： e(ｂ1i，ｇ２)＝e(ｍiｇ１，ｂ5i)
式(2)： e(ｂ3，ｇ2)＝e(Πni=1ｂ1i，Ｘ')
を計算し、式(1)と(2)の等式全てが成立するか否かをi=1,…,nについて判定し、成立する場合には受理し、成立しない場合には拒否する判定部を有することを特徴とする電子署名検証システム。
【請求項３】
電子署名装置と、検証装置からなる電子署名検証システムにおいて、
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝(ｑ，Ｇ１，Ｇ２，ＧT，ｅ)とし、
前記電子署名装置は、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択部と、
Ｚqに属する乱数ｒ、ｘ及び１以上のｎ個の乱数ｙi、但し、i=1,…,n、を生成する乱数生成部と、
前記ｘ、ｙｉ、ｇ１及びｇ２が入力され、Ｘ'＝ｇ２ｘ、Ｙ'ｉ＝ｇ２ｙｉ、Ｙi＝ｇ1yiを計算し、公開鍵pk＝(ｖ，ｇ1，ｇ2，Ｘ'，Ｙ'i，Ｙi)を生成する公開鍵生成部と、
前記ｇ１、ｇ２、ｒ、ｘ、ｙｉ及びｎ個の平文ｍｉが入力され、
ｂ1i＝ｍiryiＹir、
ｂ3＝(Πni=1ｍiyi)rx(Πni=1Ｙi)rx、
ｂ5i＝ｇ2ryi
を計算し、電子署名σ＝(ｂ1i，ｂ３，ｂ5i)を生成する電子署名生成部と、を有し、
前記検証装置は、前記電子署名装置から前記電子署名σ及びｎ個の平文ｍｉを受け、前記公開鍵pk、電子署名σ及びｎ個の平文ｍiを使って
式(1)： e(ｂ1i，ｇ2)＝e(ｍiｇ１，ｂ5i)
式(2)： e(ｂ3，ｇ2)＝e(Πni=1ｂ1i，Ｘ')
を計算し、式(1), (2)の等式全てがi=1,…,nについて成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定部を有することを特徴とする電子署名検証システム。
【請求項４】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）とし、
Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択部と、
Ｚqに属する乱数ｒ、ｘ及びｙを生成する乱数生成部と、
前記ｘ、ｙ、ｇ１及びｇ２が入力され、Ｘ'＝ｇ2ｘ、Ｙ'＝ｇ2y、Ｙ＝ｇ1yを計算し、公開鍵pk＝(ｖ，ｇ１，ｇ２，Ｘ'，Ｙ'，Ｙ)を生成する公開鍵生成部と、
前記ｇ１、ｇ２、ｒ、ｘ、ｙ及び平文ｍが入力され、
ｂ1＝ｍryＹｒ、
ｂ３＝ｍrxyＹrx、
ｂ５＝ｇ2ry
を計算し、電子署名σ＝(ｂ1，ｂ3，ｂ5)を生成する電子署名生成部と、
を有し、前記電子署名σ及び平文ｍを検証装置へ送ることを特徴とする電子署名装置。
【請求項５】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）とし、
Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択部と、
Ｚqに属する１以上のｎ個の乱数ｒi、但し、i=1,…,n、及び乱数ｘとｙを生成する乱数生成部と、
前記ｘ、ｙ、ｇ１及びｇ２が入力され、Ｘ'＝ｇ２ｘ、Ｙ'＝ｇ２ｙ、Ｙ＝ｇ1yを計算し、公開鍵pk＝(ｖ、ｇ1、ｇ2、Ｘ'，Ｙ'，Ｙ)を生成する公開鍵生成部と、
前記ｇ１、ｇ２、ｒｉ、ｘ、ｙ及びｎ個の平文ｍｉが入力され、
ｂ1i＝ｍiriyＹri、
ｂ３＝(Πni=1ｍiri)xy(Πni=1Ｙri)ｘ、
ｂ5i＝ｇ2riｙ
を計算し、電子署名σ＝(ｂ1i，ｂ３，ｂ5i)を生成する電子署名生成部と、
を有し、電子署名σ及びｎ個の平文ｍｉを検証装置へ送ることを特徴とする電子署名装置。
【請求項６】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）とし、
Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択部と、
Ｚqに属する乱数ｒ、ｘと１以上のｎ個の乱数ｙi、但しi=1,…,n、を生成する乱数生成部と、
前記ｘ、ｙ、ｇ１及びｇ２が入力され、Ｘ'＝ｇ2x、Ｙi'＝ｇ2yi、Ｙi＝ｇ1yiを計算し、公開鍵pk＝(ｖ、ｇ1、ｇ2、Ｘ'，Ｙi'，Ｙi)を生成する公開鍵生成部と、
前記ｇ１、ｇ２、ｒ、ｘ、ｎ個のｙi及びｎ個の平文ｍｉが入力され、
ｂ1i＝ｍiryiＹir、
ｂ３＝(Πni=1ｍiyi)rx(Πni=1Ｙi)rx、
ｂ5i＝ｇ2ryi
を計算し、電子署名σ＝(ｂ1i，ｂ３，ｂ5i)を生成する電子署名生成部と、
を有し、電子署名σ及びｎ個の平文ｍｉを検証装置へ送ることを特徴とする電子署名装置。
【請求項７】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、ｇ1及びｇ2、をそれぞれＧ，Ｇの生成元とし、公開パラメータｖをｖ＝(ｑ，Ｇ1，Ｇ2，ＧT，ｅ)とし、公開鍵pkをpk＝(ｖ，ｇ1，ｇ2，Ｘ'，Ｙ'，Ｙ)とし、Ｘ'＝ｇ2x、Ｙ'＝ｇ2y、Ｙ＝ｇ1yとし、ｘ、ｙをＺqに属する乱数とし、
電子署名装置から電子署名σ＝(ｂ1，ｂ3，ｂ5)及び平文ｍを受け、公開鍵pk、電子署名σ及び平文ｍを使って、
(1) e(ｂ1，ｇ2)＝e(ｍｇ1，ｂ5)
(2) e(ｂ3，ｇ2)＝e(ｂ1，Ｘ')
を計算し、式(1), (2)の等式全てが成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定部を有することを特徴とする検証装置。
【請求項８】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、ｇ1及びｇ2、をそれぞれＧ，Ｇの生成元とし、公開パラメータｖをｖ＝(ｑ，Ｇ1，Ｇ2，ＧT，ｅ)とし、公開鍵pkをpk＝(ｖ，ｇ1，ｇ2，Ｘ'，Ｙ'，Ｙ)とし、Ｘ'＝ｇ2x、Ｙ'＝ｇ2y、Ｙ＝ｇ1yとし、ｘ、ｙをＺqに属する乱数とし、
電子署名装置から電子署名σ＝(ｂ1i，ｂ3，ｂ5i)及び１以上のｎ個の平文ｍｉ、但し、i=1,…,n、を受け、公開鍵pk、電子署名σ及びｎ個の平文ｍｉを使って、
(1) e(ｂ1i，ｇ2)＝e(ｍiｇ１，ｂ5i)
(2) e(ｂ3，ｇ2)＝e(Πni=1ｂ1i，Ｘ')
を計算し、式(1), (2)の等式全てがi=1,…,nについて成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定部を有することを特徴とする検証装置。
【請求項９】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、ｇ1及びｇ2、をそれぞれＧ，Ｇの生成元とし、公開パラメータｖをｖ＝(ｑ，Ｇ1，Ｇ2，ＧT，ｅ)とし、公開鍵pkをpk＝(ｖ，ｇ1，ｇ2，Ｘ'，Ｙi'，Ｙi)とし、Ｘ'＝ｇ2x、Ｙi'＝ｇ2yi、Ｙi＝ｇ1yiとし、ｘ、ｙiをＺqに属する乱数とし、
電子署名装置から電子署名σ＝(ｂ1i，ｂ3，ｂ5i)及び１以上のｎ個の平文ｍｉを受け、公開鍵pk、電子署名σ及びｎ個の平文ｍｉを使って、
(1) e(ｂ1i，ｇ2)＝e(ｍiｇ１，ｂ5i)
(2) e(ｂ3，ｇ2)＝e(Πni=1ｂ1i，Ｘ')
を計算し、式(1), (2)の等式全てがi=1,…,nについて成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定部を有することを特徴とする検証装置。
【請求項１０】
電子署名装置と、検証装置を用いる電子署名検証方法であって、
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）として、 前記電子署名装置が、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択ステップと、
前記電子署名装置が、Ｚqに属する乱数ｒ、ｘ及びｙを生成する乱数生成ステップと、
前記電子署名装置が、前記ｘ、ｙ、ｇ１及びｇ２を用いて、Ｘ'＝ｇ２ｘ、Ｙ'＝ｇ２ｙ、及びＹ＝ｇ1yを計算し、公開鍵pk＝(ｖ、ｇ1、ｇ2、Ｘ'，Ｙ'，Ｙ)を生成して公開するステップと、
前記電子署名装置が、前記ｇ１、ｇ２、ｒｉ、ｘ、ｙ及び平文ｍを用いて、
ｂ1＝ｍryＹｒ、
ｂ3＝ｍryxＹrx、
ｂ5＝ｇ2ry
を計算し、電子署名σ＝(ｂ1，ｂ3，ｂ5)を生成する電子署名生成ステップと、
前記検証装置が、前記公開鍵pkと、前記電子署名装置から受け取った前記電子署名σ及び平文ｍとを使って
前記検証装置が、
式(1)： e(ｂ1，ｇ2)＝e(ｍｇ1，ｂ5)
式(2)： e(ｂ3，ｇ2)＝e(ｂ1，Ｘ')
を計算し、式(1), (2)の等式全てが成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定ステップを有する、
ことを特徴とする電子署名検証方法。
【請求項１１】
電子署名装置と、検証装置を用いる電子署名検証方法であって、
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）として、 前記電子署名装置が、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択ステップと、
前記電子署名装置が、Ｚqに属する１以上のｎ個の乱数ｒi、但し、i=1,…,ｎであり、ｘ及びｙを生成する乱数生成ステップと、
前記電子署名装置が、前記ｘ、ｙ、ｇ１及びｇ２を用いて、Ｘ'＝ｇ２ｘ、Ｙ'＝ｇ２ｙ、及びＹ＝ｇ1yを計算し、公開鍵pk＝(ｖ、ｇ1、ｇ2、Ｘ'，Ｙ'，Ｙ)を生成して公開するステップと、
前記電子署名装置が、前記ｇ１、ｇ２、ｎ個のｒｉ、ｘ、ｙ及びｎ個の平文ｍｉを用いて、
ｂ1i＝ｍiriyＹri、
ｂ3＝(Πni=1ｍiri)yx(Πni=1Ｙri)x、
ｂ5i＝ｇ2riy
を計算し、電子署名σ＝(ｂ1i，ｂ3，ｂ5i)を生成する電子署名生成ステップと、
前記検証装置が、前記公開鍵pkと、前記電子署名装置から受け取った前記電子署名σ及びｎ個の平文ｍｉとを使って
前記検証装置が、
式(1)： e(ｂ1i，ｇ2)＝e(ｍiｇ1，ｂ5i)
式(2)： e(ｂ3，ｇ2)＝e(Πni=1ｂ1i，Ｘ')
を計算し、式(1), (2)の等式全てがi=1,…,nについて成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定ステップを有する、
ことを特徴とする電子署名検証方法。
【請求項１２】
電子署名装置と、検証装置を用いる電子署名検証方法であって、
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）として、 前記電子署名装置が、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択ステップと、
前記電子署名装置が、Ｚqに属する乱数ｒ、ｘ及び１以上のｎ個の乱数ｙi、但し、i=1,…,n、を生成する乱数生成ステップと、
前記電子署名装置が、前記ｘ、ｙi、ｇ１及びｇ２を用いて、Ｘ'＝ｇ2x、Ｙi'＝ｇ2yi、及びＹi＝ｇ1yiを計算し、公開鍵pk＝(ｖ、ｇ1、ｇ2、Ｘ'，Ｙi'，Ｙi)を生成して公開するステップと、
前記電子署名装置が、前記ｇ１、ｇ２、ｒ、ｘ、ｎ個のｙi及びｎ個の平文ｍｉを用いて、
ｂ1i＝ｍiryiＹｒ、
ｂ3＝(Πni=1ｍiyi)rx(Πni=1Ｙi)rx、
ｂ5i＝ｇ2ryi
を計算し、電子署名σ＝(ｂ1i，ｂ3，ｂ5i)を生成する電子署名生成ステップと、
前記検証装置が、前記公開鍵pkと、前記電子署名装置から受け取った前記電子署名σ及びｎ個の平文ｍｉとを使って
前記検証装置が、
式(1)： e(ｂ1i，ｇ2)＝e(ｍiｇ1，ｂ5i)
式(2)： e(ｂ3，ｇ2)＝e(Πni=1ｂ1i，Ｘ')
を計算し、式(1), (2)の等式全てがi=1,…,nについて成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定ステップを有する、
ことを特徴とする電子署名検証方法。
【請求項１３】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）として、 前記電子署名装置が、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択ステップと、
前記電子署名装置が、Ｚqに属する乱数ｒ、ｘ及びｙを生成する乱数生成ステップと、
前記電子署名装置が、前記ｘ、ｙ、ｇ1及びｇ2を用いて、Ｘ'＝ｇ2x、Ｙ'＝ｇ2y,、Ｙ＝ｇ1yを計算し、公開鍵pk＝(ｖ、ｇ1，ｇ2，Ｘ'，Ｙ'，Ｙ)を生成する公開鍵生成ステップと、
前記電子署名装置が、前記ｇ１、ｇ２、ｒｉ、ｘ、ｙ及び平文ｍを用いて、
ｂ1＝ｍryＹｒ、
ｂ3＝ｍryxＹrx、
ｂ5＝ｇ2ry
を計算し、電子署名σ＝(ｂ1，ｂ3，ｂ5)を生成する電子署名生成ステップと、
を有する電子署名方法。
【請求項１４】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）として、 前記電子署名装置が、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択ステップと、
前記電子署名装置が、Ｚqに属する１以上のｎ個の乱数ｒｉ、但し、i=1,…,n、と乱数ｘ及びｙを生成する乱数生成ステップと、
前記電子署名装置が、前記ｘ、ｙ、ｇ1及びｇ2を用いて、Ｘ'＝ｇ2x、Ｙ'＝ｇ2y,、Ｙ＝ｇ1yを計算し、公開鍵pk＝(ｖ、ｇ1，ｇ2，Ｘ'，Ｙ'，Ｙ)を生成する公開鍵生成ステップと、
前記電子署名装置が、前記ｇ１、ｇ２、ｒｉ、ｘ、ｙ及びｎ個の平文ｍｉを用いて、
ｂ1i＝ｍiriyＹｒｉ、
ｂ3＝(Πni=1ｍiri)yx(Πni=1Ｙri)x、
ｂ5i＝ｇ2riy
を計算し、電子署名σ＝(ｂ1i，ｂ3，ｂ5i)を生成する電子署名生成ステップと、
を有する電子署名方法。
【請求項１５】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）として、 前記電子署名装置が、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択ステップと、
前記電子署名装置が、Ｚqに属する乱数ｒ、ｘ及び１以上のｎ個の乱数ｙi、但し、i=1,…,n、を生成する乱数生成ステップと、
前記電子署名装置が、前記ｘ、ｙi、ｇ1及びｇ2を用いて、Ｘ'＝ｇ2x、Ｙi'＝ｇ2yi,、Ｙi＝ｇ1yiを計算し、公開鍵pk＝(ｖ、ｇ1，ｇ2，Ｘ'，Ｙi'，Ｙi)を生成する公開鍵生成ステップと、
前記電子署名装置が、前記ｇ１、ｇ２、ｒ、ｘ、ｎ個のｙi及びｎ個の平文ｍｉを用いて、
ｂ1i＝ｍiryiＹir、
ｂ3＝(Πni=1ｍiyi)rx(Πni=1Ｙi)rx、
ｂ5i＝ｇ2ryi
を計算し、電子署名σ＝(ｂ1i，ｂ3，ｂ5i)を生成する電子署名生成ステップと、
を有する電子署名方法。
【請求項１６】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、ｇ1及びｇ2、をそれぞれＧ，Ｇの生成元とし、公開パラメータｖをｖ＝(ｑ，Ｇ1，Ｇ2，ＧT，ｅ)とし、公開鍵pkをpk＝(ｖ，ｇ1，ｇ2，Ｘ'，Ｙ'，Ｙ)とし、Ｘ'＝ｇ2x、Ｙ'＝ｇ2y、Ｙ＝ｇ1yとし、ｘ、ｙをＺqに属する乱数とし、
電子署名装置から電子署名σ＝(ｂ1，ｂ3，ｂ5)及び平文ｍを受け、公開鍵pk、電子署名σ及び平文ｍを使って、
(1) e(ｂ1，ｇ2)＝e(ｍｇ1，ｂ5)
(2) e(ｂ3，ｇ2)＝e(ｂ1，Ｘ')
を計算し、式(1), (2)の等式全てが成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定ステップを有する検証方法。
【請求項１７】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、ｇ1及びｇ2、をそれぞれＧ，Ｇの生成元とし、公開パラメータｖをｖ＝(ｑ，Ｇ1，Ｇ2，ＧT，ｅ)とし、公開鍵pkをpk＝(ｖ，ｇ1，ｇ2，Ｘ'，Ｙ'，Ｙ)とし、Ｘ'＝ｇ2x、Ｙ'＝ｇ2y、Ｙ＝ｇ1yとし、ｘ、ｙをＺqに属する乱数とし、
電子署名装置から電子署名σ＝(ｂ1i，ｂ3，ｂ5i)及びｎ個の平文ｍｉを受け、公開鍵pk、電子署名σ及び１以上のｎ個の平文ｍｉ、但し、i=1,…,n、を使って、
(1) e(ｂ1i，ｇ2)＝e(ｍiｇ１，ｂ5i)
(2) e(ｂ3，ｇ2)＝e(Πni=1ｂ1i，Ｘ')
を計算し、式(1), (2)の等式全てがi=1,…,nについて成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定ステップと、
を有する検証方法。
【請求項１８】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、ｇ1及びｇ2、をそれぞれＧ，Ｇの生成元とし、公開パラメータｖをｖ＝(ｑ，Ｇ1，Ｇ2，ＧT，ｅ)とし、公開鍵pkをpk＝(ｖ，ｇ1，ｇ2，Ｘ'，Ｙi'，Ｙi)とし、Ｘ'＝ｇ2x、Ｙi'＝ｇ2yi、Ｙi＝ｇ1yiとし、ｘ及びｎ個のｙiをＺqに属する乱数とし、
電子署名装置から電子署名σ＝(ｂ1i，ｂ3，ｂ5i)及び１以上のｎ個の平文ｍｉを受け、公開鍵pk、電子署名σ及び１以上のｎ個の平文ｍｉ、但し、i=1,…,n、を使って、
(1) e(ｂ1i，ｇ2)＝e(ｍiｇ１，ｂ5i)
(2) e(ｂ3，ｇ2)＝e(Πni=1ｂ1i，Ｘ')
を計算し、式(1), (2)の等式全てがi=1,…,nについて成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定ステップと、
を有する検証方法。
【請求項１９】
請求項４，５又は６のいずれか記載の電子署名装置としてコンピュータを機能させるための電子署名プログラム。
【請求項２０】
請求項７，８又は９のいずれか記載の検証装置としてコンピュータを機能させるための検証プログラム。
【請求項１】
電子署名装置と、検証装置とを含む電子署名検証システムにおいて、
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）とし、
前記電子署名装置は、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択部と、
Ｚqに属する乱数ｒ、ｘ及びｙを生成する乱数生成部と、
前記ｘ、ｙ、ｇ１及びｇ２が入力され、Ｘ'＝ｇ２ｘ、Ｙ'＝ｇ２ｙ、Ｙ＝ｇ１ｙを計算し、公開鍵pkをpk＝(ｖ，ｇ１，ｇ２，Ｘ'，Ｙ'，Ｙ)として生成する公開鍵生成部と、
前記ｇ１、ｇ２、ｒ、ｘ、ｙ及び平文ｍが入力され、
ｂ１＝ｍｒｙＹｒ、
ｂ３＝ｍｒｘｙＹｒｘ、
ｂ５＝ｇ２ｒｙ
を計算し、電子署名σ＝(ｂ１，ｂ３，ｂ５)を生成する電子署名生成部と、を有し、
前記検証装置は、前記電子署名装置から前記電子署名σ及び平文ｍを受け、前記公開鍵pk、電子署名σ及び平文ｍを使って、
式(1)： e(ｂ１，ｇ２)＝e(ｍｇ１，ｂ５)
式(2)： e(ｂ３，ｇ２)＝e(ｂ１，Ｘ')
を計算し、式(1)と(2)の等式全てが成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定部を有することを特徴とする電子署名検証システム。
【請求項２】
電子署名装置と、検証装置とを含む電子署名検証システムにおいて、
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）とし、
前記電子署名装置は、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択部と、
Ｚqに属する１以上のｎ個の乱数ｒi, 但し、i=1,…, n、と乱数ｘ及びｙを生成する乱数生成部と、
前記ｘ、ｙ、ｇ1及びｇ2が入力され、Ｘ'＝ｇ2x、Ｙ'＝ｇ2y、Ｙ＝ｇ1yを計算し、公開鍵pk＝(ｖ，ｇ1，ｇ2，Ｘ'，Ｙ'，Ｙ)を生成する公開鍵生成部と、
前記ｇ1、ｇ2、ｎ個のｒi、ｘ、ｙ及びｎ個の平文ｍiが入力され、i=1,…,nについて
ｂ1i＝ｍiriｙＹri、
ｂ3＝(Πni=1ｍiri)ｘｙ(Πni=1Ｙri)ｘ、
ｂ5i＝ｇ２riｙ
を計算し、電子署名σ＝(ｂ1i，ｂ３，ｂ5i)を生成する電子署名生成部と、を有し、
前記検証装置は、前記電子署名装置から前記電子署名σ及びｎ個の平文ｍｉを受け、前記公開鍵pk、電子署名σ及びｎ個の平文ｍiを使って、
式(1)： e(ｂ1i，ｇ２)＝e(ｍiｇ１，ｂ5i)
式(2)： e(ｂ3，ｇ2)＝e(Πni=1ｂ1i，Ｘ')
を計算し、式(1)と(2)の等式全てが成立するか否かをi=1,…,nについて判定し、成立する場合には受理し、成立しない場合には拒否する判定部を有することを特徴とする電子署名検証システム。
【請求項３】
電子署名装置と、検証装置からなる電子署名検証システムにおいて、
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝(ｑ，Ｇ１，Ｇ２，ＧT，ｅ)とし、
前記電子署名装置は、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択部と、
Ｚqに属する乱数ｒ、ｘ及び１以上のｎ個の乱数ｙi、但し、i=1,…,n、を生成する乱数生成部と、
前記ｘ、ｙｉ、ｇ１及びｇ２が入力され、Ｘ'＝ｇ２ｘ、Ｙ'ｉ＝ｇ２ｙｉ、Ｙi＝ｇ1yiを計算し、公開鍵pk＝(ｖ，ｇ1，ｇ2，Ｘ'，Ｙ'i，Ｙi)を生成する公開鍵生成部と、
前記ｇ１、ｇ２、ｒ、ｘ、ｙｉ及びｎ個の平文ｍｉが入力され、
ｂ1i＝ｍiryiＹir、
ｂ3＝(Πni=1ｍiyi)rx(Πni=1Ｙi)rx、
ｂ5i＝ｇ2ryi
を計算し、電子署名σ＝(ｂ1i，ｂ３，ｂ5i)を生成する電子署名生成部と、を有し、
前記検証装置は、前記電子署名装置から前記電子署名σ及びｎ個の平文ｍｉを受け、前記公開鍵pk、電子署名σ及びｎ個の平文ｍiを使って
式(1)： e(ｂ1i，ｇ2)＝e(ｍiｇ１，ｂ5i)
式(2)： e(ｂ3，ｇ2)＝e(Πni=1ｂ1i，Ｘ')
を計算し、式(1), (2)の等式全てがi=1,…,nについて成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定部を有することを特徴とする電子署名検証システム。
【請求項４】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）とし、
Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択部と、
Ｚqに属する乱数ｒ、ｘ及びｙを生成する乱数生成部と、
前記ｘ、ｙ、ｇ１及びｇ２が入力され、Ｘ'＝ｇ2ｘ、Ｙ'＝ｇ2y、Ｙ＝ｇ1yを計算し、公開鍵pk＝(ｖ，ｇ１，ｇ２，Ｘ'，Ｙ'，Ｙ)を生成する公開鍵生成部と、
前記ｇ１、ｇ２、ｒ、ｘ、ｙ及び平文ｍが入力され、
ｂ1＝ｍryＹｒ、
ｂ３＝ｍrxyＹrx、
ｂ５＝ｇ2ry
を計算し、電子署名σ＝(ｂ1，ｂ3，ｂ5)を生成する電子署名生成部と、
を有し、前記電子署名σ及び平文ｍを検証装置へ送ることを特徴とする電子署名装置。
【請求項５】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）とし、
Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択部と、
Ｚqに属する１以上のｎ個の乱数ｒi、但し、i=1,…,n、及び乱数ｘとｙを生成する乱数生成部と、
前記ｘ、ｙ、ｇ１及びｇ２が入力され、Ｘ'＝ｇ２ｘ、Ｙ'＝ｇ２ｙ、Ｙ＝ｇ1yを計算し、公開鍵pk＝(ｖ、ｇ1、ｇ2、Ｘ'，Ｙ'，Ｙ)を生成する公開鍵生成部と、
前記ｇ１、ｇ２、ｒｉ、ｘ、ｙ及びｎ個の平文ｍｉが入力され、
ｂ1i＝ｍiriyＹri、
ｂ３＝(Πni=1ｍiri)xy(Πni=1Ｙri)ｘ、
ｂ5i＝ｇ2riｙ
を計算し、電子署名σ＝(ｂ1i，ｂ３，ｂ5i)を生成する電子署名生成部と、
を有し、電子署名σ及びｎ個の平文ｍｉを検証装置へ送ることを特徴とする電子署名装置。
【請求項６】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）とし、
Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択部と、
Ｚqに属する乱数ｒ、ｘと１以上のｎ個の乱数ｙi、但しi=1,…,n、を生成する乱数生成部と、
前記ｘ、ｙ、ｇ１及びｇ２が入力され、Ｘ'＝ｇ2x、Ｙi'＝ｇ2yi、Ｙi＝ｇ1yiを計算し、公開鍵pk＝(ｖ、ｇ1、ｇ2、Ｘ'，Ｙi'，Ｙi)を生成する公開鍵生成部と、
前記ｇ１、ｇ２、ｒ、ｘ、ｎ個のｙi及びｎ個の平文ｍｉが入力され、
ｂ1i＝ｍiryiＹir、
ｂ３＝(Πni=1ｍiyi)rx(Πni=1Ｙi)rx、
ｂ5i＝ｇ2ryi
を計算し、電子署名σ＝(ｂ1i，ｂ３，ｂ5i)を生成する電子署名生成部と、
を有し、電子署名σ及びｎ個の平文ｍｉを検証装置へ送ることを特徴とする電子署名装置。
【請求項７】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、ｇ1及びｇ2、をそれぞれＧ，Ｇの生成元とし、公開パラメータｖをｖ＝(ｑ，Ｇ1，Ｇ2，ＧT，ｅ)とし、公開鍵pkをpk＝(ｖ，ｇ1，ｇ2，Ｘ'，Ｙ'，Ｙ)とし、Ｘ'＝ｇ2x、Ｙ'＝ｇ2y、Ｙ＝ｇ1yとし、ｘ、ｙをＺqに属する乱数とし、
電子署名装置から電子署名σ＝(ｂ1，ｂ3，ｂ5)及び平文ｍを受け、公開鍵pk、電子署名σ及び平文ｍを使って、
(1) e(ｂ1，ｇ2)＝e(ｍｇ1，ｂ5)
(2) e(ｂ3，ｇ2)＝e(ｂ1，Ｘ')
を計算し、式(1), (2)の等式全てが成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定部を有することを特徴とする検証装置。
【請求項８】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、ｇ1及びｇ2、をそれぞれＧ，Ｇの生成元とし、公開パラメータｖをｖ＝(ｑ，Ｇ1，Ｇ2，ＧT，ｅ)とし、公開鍵pkをpk＝(ｖ，ｇ1，ｇ2，Ｘ'，Ｙ'，Ｙ)とし、Ｘ'＝ｇ2x、Ｙ'＝ｇ2y、Ｙ＝ｇ1yとし、ｘ、ｙをＺqに属する乱数とし、
電子署名装置から電子署名σ＝(ｂ1i，ｂ3，ｂ5i)及び１以上のｎ個の平文ｍｉ、但し、i=1,…,n、を受け、公開鍵pk、電子署名σ及びｎ個の平文ｍｉを使って、
(1) e(ｂ1i，ｇ2)＝e(ｍiｇ１，ｂ5i)
(2) e(ｂ3，ｇ2)＝e(Πni=1ｂ1i，Ｘ')
を計算し、式(1), (2)の等式全てがi=1,…,nについて成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定部を有することを特徴とする検証装置。
【請求項９】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、ｇ1及びｇ2、をそれぞれＧ，Ｇの生成元とし、公開パラメータｖをｖ＝(ｑ，Ｇ1，Ｇ2，ＧT，ｅ)とし、公開鍵pkをpk＝(ｖ，ｇ1，ｇ2，Ｘ'，Ｙi'，Ｙi)とし、Ｘ'＝ｇ2x、Ｙi'＝ｇ2yi、Ｙi＝ｇ1yiとし、ｘ、ｙiをＺqに属する乱数とし、
電子署名装置から電子署名σ＝(ｂ1i，ｂ3，ｂ5i)及び１以上のｎ個の平文ｍｉを受け、公開鍵pk、電子署名σ及びｎ個の平文ｍｉを使って、
(1) e(ｂ1i，ｇ2)＝e(ｍiｇ１，ｂ5i)
(2) e(ｂ3，ｇ2)＝e(Πni=1ｂ1i，Ｘ')
を計算し、式(1), (2)の等式全てがi=1,…,nについて成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定部を有することを特徴とする検証装置。
【請求項１０】
電子署名装置と、検証装置を用いる電子署名検証方法であって、
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）として、 前記電子署名装置が、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択ステップと、
前記電子署名装置が、Ｚqに属する乱数ｒ、ｘ及びｙを生成する乱数生成ステップと、
前記電子署名装置が、前記ｘ、ｙ、ｇ１及びｇ２を用いて、Ｘ'＝ｇ２ｘ、Ｙ'＝ｇ２ｙ、及びＹ＝ｇ1yを計算し、公開鍵pk＝(ｖ、ｇ1、ｇ2、Ｘ'，Ｙ'，Ｙ)を生成して公開するステップと、
前記電子署名装置が、前記ｇ１、ｇ２、ｒｉ、ｘ、ｙ及び平文ｍを用いて、
ｂ1＝ｍryＹｒ、
ｂ3＝ｍryxＹrx、
ｂ5＝ｇ2ry
を計算し、電子署名σ＝(ｂ1，ｂ3，ｂ5)を生成する電子署名生成ステップと、
前記検証装置が、前記公開鍵pkと、前記電子署名装置から受け取った前記電子署名σ及び平文ｍとを使って
前記検証装置が、
式(1)： e(ｂ1，ｇ2)＝e(ｍｇ1，ｂ5)
式(2)： e(ｂ3，ｇ2)＝e(ｂ1，Ｘ')
を計算し、式(1), (2)の等式全てが成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定ステップを有する、
ことを特徴とする電子署名検証方法。
【請求項１１】
電子署名装置と、検証装置を用いる電子署名検証方法であって、
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）として、 前記電子署名装置が、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択ステップと、
前記電子署名装置が、Ｚqに属する１以上のｎ個の乱数ｒi、但し、i=1,…,ｎであり、ｘ及びｙを生成する乱数生成ステップと、
前記電子署名装置が、前記ｘ、ｙ、ｇ１及びｇ２を用いて、Ｘ'＝ｇ２ｘ、Ｙ'＝ｇ２ｙ、及びＹ＝ｇ1yを計算し、公開鍵pk＝(ｖ、ｇ1、ｇ2、Ｘ'，Ｙ'，Ｙ)を生成して公開するステップと、
前記電子署名装置が、前記ｇ１、ｇ２、ｎ個のｒｉ、ｘ、ｙ及びｎ個の平文ｍｉを用いて、
ｂ1i＝ｍiriyＹri、
ｂ3＝(Πni=1ｍiri)yx(Πni=1Ｙri)x、
ｂ5i＝ｇ2riy
を計算し、電子署名σ＝(ｂ1i，ｂ3，ｂ5i)を生成する電子署名生成ステップと、
前記検証装置が、前記公開鍵pkと、前記電子署名装置から受け取った前記電子署名σ及びｎ個の平文ｍｉとを使って
前記検証装置が、
式(1)： e(ｂ1i，ｇ2)＝e(ｍiｇ1，ｂ5i)
式(2)： e(ｂ3，ｇ2)＝e(Πni=1ｂ1i，Ｘ')
を計算し、式(1), (2)の等式全てがi=1,…,nについて成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定ステップを有する、
ことを特徴とする電子署名検証方法。
【請求項１２】
電子署名装置と、検証装置を用いる電子署名検証方法であって、
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）として、 前記電子署名装置が、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択ステップと、
前記電子署名装置が、Ｚqに属する乱数ｒ、ｘ及び１以上のｎ個の乱数ｙi、但し、i=1,…,n、を生成する乱数生成ステップと、
前記電子署名装置が、前記ｘ、ｙi、ｇ１及びｇ２を用いて、Ｘ'＝ｇ2x、Ｙi'＝ｇ2yi、及びＹi＝ｇ1yiを計算し、公開鍵pk＝(ｖ、ｇ1、ｇ2、Ｘ'，Ｙi'，Ｙi)を生成して公開するステップと、
前記電子署名装置が、前記ｇ１、ｇ２、ｒ、ｘ、ｎ個のｙi及びｎ個の平文ｍｉを用いて、
ｂ1i＝ｍiryiＹｒ、
ｂ3＝(Πni=1ｍiyi)rx(Πni=1Ｙi)rx、
ｂ5i＝ｇ2ryi
を計算し、電子署名σ＝(ｂ1i，ｂ3，ｂ5i)を生成する電子署名生成ステップと、
前記検証装置が、前記公開鍵pkと、前記電子署名装置から受け取った前記電子署名σ及びｎ個の平文ｍｉとを使って
前記検証装置が、
式(1)： e(ｂ1i，ｇ2)＝e(ｍiｇ1，ｂ5i)
式(2)： e(ｂ3，ｇ2)＝e(Πni=1ｂ1i，Ｘ')
を計算し、式(1), (2)の等式全てがi=1,…,nについて成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定ステップを有する、
ことを特徴とする電子署名検証方法。
【請求項１３】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）として、 前記電子署名装置が、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択ステップと、
前記電子署名装置が、Ｚqに属する乱数ｒ、ｘ及びｙを生成する乱数生成ステップと、
前記電子署名装置が、前記ｘ、ｙ、ｇ1及びｇ2を用いて、Ｘ'＝ｇ2x、Ｙ'＝ｇ2y,、Ｙ＝ｇ1yを計算し、公開鍵pk＝(ｖ、ｇ1，ｇ2，Ｘ'，Ｙ'，Ｙ)を生成する公開鍵生成ステップと、
前記電子署名装置が、前記ｇ１、ｇ２、ｒｉ、ｘ、ｙ及び平文ｍを用いて、
ｂ1＝ｍryＹｒ、
ｂ3＝ｍryxＹrx、
ｂ5＝ｇ2ry
を計算し、電子署名σ＝(ｂ1，ｂ3，ｂ5)を生成する電子署名生成ステップと、
を有する電子署名方法。
【請求項１４】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）として、 前記電子署名装置が、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択ステップと、
前記電子署名装置が、Ｚqに属する１以上のｎ個の乱数ｒｉ、但し、i=1,…,n、と乱数ｘ及びｙを生成する乱数生成ステップと、
前記電子署名装置が、前記ｘ、ｙ、ｇ1及びｇ2を用いて、Ｘ'＝ｇ2x、Ｙ'＝ｇ2y,、Ｙ＝ｇ1yを計算し、公開鍵pk＝(ｖ、ｇ1，ｇ2，Ｘ'，Ｙ'，Ｙ)を生成する公開鍵生成ステップと、
前記電子署名装置が、前記ｇ１、ｇ２、ｒｉ、ｘ、ｙ及びｎ個の平文ｍｉを用いて、
ｂ1i＝ｍiriyＹｒｉ、
ｂ3＝(Πni=1ｍiri)yx(Πni=1Ｙri)x、
ｂ5i＝ｇ2riy
を計算し、電子署名σ＝(ｂ1i，ｂ3，ｂ5i)を生成する電子署名生成ステップと、
を有する電子署名方法。
【請求項１５】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）として、 前記電子署名装置が、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択ステップと、
前記電子署名装置が、Ｚqに属する乱数ｒ、ｘ及び１以上のｎ個の乱数ｙi、但し、i=1,…,n、を生成する乱数生成ステップと、
前記電子署名装置が、前記ｘ、ｙi、ｇ1及びｇ2を用いて、Ｘ'＝ｇ2x、Ｙi'＝ｇ2yi,、Ｙi＝ｇ1yiを計算し、公開鍵pk＝(ｖ、ｇ1，ｇ2，Ｘ'，Ｙi'，Ｙi)を生成する公開鍵生成ステップと、
前記電子署名装置が、前記ｇ１、ｇ２、ｒ、ｘ、ｎ個のｙi及びｎ個の平文ｍｉを用いて、
ｂ1i＝ｍiryiＹir、
ｂ3＝(Πni=1ｍiyi)rx(Πni=1Ｙi)rx、
ｂ5i＝ｇ2ryi
を計算し、電子署名σ＝(ｂ1i，ｂ3，ｂ5i)を生成する電子署名生成ステップと、
を有する電子署名方法。
【請求項１６】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、ｇ1及びｇ2、をそれぞれＧ，Ｇの生成元とし、公開パラメータｖをｖ＝(ｑ，Ｇ1，Ｇ2，ＧT，ｅ)とし、公開鍵pkをpk＝(ｖ，ｇ1，ｇ2，Ｘ'，Ｙ'，Ｙ)とし、Ｘ'＝ｇ2x、Ｙ'＝ｇ2y、Ｙ＝ｇ1yとし、ｘ、ｙをＺqに属する乱数とし、
電子署名装置から電子署名σ＝(ｂ1，ｂ3，ｂ5)及び平文ｍを受け、公開鍵pk、電子署名σ及び平文ｍを使って、
(1) e(ｂ1，ｇ2)＝e(ｍｇ1，ｂ5)
(2) e(ｂ3，ｇ2)＝e(ｂ1，Ｘ')
を計算し、式(1), (2)の等式全てが成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定ステップを有する検証方法。
【請求項１７】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、ｇ1及びｇ2、をそれぞれＧ，Ｇの生成元とし、公開パラメータｖをｖ＝(ｑ，Ｇ1，Ｇ2，ＧT，ｅ)とし、公開鍵pkをpk＝(ｖ，ｇ1，ｇ2，Ｘ'，Ｙ'，Ｙ)とし、Ｘ'＝ｇ2x、Ｙ'＝ｇ2y、Ｙ＝ｇ1yとし、ｘ、ｙをＺqに属する乱数とし、
電子署名装置から電子署名σ＝(ｂ1i，ｂ3，ｂ5i)及びｎ個の平文ｍｉを受け、公開鍵pk、電子署名σ及び１以上のｎ個の平文ｍｉ、但し、i=1,…,n、を使って、
(1) e(ｂ1i，ｇ2)＝e(ｍiｇ１，ｂ5i)
(2) e(ｂ3，ｇ2)＝e(Πni=1ｂ1i，Ｘ')
を計算し、式(1), (2)の等式全てがi=1,…,nについて成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定ステップと、
を有する検証方法。
【請求項１８】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、ｇ1及びｇ2、をそれぞれＧ，Ｇの生成元とし、公開パラメータｖをｖ＝(ｑ，Ｇ1，Ｇ2，ＧT，ｅ)とし、公開鍵pkをpk＝(ｖ，ｇ1，ｇ2，Ｘ'，Ｙi'，Ｙi)とし、Ｘ'＝ｇ2x、Ｙi'＝ｇ2yi、Ｙi＝ｇ1yiとし、ｘ及びｎ個のｙiをＺqに属する乱数とし、
電子署名装置から電子署名σ＝(ｂ1i，ｂ3，ｂ5i)及び１以上のｎ個の平文ｍｉを受け、公開鍵pk、電子署名σ及び１以上のｎ個の平文ｍｉ、但し、i=1,…,n、を使って、
(1) e(ｂ1i，ｇ2)＝e(ｍiｇ１，ｂ5i)
(2) e(ｂ3，ｇ2)＝e(Πni=1ｂ1i，Ｘ')
を計算し、式(1), (2)の等式全てがi=1,…,nについて成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定ステップと、
を有する検証方法。
【請求項１９】
請求項４，５又は６のいずれか記載の電子署名装置としてコンピュータを機能させるための電子署名プログラム。
【請求項２０】
請求項７，８又は９のいずれか記載の検証装置としてコンピュータを機能させるための検証プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２０１０−１８６００３（Ｐ２０１０−１８６００３Ａ）
【公開日】平成２２年８月２６日（２０１０．８．２６）
【国際特許分類】
【出願番号】特願２００９−２９４２９（Ｐ２００９−２９４２９）
【出願日】平成２１年２月１２日（２００９．２．１２）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２２年８月２６日（２０１０．８．２６）
【国際特許分類】
【出願日】平成２１年２月１２日（２００９．２．１２）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]