電子署名検証システム、電子署名装置、検証装置、電子署名検証方法、電子署名方法、検証方法、電子署名プログラム、検証プログラム
【課題】本発明は、電子署名を構成する要素の数を少なくし、電子署名長が短く、情報量及び通信量が少なく、また、検証時の計算量の少ない電子署名検証方法及び装置を提供することを目的とする。
【解決手段】本発明の電子署名検証システムは、登録装置と、電子署名装置と、検証装置からなる。電子署名装置は、乱数ｘ及びｙとＧ１及びＧ２それぞれの生成元ｇ１及びｇ２を用いて、Ｘ＝ｇ２ｘ、Ｙ＝ｇ２ｙを計算し、公開鍵ｐｋを生成する。ｇ１、ｇ２、乱数ｒｉ、ｘ、ｙ及び平文ｍｉを用いて、電子署名σを生成する。検証装置は、公開鍵ｐｋ、電子署名σ及び平文ｍｉを用いて、改竄等が行われていないか検証する。
【解決手段】本発明の電子署名検証システムは、登録装置と、電子署名装置と、検証装置からなる。電子署名装置は、乱数ｘ及びｙとＧ１及びＧ２それぞれの生成元ｇ１及びｇ２を用いて、Ｘ＝ｇ２ｘ、Ｙ＝ｇ２ｙを計算し、公開鍵ｐｋを生成する。ｇ１、ｇ２、乱数ｒｉ、ｘ、ｙ及び平文ｍｉを用いて、電子署名σを生成する。検証装置は、公開鍵ｐｋ、電子署名σ及び平文ｍｉを用いて、改竄等が行われていないか検証する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電気通信システムで送信者の身元を確認する電子署名検証システム、電子署名装置、検証装置、その方法及びプログラムに関する。
【背景技術】
【０００２】
電子署名はメッセージｍに対して、公開鍵ｐｋに対応する秘密鍵ｓｋを知る署名者が、メッセージｍに対して秘密鍵ｓｋを正しく使ったときにのみ計算できる値σを算出し、これを電子的な署名として用いるものである。正しく計算された電子署名は誰でも公開鍵ｐｋを用いてその正当性を検証することが可能である。一方、秘密鍵ｓｋを知らないいかなる第三者も正当な電子署名σを算出することはできない。電子署名は電子現金やクレデンシャルシステムなど、様々な暗号プロトコルにおいて基本的な構成要素として利用されている。
【０００３】
また、利用者のプライバシーを必要とする応用においては、ゼロ知識証明と組み合わせることにより、電子署名σを明かさないまま、あるメッセージに対する電子署名を保持しているという事実を任意の第三者に納得させるなど、高度な利用形態がある。例えば、非特許文献１のようにペアリング技術を用い、群の要素がある関係を満たすという事実を効率的に証明するゼロ知識証明が構成可能となった。これによって、電子署名σが効率的なバイリニアマップを持つ群の要素である、すなわち、σ∈Ｇである場合、前述のように、電子署名σを明かさないまま、正しい電子署名σを保持しているという事実を証明することが可能である。
【０００４】
例えば、非特許文献２記載の技術、いわゆる、CL-Signatureと言われる技術では、メッセージｍ∈Ｚｑに対する電子署名σは３つの群要素（ａ，ｂ，ｃ）∈Ｇ３から構成されている。
【０００５】
しかしながら、CL-Signatureと言われる技術では、ランダムオラクルモデル等の理想化された構成要素を用いず、数論的な仮定のみによって安全性が証明できる既存の電子署名方法では、メッセージｍが群Ｇの要素ではないため、メッセージｍを秘匿した状態で、その秘匿したメッセージに対する正しい電子署名を保持していることを証明する、という応用には適さない。メッセージｍが群Ｇの要素である場合にも、安全な電子署名方法として、非特許文献３がある。以下説明する。
【０００６】
ｑを大きな素数とし、Ｇ１，Ｇ２，ＧＴを位数ｑの群とし、ｅを効率的に計算可能なバイリニアマップｅ：Ｇ１×Ｇ２→ＧＴとし、ｖ＝（ｑ，Ｇ１，Ｇ２，ＧＴ，ｅ）を公開パラメータとする。
【０００７】
署名者は、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択し、Ｚｑに属する乱数ｒ、ｘ及びｙを生成し、Ｘ＝ｇ２ｘ、Ｙ＝ｇ２ｙとする。ｖ、ｇ１、ｇ２、Ｘ、Ｙを公開鍵ｐｋとし、ｘ、ｙを秘密鍵ｓｋとする。
【０００８】
メッセージｍ∈Ｇ１に対して、以下のように、電子署名σを生成する。電子署名σ＝（ａ１，ａ２，ａ３，ａ４，ａ５）∈Ｇ１４×Ｇ２とし、
ａ１＝ｇ１ｒ （１）
ａ２＝ｍｒ （２）
ａ３＝ｇ１ｒｘｍｒｘｙ （３）
ａ４＝ｍｒｙ （４）
ａ５＝ｇ２ｒ （５）
とする。
【０００９】
検証者は、公開鍵ｐｋ及び電子署名σを用いて、以下の等式が成り立つことを確認し、電子署名の真正性及び完全性を検証する。
【００１０】
ｅ（ａ１，ｇ２）＝ｅ（ｇ１，ａ５） （６）
ｅ（ｍ，ａ５）＝ｅ（ａ２，ｇ２） （７）
ｅ（ａ２，Ｙ）＝ｅ（ａ４，ｇ２） （８）
ｅ（ａ３，ｇ２）＝ｅ（ａ１ａ４，Ｘ） （９）
【非特許文献１】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 Hopkins 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，ｅ）とする。電子署名装置は、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する。Ｚｑに属する乱数ｒｉ（但し、１≦ｉ≦ｎであり、ｎは、平文の個数を表す）、ｘ及びｙを生成する。公開パラメータｖと乱数ｒｉ、ｘ及びｙを記憶し、特にｘ、ｙは秘密鍵ｓｋとして秘密に記憶する。ｘ、ｙ、ｇ１及びｇ２を用いて、Ｘ＝ｇ２ｘ、Ｙ＝ｇ２ｙを計算し、公開鍵ｐｋを生成する。ｇ１、ｇ２、ｒｉ、ｘ、ｙ及び平文ｍｉを用いて、ｂｉ１＝ｇ１ｒｉ、ｂ３＝Πｎｉ＝１ｇ１ｒｉｘｍｉｒｉｘｙ、ｂｉ４＝ｍｉｒｉｙ、ｂｉ５＝ｇ２ｒｉｙを計算し、電子署名σ＝（ｂｉ１，ｂ３，ｂｉ４，ｂｉ５）を生成する。検証装置は、公開鍵ｐｋ、電子署名σ及び平文ｍｉを記憶する。
【００１３】
（１）ｅ（ｂｉ１，Ｙ）＝ｅ（ｇ１，ｂｉ５）
（２）ｅ（ｍｉ，ｂｉ５）＝ｅ（ｂｉ４，ｇ２）
（３）ｅ（ｂ３，ｇ２）＝ｅ（Πｎｉ＝１ｂｉ１ｂｉ４，Ｘ）
（１）〜（３）の等式全てが成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する。登録装置は、公開パラメータｖ及び公開鍵ｐｋを記憶する記憶部を有する。電子署名装置は、登録装置から公開パラメータｖを受け取り、公開鍵ｐｋを登録装置へ、電子署名σ及び平文ｍｉを検証装置へ、送る。検証装置は、登録装置から公開鍵ｐｋを、電子署名装置から電子署名σ及び平文ｍｉを、受け取る。
【発明の効果】
【００１４】
本発明の電子署名検証方法及び装置によれば、従来技術同様、真正性及び完全性を担保しながら、群の元を用いて電子署名を構成することができ、かつ、電子署名を構成する要素の数を少なくすることにより、電子署名長が短く、通信量が少なくすることができる。また、検証時の計算式の少なくすることにより、計算量を少なくすることができる。
【発明を実施するための最良の形態】
【００１５】
ここで、本発明の実施例について説明する。
【実施例１】
【００１６】
［電子署名検証システム１］
図１は、電子署名検証システム１の構成例を示す図である。図２は、電子署名検証システム１のシーケンス図の一例を示す図である。電子署名検証システム１は、登録装置３００と、電子署名装置１００と、検証装置２００からなる。
【００１７】
ｑを大きな素数とし、Ｇ１，Ｇ２，ＧＴを位数ｑの群とし、ｅを効率的に計算可能なバイリニアマップｅ：Ｇ１×Ｇ２→ＧＴとし、ｖ＝（ｑ，Ｇ１，Ｇ２，ＧＴ，ｅ）を公開パラメータとする。なお、ｇａとは、ｇ∈Ｇに対し、群Ｇで定義される演算をａ回行うことを意味する。バイリニアマップとしては、例えば、ＷｅｉｌペアリングやＴａｔｅペアリング等が考えられる。
【００１８】
電子署名装置１００は、平文ｍを検証装置２００に送る際に、電子署名σを添付するために、登録装置３００に対して、公開パラメータｖを要求する（ｓ１０）。登録装置３００は、ｖを電子署名装置１００へ送る（ｓ１２）。電子署名装置１００は、公開パラメータｖから公開鍵ｐｋを生成し、登録装置３００へ送る（ｓ１４）。登録装置３００は、公開鍵ｐｋを登録及び公開する（ｓ１６）。なお、送るたびに公開パラメータを要求しなくとも、記憶している公開パラメータを利用して公開鍵を生成してもよい。さらに、平文ｍ、公開鍵ｐｋ及び秘密鍵ｓｋを用いて、電子署名σを生成する。電子署名装置１００は、電子署名σ及び平文ｍを検証装置へ送る（ｓ１８）。
【００１９】
検証装置２００は、電子署名σに対応する公開鍵ｐｋを登録装置３００へ要求する（ｓ２０）。登録装置３００は、公開鍵ｐｋを検証装置２００へ送る（ｓ２２）。検証装置２００は、電子署名σ、平文ｍ、公開鍵ｐｋを用いて、改竄及び成りすまし等が行われていないか検証する（ｓ２４）。以下、各装置及び各処理について詳細を説明する。
【００２０】
［登録装置３００］
登録装置３００は、公開パラメータｖを登録及び公開している。例えば、登録装置３００は、信頼できる第三者等が管理し、通信部３０１と、記憶部３０３と、制御部３０５を有する。登録装置３００は、通信部３０１を介して、電子署名装置及び検証装置と通信する。通信部３０１は、例えば、ＬＡＮアダプタ等により構成され、ＬＡＮやインターネット等からなる通信回線と接続される。但し、必ずしも通信部を有さずともよく、例えば、キーボード等の入力装置から公開パラメータを入力してもよいし、また、ＵＳＢメモリ等の可搬媒体に公開パラメータを記憶し、それを入力してもよい。以下、同様に各装置（電子署名装置及び検証装置）は送信部１０１、２０１を有さずともよく、装置間のデータの入出力は、通信以外の方法であってもよい。記憶部３０３は、公開パラメータ、公開鍵等を記憶する。なお、上記「登録」とは、記憶部３０３に記憶することを意味してもよい。また、「公開」とは、利用者の求めに応じて、情報（例えば、公開パラメータ）を閲覧可能、または、取得可能とすることを意味する。制御部３０５は、各処理を制御する。
【００２１】
［電子署名装置１００］
図３は、電子署名装置１００の構成例を示す図である。図４は、電子署名装置１００の処理フローの一例を示す図である。電子署名装置１００は、通信部１０１と、記憶部１０３と、制御部１０５と、生成元選択部１２０と、乱数生成部１３０と、公開鍵生成部１４０と、電子署名生成部１５０を有する。
【００２２】
＜制御部１０５及び通信部１０１＞
本実施例の電子署名装置１００は、制御部１０５の制御のもと各処理を実行する。電子署名装置１００は、登録装置３００から公開パラメータｖを受け取る。例えば、通信部１０１は、登録装置３００及び検証装置２００と通信を行い、登録装置３００から公開パラメータｖを受信する（ｓ１０１）。以下、特に記述しなくとも、登録装置３００及び検証装置２００と通信する際には、通信部１０１を介して行われるものとする。
【００２３】
受信した公開パラメータｖを記憶部１０３に記憶する（ｓ１０３）。また、特に示さない限り、入出力される各データや演算過程の各データは、逐一、記憶部１０３に格納・読み出され、各演算処理が進められる。但し、必ずしも記憶部１０３に記憶しなければならないわけではなく、各部間で直接データを受け渡してもよい。
【００２４】
＜生成元選択部１２０、乱数生成部１３０及び記憶部１０３＞
生成元選択部１２０は、群Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する（ｓ１２０）。生成元選択部１２０は、通信部１０１を介して、または、通信部１０１及び記憶部１０３を介して、公開パラメータｖを入力され、生成元ｇ１及びｇ２を公開鍵生成部１４０及び電子署名生成部１５０へ、出力する。乱数生成部１３０は、Ｚｑに属する乱数ｒ、ｘ及びｙを生成して出力する（ｓ１３０）。乱数生成部１３０は、乱数ｘ、ｙを公開鍵生成部１４０へ、乱数ｒ、ｘ、ｙを電子署名生成部１５０へ出力する。記憶部１０３は、乱数ｒ、ｘ及びｙが記憶され、特にｘ、ｙは秘密鍵ｓｋ＝（ｘ，ｙ）として秘密に記憶される（ｓ１３３）。なお、秘密鍵ｓｋには、対応する公開鍵ｐｋを含め、ｓｋ＝（ｐｋ，ｘ，ｙ）としてもよい。他の実施例においても同様である。公開鍵ｐｋについての詳細は後述する。
【００２５】
＜公開鍵生成部１４０＞
公開鍵生成部１４０は、ｘ、ｙ、ｇ１及びｇ２が入力され、Ｘ＝ｇ２ｘ、Ｙ＝ｇ２ｙを計算し、公開鍵ｐｋ＝（ｖ，ｇ１，ｇ２，Ｘ，Ｙ）を生成する（ｓ１４０）。公開鍵ｐｋは、通信部１０１を介して、登録装置３００へ送られる。なお、公開鍵ｐｋには、利用した公開パラメータを表示する情報ｉ等を含めｐｋ＝（ｉ，ｇ１，ｇ２，Ｘ，Ｙ）としてもよい。この場合には、以下で説明する検証装置２００は、情報ｉに基づいて、登録装置３００に対応する公開パラメータｖｉを要求する。また、登録装置３００の記憶している公開パラメータの中から対応する公開パラメータを特定することができる場合には、公開鍵ｐｋに公開パラメータｖや、公開パラメータを表示する情報ｉ等を含まなくともよく、検証装置２００は、平文ｍ及び電子署名σを受け付けた際に、登録装置３００に公開パラメータｖを要求する。
【００２６】
＜電子署名生成部１５０＞
電子署名生成部１５０は、ｇ１、ｇ２、ｒ、ｘ、ｙ及び平文ｍ∈Ｇ１が入力され、
ｂ１＝ｇ１ｒ （１１）
ｂ３＝ｇ１ｒｘｍｒｘｙ （１３）
ｂ４＝ｍｒｙ （１４）
ｂ５＝ｇ２ｒｙ （１５）
を計算し、電子署名σ＝（ｂ１，ｂ３，ｂ４，ｂ５）を生成する（ｓ１５０）。電子署名生成部１５０は、生成元選択部１２０から生成元ｇ１、ｇ２を、乱数生成部１３０から乱数ｒ、ｘ、ｙを、さらに平文ｍを入力され、電子署名σを出力する。なお、平文ｍ∈Ｚｑであり、補助記憶装置やメモリ上のデータ等、もしくは、入力インターフェース、キーボード、マウス等から入力されるデータである。
【００２７】
電子署名装置１００は、公開鍵ｐｋを登録装置３００へ、電子署名σ及び平文ｍを検証装置２００へ、送る。例えば、通信部１０１を介して、送信する（ｓ１５３）。
【００２８】
このような構成とすることで、電子署名σを構成する要素の数を５つから４つに少なくすることができる。これにより、例えば、電子署名σの各要素を生成する演算量が同一の場合には、演算量を２０％軽減できる。また、例えば、電子署名σの各要素が同一の情報量を有している場合には、電子署名長を２０％短く作成することができる。これにより電子署名σに要する通信量を軽減することもできる。なお、公開鍵の生成（ｓ１４０）と電子署名の生成（ｓ１５０）は、どちらが先に行われてもよい。
【００２９】
［検証装置２００］
図５は、検証装置２００の構成例を示す。図６は、検証装置１００の処理フローの一例を示す図である。検証装置２００は、通信部２０１と、記憶部２０３と、制御部２０５と、判定部２２０を有する。
＜制御部２０５、通信部２０１及び記憶部２０３＞
本実施例の検証装置２００は、制御部２０５の制御のもと各処理を実行する。検証装置は、登録装置から公開鍵ｐｋを、電子署名装置から電子署名σ及び平文ｍを、受け取る。例えば、通信部２０１は、登録装置３００及び検証装置１００と通信を行う。登録装置３００から公開鍵ｐｋを受信する（ｓ２０１）。電子署名装置１００から電子署名σ及び平文ｍを受信する（ｓ２０２）。機能、構成等は、通信部１０１と同様である。記憶部２０３は、公開鍵ｐｋ、電子署名σ及び平文ｍが記憶される（ｓ２０３）。
【００３０】
＜判定部２２０＞
判定部２２０は、以下の等式全てが成立するか否かを判定する（ｓ２２０）。成立する場合には受理し（ｓ２２３）、成立しない場合には拒否する（ｓ２２５）。
【００３１】
ｅ（ｂ１，Ｙ）＝ｅ（ｇ１，ｂ５） （１６）
ｅ（ｍ，ｂ５）＝ｅ（ｂ４，ｇ２） （１７）
ｅ（ｂ３，ｇ２）＝ｅ（ｂ１ｂ４，Ｘ） （１８）
判定部２２０は、通信部２０１を介して、または、通信部２０１及び記憶部２０３を介して、公開鍵ｐｋ、署名σ及び平文ｍが入力される。以下、上記の式（１６）〜（１８）について従来技術の式（６）〜（９）と比較して説明する。
【００３２】
＜非特許文献３の検証方法＞
従来技術では、式（６）は式（１）及び（５）を用いて、以下のように表すことができる。
ｅ（ｇ１ｒ，ｇ２）＝ｅ（ｇ１，ｇ２ｒ） （６）’
これにより、乱数ｒが同一であることを確認する。式（７）は式（１）及び（２）を用いて、以下のように表すことができる。
ｅ（ｍ，ｇ２ｒ）＝ｅ（ｍｒ，ｇ２） （７）’
これにより、同一の乱数ｒを用いているため、ｍが同一であることを確認する。式（８）は式（２）、（４）、Ｙ＝ｇ２ｙを用いて、以下のように表すことができる。
ｅ（ｍｒ，ｇ２ｙ）＝ｅ（ｍｒｙ，ｇ２） （８）’
これにより、同一の乱数ｒと平文ｍを用いているため、等式が成り立つ場合には、ｙが正しいことが確認できる。式（９）は、式（１）、（３）、（４）、Ｘ＝ｇ２ｘを用いて、以下のように表すことができる。
ｅ（ｇ１ｒｘｍｒｘｙ，ｇ２）＝ｅ（ｇ１ｒｍｒｙ，ｇ２ｘ） （９）’
これにより、同一の乱数ｒ、平文ｍ、ｙを用いているため、等式が成り立つ場合には、ｘが正しいことが確認できる。これらの処理により、電子署名σを作成できるのは、秘密鍵ｓｋ＝（ｘ，ｙ）を知っている署名者のみであることが確認できる。
【００３３】
＜本実施例の検証方法＞
一方、本発明では、式（１６）は式（１１）及び（１５）、Ｙ＝ｇ２ｙを用いて、以下のように表すことができる。
ｅ（ｇ１ｒ，ｇ２ｙ）＝ｅ（ｇ１，ｇ２ｒｙ） （１６）’
バイリニアマップｅの性質により、等式が成立する場合には、乱数ｒ及びｙが同一であることが確認できる。式（１７）は式（１５）及び（１４）を用いて、以下のように表すことができる。
ｅ（ｍ，ｇ２ｒｙ）＝ｅ（ｍｒｙ，ｇ２） （１７）’
これにより、同一の乱数ｒ及びｙを用いているため、平文ｍが同一であることが確認できる。式（１８）は式（１１）、（１５）及び（１４）、Ｘ＝ｇ２ｘを用いて、以下のように表すことができる。
ｅ（ｇ１ｒｘｍｒｘｙ，ｇ２）＝ｅ（ｇ１ｒｍｒｙ，ｇ２ｘ） （１８）’
これにより、同一の乱数ｒ、平文ｍ及びｙを用いているため、ｘが正しいことが確認できる。従来技術と同様に、電子署名σを作成できるのは、秘密鍵ｓｋ＝（ｘ，ｙ）を知っている署名者のみであることが確認できる。このような構成とすることで、従来技術同様、真正性及び完全性を担保しながら、群の元を用いて電子署名を構成することができる。また、検証時の計算式を４つから３つに少なくすることにより、各計算式の計算量が同一の場合には、計算量を２５％軽減することができる。
【００３４】
＜ハードウェア構成＞
図７は、本実施例における電子署名装置１００のハードウェア構成を例示したブロック図である。検証装置２００及び登録装置３００も同様の構成を有する。
【００３５】
図７に例示するように、この例の電子署名装置１００、検証装置２００、登録装置３００は、それぞれＣＰＵ（Central Processing Unit）１１、入力部１２、出力部１３、補助記憶装置１４、ＲＯＭ（Read Only Memory）１５、ＲＡＭ（Random Access Memory）１６及びバス１７を有している。
【００３６】
この例のＣＰＵ１１は、制御部１１ａ、演算部１１ｂ及びレジスタ１１ｃを有し、レジスタ１１ｃに読み込まれた各種プログラムに従って様々な演算処理を実行する。また、入力部１２は、データが入力される入力インターフェース、キーボード、マウス等であり、出力部１３は、データが出力される出力インターフェース等である。補助記憶装置１４は、例えば、ハードディスク、ＭＯ（Magneto-Optical disc）、半導体メモリ等であり、電子署名装置１００、検証装置２００及び登録装置３００としてコンピュータを機能させるためのプログラムが格納されるプログラム領域１４ａ及び各種データが格納されるデータ領域１４ｂを有している。また、ＲＡＭ１６は、ＳＲＡＭ (Static Random Access Memory)、ＤＲＡＭ (Dynamic Random Access Memory)等であり、上記のプログラムが格納されるプログラム領域１６ａ及び各種データが格納されるデータ領域１６ｂを有している。また、バス１７は、ＣＰＵ１１、入力部１２、出力部１３、補助記憶装置１４、ＲＯＭ１５及びＲＡＭ１６を通信可能に接続する。
【００３７】
なお、このようなハードウェアの具体例としては、例えば、パーソナルコンピュータの他、サーバ装置やワークステーション等を例示できる。
【００３８】
＜プログラム構成＞
上述のように、プログラム領域１４ａ，１６ａには、本実施例の電子署名装置１００、検証装置２００、登録装置３００の各処理を実行するための各プログラムが格納される。電子署名プログラム、検証プログラム及び登録プログラムを構成する各プログラムは、単一のプログラム列として記載されていてもよく、また、少なくとも一部のプログラムが別個のモジュールとしてライブラリに格納されていてもよい。また、各プログラムが単体でそれぞれの機能を実現してもよいし、各プログラムがさらに他のライブラリを読み出して各機能を実現するものでもよい。
【００３９】
＜ハードウェアとプログラムとの協働＞
ＣＰＵ１１（図７）は、読み込まれたＯＳ（Operating System）プログラムに従い、補助記憶装置１４のプログラム領域１４ａに格納されている上述のプログラムをＲＡＭ１６のプログラム領域１６ａに書き込む。同様にＣＰＵ１１は、補助記憶装置１４のデータ領域１４ｂに格納されている各種データを、ＲＡＭ１６のデータ領域１６ｂに書き込む。そして、このプログラムやデータが書き込まれたＲＡＭ１６上のアドレスがＣＰＵ１１のレジスタ１１ｃに格納される。ＣＰＵ１１の制御部１１ａは、レジスタ１１ｃに格納されたこれらのアドレスを順次読み出し、読み出したアドレスが示すＲＡＭ１６上の領域からプログラムやデータを読み出し、そのプログラムが示す演算を演算部１１ｂに順次実行させ、その演算結果をレジスタ１１ｃに格納していく。
【００４０】
図３、５は、このようにＣＰＵ１１に上述のプログラムが読み込まれて実行されることにより構成される電子署名装置１００、検証装置２００の機能構成を例示したブロック図である。
【００４１】
ここで、記憶部１０３及び２０３は、補助記憶装置１４、ＲＡＭ１６、レジスタ１１ｃ、その他のバッファメモリやキャッシュメモリ等の何れか、あるいはこれらを併用した記憶領域に相当する。また、通信部１０１と、記憶部１０３と、制御部１０５と、生成元選択部１２０と、乱数生成部１３０と、公開鍵生成部１４０と、電子署名生成部１５０は、ＣＰＵ１１に電子署名プログラムを実行させることにより構成されるものである。また、通信部２０１と、記憶部２０３と、制御部２０５と、判定部２２０は、ＣＰＵ１１に検証プログラムを実行させることにより構成されるものである。
【００４２】
また、本形態の電子署名装置１００、検証装置２００及び登録装置３００は、各制御部１０５、２０５及び３０５の制御のもと各処理を実行する。
【実施例２】
【００４３】
実施例１と異なる部分についてのみ説明する。実施例２記載の電子署名検証システム１０００は、実施例１で示した構成を複数並列に処理し、等式の両辺を乗算にてまとめることにより、複数の平文ｍｉ（１≦ｉ≦ｎ）に対する電子署名σにも対応することができる。
【００４４】
［電子署名検証システム１０００］
電子署名検証システム１０００は、登録装置３００と、電子署名装置１１００と、検証装置１２００からなる。電子署名装置１１００は、複数の平文ｍｉを検証装置１２００に送る際に、電子署名σを添付するために、登録装置３００に対して、公開パラメータｖを要求する。登録装置３００は、ｖを電子署名装置１００へ送る。電子署名装置１１００は、公開パラメータｖから公開鍵ｐｋを生成し、登録装置３００へ送る。さらに、平文ｍｉ、公開鍵ｐｋ及び秘密鍵ｓｋを用いて、電子署名σを生成する。電子署名装置１１００は、電子署名σ及び平文ｍｉを検証装置１２００へ送る。
【００４５】
検証装置１２００は、電子署名σに対応する公開鍵ｐｋを登録装置３００へ要求する。登録装置３００は、ｐｋを検証装置１２００へ送る。検証装置１２００は、電子署名σ、平文ｍｉ、公開鍵ｐｋを用いて、改竄及び成りすまし等が行われていないか検証する。以下、電子署名装置１１００及び検証装置１２００について詳細を説明する。
【００４６】
［電子署名装置１１００］
電子署名装置１１００は、通信部１０１と、記憶部１０３と、制御部１０５と、生成元選択部１２０と、乱数生成部１１３０と、公開鍵生成部１４０と、電子署名生成部１１５０を有する。
【００４７】
＜乱数生成部１１３０及び記憶部１１０３＞
乱数生成部１１３０は、Ｚｑに属する乱数ｒｉ、ｘ及びｙを生成して出力する。つまり、本実施例においては、複数の平文ｍｉに対応する複数の乱数ｒを生成する。乱数生成部１１３０は、乱数ｘ、ｙを公開鍵生成部１４０へ、乱数ｒｉ、ｘ、ｙを電子署名生成部１５０へ出力する。記憶部１１０３は、乱数ｒｉ、ｘ及びｙが記憶される。
【００４８】
＜電子署名生成部１１５０＞
電子署名生成部１１５０は、ｇ１、ｇ２、ｒｉ、ｘ、ｙ及び平文ｍｉ∈Ｇ１が入力され、
ｂｉ１＝ｇ１ｒｉ （２１）
ｂ３＝Πｎｉ＝１ｇ１ｒｉｘｍｉｒｉｘｙ （２３）
ｂｉ４＝ｍｉｒｉｙ （２４）
ｂｉ５＝ｇ２ｒｉｙ （２５）
を計算し、電子署名σ＝（ｂｉ１，ｂ３，ｂｉ４，ｂｉ５）を生成する。なお、式（２１）〜（２５）において、ｒｉとは、上記乱数ｒｉのことを意味する。電子署名生成部１１５０は、生成元選択部１２０から生成元ｇ１、ｇ２を、乱数生成部１１３０から乱数ｒｉ、ｘ、ｙを、さらに平文ｍｉを入力され、電子署名σを出力する。
【００４９】
電子署名装置１１００は、公開鍵ｐｋを登録装置３００へ、電子署名σ及び平文ｍｉを検証装置１２００へ、送る。例えば、通信部１０１を介して、送信する。
【００５０】
このような構成とすることで、実施例１同様、電子署名σを構成する要素の数を５つから４つに少なくすることができ、実施例１と同様の効果を得ることができる。さらに、複数の平文ｍｉ（１≦ｉ≦ｎ）に対して電子署名σを生成することができるため、実施例１の方法により複数の平文に対し、複数の電子署名を作成するのに比べ、処理を軽減することができる。また、電子署名の情報量、通信量を小さくすることができる。
【００５１】
［検証装置１２００］
検証装置１２００は、通信部２０１と、記憶部２０３と、制御部２０５と、判定部１２２０を有する。
【００５２】
＜判定部１２２０＞
判定部１２２０は、以下の等式全てが成立するか否かを判定する。成立する場合には受理し、成立しない場合には拒否する。
ｅ（ｂｉ１，Ｙ）＝ｅ（ｇ１，ｂｉ５） （２６）
ｅ（ｍｉ，ｂｉ５）＝ｅ（ｂｉ４，ｇ２） （２７）
ｅ（ｂ３，ｇ２）＝ｅ（Πｎｉ＝１ｂｉ１ｂｉ４，Ｘ） （２８）
判定部１２２０は、通信部２０１を介して、または、通信部２０１及び記憶部２０３を介して、公開鍵ｐｋ、署名σ及び平文ｍｉが入力される。
【００５３】
このような構成とすることによって、検証時の計算式を４つから３つに少なくし、実施例１同様の効果が得られる。さらに、等式の両辺を乗算にてまとめることにより、実施例１の方法により複数の電子署名を検証するのに比べ、処理を軽減することができる。
【００５４】
［変形例１］
実施例２と異なる部分についてのみ説明する。
【００５５】
［電子署名検証システム２０００］
電子署名検証システム１は、登録装置３００と、電子署名装置２１００と、検証装置２２００からなる。電子署名装置２１００は、複数の平文ｍｉを検証装置２２００に送る際に、電子署名σを添付するために、登録装置３００に対して、公開パラメータｖを要求する。登録装置３００は、ｖを電子署名装置１００へ送る。電子署名装置１１００は、公開パラメータｖから公開鍵ｐｋを生成し、登録装置３００へ送る。さらに、平文ｍｉ、公開鍵ｐｋ及び秘密鍵ｓｋを用いて、電子署名σを生成する。電子署名装置２１００は、電子署名σ及び平文ｍｉを検証装置２２００へ送る。
【００５６】
検証装置２２００は、電子署名σに対応する公開鍵ｐｋを登録装置３００へ要求する。登録装置３００は、ｐｋを検証装置２２００へ送る。検証装置２２００は、電子署名σ、平文ｍｉ、公開鍵ｐｋを用いて、改竄及び成りすまし等が行われていないか検証する。以下、電子署名装置２１００及び検証装置２２００について詳細を説明する。
【００５７】
［電子署名装置２１００］
電子署名装置２１００は、通信部１０１と、記憶部２１０３と、制御部１０５と、生成元選択部１２０と、乱数生成部２１３０と、公開鍵生成部２１４０と、電子署名生成部２１５０を有する。
【００５８】
＜乱数生成部２１３０及び記憶部２１０３＞
乱数生成部２１３０は、Ｚｑに属する乱数ｒ、ｘ及びｙｉを生成して出力する。つまり、本実施例においては、複数の平文ｍｉに対応する複数の乱数ｙｉを生成する。乱数生成部２１３０は、乱数ｘ、ｙｉを公開鍵生成部１４０へ、乱数ｒ、ｘ、ｙｉを電子署名生成部２１５０へ出力する。記憶部２１０３は、乱数ｒ、ｘ及びｙｉが記憶され、特にｘ、ｙｉは秘密鍵ｓｋ＝（ｘ，ｙi）として秘密に記憶される。
【００５９】
＜公開鍵生成部２１４０＞
公開鍵生成部２１４０は、ｘ、ｙｉ、及びｇ２が入力され、Ｘ＝ｇ２ｘ、Ｙｉ＝ｇ２ｙｉ（但し、ｙｉは、ｙｉを表す）を計算し、公開鍵ｐｋ＝（ｖ，ｇ１，ｇ２，Ｘ，Ｙｉ）を生成する。
【００６０】
＜電子署名生成部２１５０＞
電子署名生成部２１５０は、ｇ１、ｇ２、ｒ、ｘ、ｙｉ及び平文ｍｉ∈Ｇ１が入力され、
ｂ１＝ｇ１ｒ （３１）
ｂ３＝ｇ１ｒｘΠｎｉ＝１ｍｉｒｘｙｉ （３３）
ｂｉ４＝ｍｉｒｙｉ （３４）
ｂｉ５＝ｇ２ｒｙｉ （３５）
を計算し、電子署名σ＝（ｂ１，ｂ３，ｂｉ４，ｂｉ５）を生成する。なお、式（３１）〜（３５）において、ｙｉとは、上記乱数ｙｉのことを意味する。電子署名生成部２１５０は、生成元選択部１２０から生成元ｇ１、ｇ２を、乱数生成部２１３０から乱数ｒ、ｘ、ｙｉを、さらに平文ｍｉを入力され、電子署名σを出力する。
このような構成とすることで、実施例２と同様の効果が得られる。
【００６１】
［検証装置２２００］
検証装置２２００は、通信部２０１と、記憶部２０３と、制御部２０５と、判定部２２２０を有する。
【００６２】
＜判定部２２２０＞
判定部２２２０は、以下の等式全てが成立するか否かを判定する。成立する場合には受理し、成立しない場合には拒否する。
【００６３】
ｅ（ｂ１，Ｙｉ）＝ｅ（ｇ１，ｂｉ５） （３６）
ｅ（ｍｉ，ｂｉ５）＝ｅ（ｂｉ４，ｇ２） （３７）
ｅ（ｂ３，ｇ２）＝ｅ（ｂ１Πｎｉ＝１ｂｉ４，Ｘ） （３８）
このような構成とすることによって、実施例２と同様の効果が得られる。
【図面の簡単な説明】
【００６４】
【図１】電子署名検証システム１の構成例を示す図。
【図２】電子署名検証システム１のシーケンス図の一例を示す図。
【図３】電子署名装置１００の構成例を示す図。
【図４】電子署名装置１００の処理フローの一例を示す図。
【図５】検証装置２００の構成例を示す図。
【図６】検証装置２００の処理フローの一例を示す図。
【図７】実施例１における電子署名装置１００のハードウェア構成を例示したブロック図。
【符号の説明】
【００６５】
１ 電子署名検証システム
１００ 電子署名装置 ２００ 検証装置 ３００ 登録装置
１０１、２０１ 通信部 １０３、２０３ 記憶部
１０５、２０５ 制御部 １２０ 生成元選択部
１３０ 乱数生成部 １５０ 電子署名生成部
２２０ 判定部
【技術分野】
【０００１】
本発明は、電気通信システムで送信者の身元を確認する電子署名検証システム、電子署名装置、検証装置、その方法及びプログラムに関する。
【背景技術】
【０００２】
電子署名はメッセージｍに対して、公開鍵ｐｋに対応する秘密鍵ｓｋを知る署名者が、メッセージｍに対して秘密鍵ｓｋを正しく使ったときにのみ計算できる値σを算出し、これを電子的な署名として用いるものである。正しく計算された電子署名は誰でも公開鍵ｐｋを用いてその正当性を検証することが可能である。一方、秘密鍵ｓｋを知らないいかなる第三者も正当な電子署名σを算出することはできない。電子署名は電子現金やクレデンシャルシステムなど、様々な暗号プロトコルにおいて基本的な構成要素として利用されている。
【０００３】
また、利用者のプライバシーを必要とする応用においては、ゼロ知識証明と組み合わせることにより、電子署名σを明かさないまま、あるメッセージに対する電子署名を保持しているという事実を任意の第三者に納得させるなど、高度な利用形態がある。例えば、非特許文献１のようにペアリング技術を用い、群の要素がある関係を満たすという事実を効率的に証明するゼロ知識証明が構成可能となった。これによって、電子署名σが効率的なバイリニアマップを持つ群の要素である、すなわち、σ∈Ｇである場合、前述のように、電子署名σを明かさないまま、正しい電子署名σを保持しているという事実を証明することが可能である。
【０００４】
例えば、非特許文献２記載の技術、いわゆる、CL-Signatureと言われる技術では、メッセージｍ∈Ｚｑに対する電子署名σは３つの群要素（ａ，ｂ，ｃ）∈Ｇ３から構成されている。
【０００５】
しかしながら、CL-Signatureと言われる技術では、ランダムオラクルモデル等の理想化された構成要素を用いず、数論的な仮定のみによって安全性が証明できる既存の電子署名方法では、メッセージｍが群Ｇの要素ではないため、メッセージｍを秘匿した状態で、その秘匿したメッセージに対する正しい電子署名を保持していることを証明する、という応用には適さない。メッセージｍが群Ｇの要素である場合にも、安全な電子署名方法として、非特許文献３がある。以下説明する。
【０００６】
ｑを大きな素数とし、Ｇ１，Ｇ２，ＧＴを位数ｑの群とし、ｅを効率的に計算可能なバイリニアマップｅ：Ｇ１×Ｇ２→ＧＴとし、ｖ＝（ｑ，Ｇ１，Ｇ２，ＧＴ，ｅ）を公開パラメータとする。
【０００７】
署名者は、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択し、Ｚｑに属する乱数ｒ、ｘ及びｙを生成し、Ｘ＝ｇ２ｘ、Ｙ＝ｇ２ｙとする。ｖ、ｇ１、ｇ２、Ｘ、Ｙを公開鍵ｐｋとし、ｘ、ｙを秘密鍵ｓｋとする。
【０００８】
メッセージｍ∈Ｇ１に対して、以下のように、電子署名σを生成する。電子署名σ＝（ａ１，ａ２，ａ３，ａ４，ａ５）∈Ｇ１４×Ｇ２とし、
ａ１＝ｇ１ｒ （１）
ａ２＝ｍｒ （２）
ａ３＝ｇ１ｒｘｍｒｘｙ （３）
ａ４＝ｍｒｙ （４）
ａ５＝ｇ２ｒ （５）
とする。
【０００９】
検証者は、公開鍵ｐｋ及び電子署名σを用いて、以下の等式が成り立つことを確認し、電子署名の真正性及び完全性を検証する。
【００１０】
ｅ（ａ１，ｇ２）＝ｅ（ｇ１，ａ５） （６）
ｅ（ｍ，ａ５）＝ｅ（ａ２，ｇ２） （７）
ｅ（ａ２，Ｙ）＝ｅ（ａ４，ｇ２） （８）
ｅ（ａ３，ｇ２）＝ｅ（ａ１ａ４，Ｘ） （９）
【非特許文献１】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 Hopkins 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，ｅ）とする。電子署名装置は、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する。Ｚｑに属する乱数ｒｉ（但し、１≦ｉ≦ｎであり、ｎは、平文の個数を表す）、ｘ及びｙを生成する。公開パラメータｖと乱数ｒｉ、ｘ及びｙを記憶し、特にｘ、ｙは秘密鍵ｓｋとして秘密に記憶する。ｘ、ｙ、ｇ１及びｇ２を用いて、Ｘ＝ｇ２ｘ、Ｙ＝ｇ２ｙを計算し、公開鍵ｐｋを生成する。ｇ１、ｇ２、ｒｉ、ｘ、ｙ及び平文ｍｉを用いて、ｂｉ１＝ｇ１ｒｉ、ｂ３＝Πｎｉ＝１ｇ１ｒｉｘｍｉｒｉｘｙ、ｂｉ４＝ｍｉｒｉｙ、ｂｉ５＝ｇ２ｒｉｙを計算し、電子署名σ＝（ｂｉ１，ｂ３，ｂｉ４，ｂｉ５）を生成する。検証装置は、公開鍵ｐｋ、電子署名σ及び平文ｍｉを記憶する。
【００１３】
（１）ｅ（ｂｉ１，Ｙ）＝ｅ（ｇ１，ｂｉ５）
（２）ｅ（ｍｉ，ｂｉ５）＝ｅ（ｂｉ４，ｇ２）
（３）ｅ（ｂ３，ｇ２）＝ｅ（Πｎｉ＝１ｂｉ１ｂｉ４，Ｘ）
（１）〜（３）の等式全てが成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する。登録装置は、公開パラメータｖ及び公開鍵ｐｋを記憶する記憶部を有する。電子署名装置は、登録装置から公開パラメータｖを受け取り、公開鍵ｐｋを登録装置へ、電子署名σ及び平文ｍｉを検証装置へ、送る。検証装置は、登録装置から公開鍵ｐｋを、電子署名装置から電子署名σ及び平文ｍｉを、受け取る。
【発明の効果】
【００１４】
本発明の電子署名検証方法及び装置によれば、従来技術同様、真正性及び完全性を担保しながら、群の元を用いて電子署名を構成することができ、かつ、電子署名を構成する要素の数を少なくすることにより、電子署名長が短く、通信量が少なくすることができる。また、検証時の計算式の少なくすることにより、計算量を少なくすることができる。
【発明を実施するための最良の形態】
【００１５】
ここで、本発明の実施例について説明する。
【実施例１】
【００１６】
［電子署名検証システム１］
図１は、電子署名検証システム１の構成例を示す図である。図２は、電子署名検証システム１のシーケンス図の一例を示す図である。電子署名検証システム１は、登録装置３００と、電子署名装置１００と、検証装置２００からなる。
【００１７】
ｑを大きな素数とし、Ｇ１，Ｇ２，ＧＴを位数ｑの群とし、ｅを効率的に計算可能なバイリニアマップｅ：Ｇ１×Ｇ２→ＧＴとし、ｖ＝（ｑ，Ｇ１，Ｇ２，ＧＴ，ｅ）を公開パラメータとする。なお、ｇａとは、ｇ∈Ｇに対し、群Ｇで定義される演算をａ回行うことを意味する。バイリニアマップとしては、例えば、ＷｅｉｌペアリングやＴａｔｅペアリング等が考えられる。
【００１８】
電子署名装置１００は、平文ｍを検証装置２００に送る際に、電子署名σを添付するために、登録装置３００に対して、公開パラメータｖを要求する（ｓ１０）。登録装置３００は、ｖを電子署名装置１００へ送る（ｓ１２）。電子署名装置１００は、公開パラメータｖから公開鍵ｐｋを生成し、登録装置３００へ送る（ｓ１４）。登録装置３００は、公開鍵ｐｋを登録及び公開する（ｓ１６）。なお、送るたびに公開パラメータを要求しなくとも、記憶している公開パラメータを利用して公開鍵を生成してもよい。さらに、平文ｍ、公開鍵ｐｋ及び秘密鍵ｓｋを用いて、電子署名σを生成する。電子署名装置１００は、電子署名σ及び平文ｍを検証装置へ送る（ｓ１８）。
【００１９】
検証装置２００は、電子署名σに対応する公開鍵ｐｋを登録装置３００へ要求する（ｓ２０）。登録装置３００は、公開鍵ｐｋを検証装置２００へ送る（ｓ２２）。検証装置２００は、電子署名σ、平文ｍ、公開鍵ｐｋを用いて、改竄及び成りすまし等が行われていないか検証する（ｓ２４）。以下、各装置及び各処理について詳細を説明する。
【００２０】
［登録装置３００］
登録装置３００は、公開パラメータｖを登録及び公開している。例えば、登録装置３００は、信頼できる第三者等が管理し、通信部３０１と、記憶部３０３と、制御部３０５を有する。登録装置３００は、通信部３０１を介して、電子署名装置及び検証装置と通信する。通信部３０１は、例えば、ＬＡＮアダプタ等により構成され、ＬＡＮやインターネット等からなる通信回線と接続される。但し、必ずしも通信部を有さずともよく、例えば、キーボード等の入力装置から公開パラメータを入力してもよいし、また、ＵＳＢメモリ等の可搬媒体に公開パラメータを記憶し、それを入力してもよい。以下、同様に各装置（電子署名装置及び検証装置）は送信部１０１、２０１を有さずともよく、装置間のデータの入出力は、通信以外の方法であってもよい。記憶部３０３は、公開パラメータ、公開鍵等を記憶する。なお、上記「登録」とは、記憶部３０３に記憶することを意味してもよい。また、「公開」とは、利用者の求めに応じて、情報（例えば、公開パラメータ）を閲覧可能、または、取得可能とすることを意味する。制御部３０５は、各処理を制御する。
【００２１】
［電子署名装置１００］
図３は、電子署名装置１００の構成例を示す図である。図４は、電子署名装置１００の処理フローの一例を示す図である。電子署名装置１００は、通信部１０１と、記憶部１０３と、制御部１０５と、生成元選択部１２０と、乱数生成部１３０と、公開鍵生成部１４０と、電子署名生成部１５０を有する。
【００２２】
＜制御部１０５及び通信部１０１＞
本実施例の電子署名装置１００は、制御部１０５の制御のもと各処理を実行する。電子署名装置１００は、登録装置３００から公開パラメータｖを受け取る。例えば、通信部１０１は、登録装置３００及び検証装置２００と通信を行い、登録装置３００から公開パラメータｖを受信する（ｓ１０１）。以下、特に記述しなくとも、登録装置３００及び検証装置２００と通信する際には、通信部１０１を介して行われるものとする。
【００２３】
受信した公開パラメータｖを記憶部１０３に記憶する（ｓ１０３）。また、特に示さない限り、入出力される各データや演算過程の各データは、逐一、記憶部１０３に格納・読み出され、各演算処理が進められる。但し、必ずしも記憶部１０３に記憶しなければならないわけではなく、各部間で直接データを受け渡してもよい。
【００２４】
＜生成元選択部１２０、乱数生成部１３０及び記憶部１０３＞
生成元選択部１２０は、群Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する（ｓ１２０）。生成元選択部１２０は、通信部１０１を介して、または、通信部１０１及び記憶部１０３を介して、公開パラメータｖを入力され、生成元ｇ１及びｇ２を公開鍵生成部１４０及び電子署名生成部１５０へ、出力する。乱数生成部１３０は、Ｚｑに属する乱数ｒ、ｘ及びｙを生成して出力する（ｓ１３０）。乱数生成部１３０は、乱数ｘ、ｙを公開鍵生成部１４０へ、乱数ｒ、ｘ、ｙを電子署名生成部１５０へ出力する。記憶部１０３は、乱数ｒ、ｘ及びｙが記憶され、特にｘ、ｙは秘密鍵ｓｋ＝（ｘ，ｙ）として秘密に記憶される（ｓ１３３）。なお、秘密鍵ｓｋには、対応する公開鍵ｐｋを含め、ｓｋ＝（ｐｋ，ｘ，ｙ）としてもよい。他の実施例においても同様である。公開鍵ｐｋについての詳細は後述する。
【００２５】
＜公開鍵生成部１４０＞
公開鍵生成部１４０は、ｘ、ｙ、ｇ１及びｇ２が入力され、Ｘ＝ｇ２ｘ、Ｙ＝ｇ２ｙを計算し、公開鍵ｐｋ＝（ｖ，ｇ１，ｇ２，Ｘ，Ｙ）を生成する（ｓ１４０）。公開鍵ｐｋは、通信部１０１を介して、登録装置３００へ送られる。なお、公開鍵ｐｋには、利用した公開パラメータを表示する情報ｉ等を含めｐｋ＝（ｉ，ｇ１，ｇ２，Ｘ，Ｙ）としてもよい。この場合には、以下で説明する検証装置２００は、情報ｉに基づいて、登録装置３００に対応する公開パラメータｖｉを要求する。また、登録装置３００の記憶している公開パラメータの中から対応する公開パラメータを特定することができる場合には、公開鍵ｐｋに公開パラメータｖや、公開パラメータを表示する情報ｉ等を含まなくともよく、検証装置２００は、平文ｍ及び電子署名σを受け付けた際に、登録装置３００に公開パラメータｖを要求する。
【００２６】
＜電子署名生成部１５０＞
電子署名生成部１５０は、ｇ１、ｇ２、ｒ、ｘ、ｙ及び平文ｍ∈Ｇ１が入力され、
ｂ１＝ｇ１ｒ （１１）
ｂ３＝ｇ１ｒｘｍｒｘｙ （１３）
ｂ４＝ｍｒｙ （１４）
ｂ５＝ｇ２ｒｙ （１５）
を計算し、電子署名σ＝（ｂ１，ｂ３，ｂ４，ｂ５）を生成する（ｓ１５０）。電子署名生成部１５０は、生成元選択部１２０から生成元ｇ１、ｇ２を、乱数生成部１３０から乱数ｒ、ｘ、ｙを、さらに平文ｍを入力され、電子署名σを出力する。なお、平文ｍ∈Ｚｑであり、補助記憶装置やメモリ上のデータ等、もしくは、入力インターフェース、キーボード、マウス等から入力されるデータである。
【００２７】
電子署名装置１００は、公開鍵ｐｋを登録装置３００へ、電子署名σ及び平文ｍを検証装置２００へ、送る。例えば、通信部１０１を介して、送信する（ｓ１５３）。
【００２８】
このような構成とすることで、電子署名σを構成する要素の数を５つから４つに少なくすることができる。これにより、例えば、電子署名σの各要素を生成する演算量が同一の場合には、演算量を２０％軽減できる。また、例えば、電子署名σの各要素が同一の情報量を有している場合には、電子署名長を２０％短く作成することができる。これにより電子署名σに要する通信量を軽減することもできる。なお、公開鍵の生成（ｓ１４０）と電子署名の生成（ｓ１５０）は、どちらが先に行われてもよい。
【００２９】
［検証装置２００］
図５は、検証装置２００の構成例を示す。図６は、検証装置１００の処理フローの一例を示す図である。検証装置２００は、通信部２０１と、記憶部２０３と、制御部２０５と、判定部２２０を有する。
＜制御部２０５、通信部２０１及び記憶部２０３＞
本実施例の検証装置２００は、制御部２０５の制御のもと各処理を実行する。検証装置は、登録装置から公開鍵ｐｋを、電子署名装置から電子署名σ及び平文ｍを、受け取る。例えば、通信部２０１は、登録装置３００及び検証装置１００と通信を行う。登録装置３００から公開鍵ｐｋを受信する（ｓ２０１）。電子署名装置１００から電子署名σ及び平文ｍを受信する（ｓ２０２）。機能、構成等は、通信部１０１と同様である。記憶部２０３は、公開鍵ｐｋ、電子署名σ及び平文ｍが記憶される（ｓ２０３）。
【００３０】
＜判定部２２０＞
判定部２２０は、以下の等式全てが成立するか否かを判定する（ｓ２２０）。成立する場合には受理し（ｓ２２３）、成立しない場合には拒否する（ｓ２２５）。
【００３１】
ｅ（ｂ１，Ｙ）＝ｅ（ｇ１，ｂ５） （１６）
ｅ（ｍ，ｂ５）＝ｅ（ｂ４，ｇ２） （１７）
ｅ（ｂ３，ｇ２）＝ｅ（ｂ１ｂ４，Ｘ） （１８）
判定部２２０は、通信部２０１を介して、または、通信部２０１及び記憶部２０３を介して、公開鍵ｐｋ、署名σ及び平文ｍが入力される。以下、上記の式（１６）〜（１８）について従来技術の式（６）〜（９）と比較して説明する。
【００３２】
＜非特許文献３の検証方法＞
従来技術では、式（６）は式（１）及び（５）を用いて、以下のように表すことができる。
ｅ（ｇ１ｒ，ｇ２）＝ｅ（ｇ１，ｇ２ｒ） （６）’
これにより、乱数ｒが同一であることを確認する。式（７）は式（１）及び（２）を用いて、以下のように表すことができる。
ｅ（ｍ，ｇ２ｒ）＝ｅ（ｍｒ，ｇ２） （７）’
これにより、同一の乱数ｒを用いているため、ｍが同一であることを確認する。式（８）は式（２）、（４）、Ｙ＝ｇ２ｙを用いて、以下のように表すことができる。
ｅ（ｍｒ，ｇ２ｙ）＝ｅ（ｍｒｙ，ｇ２） （８）’
これにより、同一の乱数ｒと平文ｍを用いているため、等式が成り立つ場合には、ｙが正しいことが確認できる。式（９）は、式（１）、（３）、（４）、Ｘ＝ｇ２ｘを用いて、以下のように表すことができる。
ｅ（ｇ１ｒｘｍｒｘｙ，ｇ２）＝ｅ（ｇ１ｒｍｒｙ，ｇ２ｘ） （９）’
これにより、同一の乱数ｒ、平文ｍ、ｙを用いているため、等式が成り立つ場合には、ｘが正しいことが確認できる。これらの処理により、電子署名σを作成できるのは、秘密鍵ｓｋ＝（ｘ，ｙ）を知っている署名者のみであることが確認できる。
【００３３】
＜本実施例の検証方法＞
一方、本発明では、式（１６）は式（１１）及び（１５）、Ｙ＝ｇ２ｙを用いて、以下のように表すことができる。
ｅ（ｇ１ｒ，ｇ２ｙ）＝ｅ（ｇ１，ｇ２ｒｙ） （１６）’
バイリニアマップｅの性質により、等式が成立する場合には、乱数ｒ及びｙが同一であることが確認できる。式（１７）は式（１５）及び（１４）を用いて、以下のように表すことができる。
ｅ（ｍ，ｇ２ｒｙ）＝ｅ（ｍｒｙ，ｇ２） （１７）’
これにより、同一の乱数ｒ及びｙを用いているため、平文ｍが同一であることが確認できる。式（１８）は式（１１）、（１５）及び（１４）、Ｘ＝ｇ２ｘを用いて、以下のように表すことができる。
ｅ（ｇ１ｒｘｍｒｘｙ，ｇ２）＝ｅ（ｇ１ｒｍｒｙ，ｇ２ｘ） （１８）’
これにより、同一の乱数ｒ、平文ｍ及びｙを用いているため、ｘが正しいことが確認できる。従来技術と同様に、電子署名σを作成できるのは、秘密鍵ｓｋ＝（ｘ，ｙ）を知っている署名者のみであることが確認できる。このような構成とすることで、従来技術同様、真正性及び完全性を担保しながら、群の元を用いて電子署名を構成することができる。また、検証時の計算式を４つから３つに少なくすることにより、各計算式の計算量が同一の場合には、計算量を２５％軽減することができる。
【００３４】
＜ハードウェア構成＞
図７は、本実施例における電子署名装置１００のハードウェア構成を例示したブロック図である。検証装置２００及び登録装置３００も同様の構成を有する。
【００３５】
図７に例示するように、この例の電子署名装置１００、検証装置２００、登録装置３００は、それぞれＣＰＵ（Central Processing Unit）１１、入力部１２、出力部１３、補助記憶装置１４、ＲＯＭ（Read Only Memory）１５、ＲＡＭ（Random Access Memory）１６及びバス１７を有している。
【００３６】
この例のＣＰＵ１１は、制御部１１ａ、演算部１１ｂ及びレジスタ１１ｃを有し、レジスタ１１ｃに読み込まれた各種プログラムに従って様々な演算処理を実行する。また、入力部１２は、データが入力される入力インターフェース、キーボード、マウス等であり、出力部１３は、データが出力される出力インターフェース等である。補助記憶装置１４は、例えば、ハードディスク、ＭＯ（Magneto-Optical disc）、半導体メモリ等であり、電子署名装置１００、検証装置２００及び登録装置３００としてコンピュータを機能させるためのプログラムが格納されるプログラム領域１４ａ及び各種データが格納されるデータ領域１４ｂを有している。また、ＲＡＭ１６は、ＳＲＡＭ (Static Random Access Memory)、ＤＲＡＭ (Dynamic Random Access Memory)等であり、上記のプログラムが格納されるプログラム領域１６ａ及び各種データが格納されるデータ領域１６ｂを有している。また、バス１７は、ＣＰＵ１１、入力部１２、出力部１３、補助記憶装置１４、ＲＯＭ１５及びＲＡＭ１６を通信可能に接続する。
【００３７】
なお、このようなハードウェアの具体例としては、例えば、パーソナルコンピュータの他、サーバ装置やワークステーション等を例示できる。
【００３８】
＜プログラム構成＞
上述のように、プログラム領域１４ａ，１６ａには、本実施例の電子署名装置１００、検証装置２００、登録装置３００の各処理を実行するための各プログラムが格納される。電子署名プログラム、検証プログラム及び登録プログラムを構成する各プログラムは、単一のプログラム列として記載されていてもよく、また、少なくとも一部のプログラムが別個のモジュールとしてライブラリに格納されていてもよい。また、各プログラムが単体でそれぞれの機能を実現してもよいし、各プログラムがさらに他のライブラリを読み出して各機能を実現するものでもよい。
【００３９】
＜ハードウェアとプログラムとの協働＞
ＣＰＵ１１（図７）は、読み込まれたＯＳ（Operating System）プログラムに従い、補助記憶装置１４のプログラム領域１４ａに格納されている上述のプログラムをＲＡＭ１６のプログラム領域１６ａに書き込む。同様にＣＰＵ１１は、補助記憶装置１４のデータ領域１４ｂに格納されている各種データを、ＲＡＭ１６のデータ領域１６ｂに書き込む。そして、このプログラムやデータが書き込まれたＲＡＭ１６上のアドレスがＣＰＵ１１のレジスタ１１ｃに格納される。ＣＰＵ１１の制御部１１ａは、レジスタ１１ｃに格納されたこれらのアドレスを順次読み出し、読み出したアドレスが示すＲＡＭ１６上の領域からプログラムやデータを読み出し、そのプログラムが示す演算を演算部１１ｂに順次実行させ、その演算結果をレジスタ１１ｃに格納していく。
【００４０】
図３、５は、このようにＣＰＵ１１に上述のプログラムが読み込まれて実行されることにより構成される電子署名装置１００、検証装置２００の機能構成を例示したブロック図である。
【００４１】
ここで、記憶部１０３及び２０３は、補助記憶装置１４、ＲＡＭ１６、レジスタ１１ｃ、その他のバッファメモリやキャッシュメモリ等の何れか、あるいはこれらを併用した記憶領域に相当する。また、通信部１０１と、記憶部１０３と、制御部１０５と、生成元選択部１２０と、乱数生成部１３０と、公開鍵生成部１４０と、電子署名生成部１５０は、ＣＰＵ１１に電子署名プログラムを実行させることにより構成されるものである。また、通信部２０１と、記憶部２０３と、制御部２０５と、判定部２２０は、ＣＰＵ１１に検証プログラムを実行させることにより構成されるものである。
【００４２】
また、本形態の電子署名装置１００、検証装置２００及び登録装置３００は、各制御部１０５、２０５及び３０５の制御のもと各処理を実行する。
【実施例２】
【００４３】
実施例１と異なる部分についてのみ説明する。実施例２記載の電子署名検証システム１０００は、実施例１で示した構成を複数並列に処理し、等式の両辺を乗算にてまとめることにより、複数の平文ｍｉ（１≦ｉ≦ｎ）に対する電子署名σにも対応することができる。
【００４４】
［電子署名検証システム１０００］
電子署名検証システム１０００は、登録装置３００と、電子署名装置１１００と、検証装置１２００からなる。電子署名装置１１００は、複数の平文ｍｉを検証装置１２００に送る際に、電子署名σを添付するために、登録装置３００に対して、公開パラメータｖを要求する。登録装置３００は、ｖを電子署名装置１００へ送る。電子署名装置１１００は、公開パラメータｖから公開鍵ｐｋを生成し、登録装置３００へ送る。さらに、平文ｍｉ、公開鍵ｐｋ及び秘密鍵ｓｋを用いて、電子署名σを生成する。電子署名装置１１００は、電子署名σ及び平文ｍｉを検証装置１２００へ送る。
【００４５】
検証装置１２００は、電子署名σに対応する公開鍵ｐｋを登録装置３００へ要求する。登録装置３００は、ｐｋを検証装置１２００へ送る。検証装置１２００は、電子署名σ、平文ｍｉ、公開鍵ｐｋを用いて、改竄及び成りすまし等が行われていないか検証する。以下、電子署名装置１１００及び検証装置１２００について詳細を説明する。
【００４６】
［電子署名装置１１００］
電子署名装置１１００は、通信部１０１と、記憶部１０３と、制御部１０５と、生成元選択部１２０と、乱数生成部１１３０と、公開鍵生成部１４０と、電子署名生成部１１５０を有する。
【００４７】
＜乱数生成部１１３０及び記憶部１１０３＞
乱数生成部１１３０は、Ｚｑに属する乱数ｒｉ、ｘ及びｙを生成して出力する。つまり、本実施例においては、複数の平文ｍｉに対応する複数の乱数ｒを生成する。乱数生成部１１３０は、乱数ｘ、ｙを公開鍵生成部１４０へ、乱数ｒｉ、ｘ、ｙを電子署名生成部１５０へ出力する。記憶部１１０３は、乱数ｒｉ、ｘ及びｙが記憶される。
【００４８】
＜電子署名生成部１１５０＞
電子署名生成部１１５０は、ｇ１、ｇ２、ｒｉ、ｘ、ｙ及び平文ｍｉ∈Ｇ１が入力され、
ｂｉ１＝ｇ１ｒｉ （２１）
ｂ３＝Πｎｉ＝１ｇ１ｒｉｘｍｉｒｉｘｙ （２３）
ｂｉ４＝ｍｉｒｉｙ （２４）
ｂｉ５＝ｇ２ｒｉｙ （２５）
を計算し、電子署名σ＝（ｂｉ１，ｂ３，ｂｉ４，ｂｉ５）を生成する。なお、式（２１）〜（２５）において、ｒｉとは、上記乱数ｒｉのことを意味する。電子署名生成部１１５０は、生成元選択部１２０から生成元ｇ１、ｇ２を、乱数生成部１１３０から乱数ｒｉ、ｘ、ｙを、さらに平文ｍｉを入力され、電子署名σを出力する。
【００４９】
電子署名装置１１００は、公開鍵ｐｋを登録装置３００へ、電子署名σ及び平文ｍｉを検証装置１２００へ、送る。例えば、通信部１０１を介して、送信する。
【００５０】
このような構成とすることで、実施例１同様、電子署名σを構成する要素の数を５つから４つに少なくすることができ、実施例１と同様の効果を得ることができる。さらに、複数の平文ｍｉ（１≦ｉ≦ｎ）に対して電子署名σを生成することができるため、実施例１の方法により複数の平文に対し、複数の電子署名を作成するのに比べ、処理を軽減することができる。また、電子署名の情報量、通信量を小さくすることができる。
【００５１】
［検証装置１２００］
検証装置１２００は、通信部２０１と、記憶部２０３と、制御部２０５と、判定部１２２０を有する。
【００５２】
＜判定部１２２０＞
判定部１２２０は、以下の等式全てが成立するか否かを判定する。成立する場合には受理し、成立しない場合には拒否する。
ｅ（ｂｉ１，Ｙ）＝ｅ（ｇ１，ｂｉ５） （２６）
ｅ（ｍｉ，ｂｉ５）＝ｅ（ｂｉ４，ｇ２） （２７）
ｅ（ｂ３，ｇ２）＝ｅ（Πｎｉ＝１ｂｉ１ｂｉ４，Ｘ） （２８）
判定部１２２０は、通信部２０１を介して、または、通信部２０１及び記憶部２０３を介して、公開鍵ｐｋ、署名σ及び平文ｍｉが入力される。
【００５３】
このような構成とすることによって、検証時の計算式を４つから３つに少なくし、実施例１同様の効果が得られる。さらに、等式の両辺を乗算にてまとめることにより、実施例１の方法により複数の電子署名を検証するのに比べ、処理を軽減することができる。
【００５４】
［変形例１］
実施例２と異なる部分についてのみ説明する。
【００５５】
［電子署名検証システム２０００］
電子署名検証システム１は、登録装置３００と、電子署名装置２１００と、検証装置２２００からなる。電子署名装置２１００は、複数の平文ｍｉを検証装置２２００に送る際に、電子署名σを添付するために、登録装置３００に対して、公開パラメータｖを要求する。登録装置３００は、ｖを電子署名装置１００へ送る。電子署名装置１１００は、公開パラメータｖから公開鍵ｐｋを生成し、登録装置３００へ送る。さらに、平文ｍｉ、公開鍵ｐｋ及び秘密鍵ｓｋを用いて、電子署名σを生成する。電子署名装置２１００は、電子署名σ及び平文ｍｉを検証装置２２００へ送る。
【００５６】
検証装置２２００は、電子署名σに対応する公開鍵ｐｋを登録装置３００へ要求する。登録装置３００は、ｐｋを検証装置２２００へ送る。検証装置２２００は、電子署名σ、平文ｍｉ、公開鍵ｐｋを用いて、改竄及び成りすまし等が行われていないか検証する。以下、電子署名装置２１００及び検証装置２２００について詳細を説明する。
【００５７】
［電子署名装置２１００］
電子署名装置２１００は、通信部１０１と、記憶部２１０３と、制御部１０５と、生成元選択部１２０と、乱数生成部２１３０と、公開鍵生成部２１４０と、電子署名生成部２１５０を有する。
【００５８】
＜乱数生成部２１３０及び記憶部２１０３＞
乱数生成部２１３０は、Ｚｑに属する乱数ｒ、ｘ及びｙｉを生成して出力する。つまり、本実施例においては、複数の平文ｍｉに対応する複数の乱数ｙｉを生成する。乱数生成部２１３０は、乱数ｘ、ｙｉを公開鍵生成部１４０へ、乱数ｒ、ｘ、ｙｉを電子署名生成部２１５０へ出力する。記憶部２１０３は、乱数ｒ、ｘ及びｙｉが記憶され、特にｘ、ｙｉは秘密鍵ｓｋ＝（ｘ，ｙi）として秘密に記憶される。
【００５９】
＜公開鍵生成部２１４０＞
公開鍵生成部２１４０は、ｘ、ｙｉ、及びｇ２が入力され、Ｘ＝ｇ２ｘ、Ｙｉ＝ｇ２ｙｉ（但し、ｙｉは、ｙｉを表す）を計算し、公開鍵ｐｋ＝（ｖ，ｇ１，ｇ２，Ｘ，Ｙｉ）を生成する。
【００６０】
＜電子署名生成部２１５０＞
電子署名生成部２１５０は、ｇ１、ｇ２、ｒ、ｘ、ｙｉ及び平文ｍｉ∈Ｇ１が入力され、
ｂ１＝ｇ１ｒ （３１）
ｂ３＝ｇ１ｒｘΠｎｉ＝１ｍｉｒｘｙｉ （３３）
ｂｉ４＝ｍｉｒｙｉ （３４）
ｂｉ５＝ｇ２ｒｙｉ （３５）
を計算し、電子署名σ＝（ｂ１，ｂ３，ｂｉ４，ｂｉ５）を生成する。なお、式（３１）〜（３５）において、ｙｉとは、上記乱数ｙｉのことを意味する。電子署名生成部２１５０は、生成元選択部１２０から生成元ｇ１、ｇ２を、乱数生成部２１３０から乱数ｒ、ｘ、ｙｉを、さらに平文ｍｉを入力され、電子署名σを出力する。
このような構成とすることで、実施例２と同様の効果が得られる。
【００６１】
［検証装置２２００］
検証装置２２００は、通信部２０１と、記憶部２０３と、制御部２０５と、判定部２２２０を有する。
【００６２】
＜判定部２２２０＞
判定部２２２０は、以下の等式全てが成立するか否かを判定する。成立する場合には受理し、成立しない場合には拒否する。
【００６３】
ｅ（ｂ１，Ｙｉ）＝ｅ（ｇ１，ｂｉ５） （３６）
ｅ（ｍｉ，ｂｉ５）＝ｅ（ｂｉ４，ｇ２） （３７）
ｅ（ｂ３，ｇ２）＝ｅ（ｂ１Πｎｉ＝１ｂｉ４，Ｘ） （３８）
このような構成とすることによって、実施例２と同様の効果が得られる。
【図面の簡単な説明】
【００６４】
【図１】電子署名検証システム１の構成例を示す図。
【図２】電子署名検証システム１のシーケンス図の一例を示す図。
【図３】電子署名装置１００の構成例を示す図。
【図４】電子署名装置１００の処理フローの一例を示す図。
【図５】検証装置２００の構成例を示す図。
【図６】検証装置２００の処理フローの一例を示す図。
【図７】実施例１における電子署名装置１００のハードウェア構成を例示したブロック図。
【符号の説明】
【００６５】
１ 電子署名検証システム
１００ 電子署名装置 ２００ 検証装置 ３００ 登録装置
１０１、２０１ 通信部 １０３、２０３ 記憶部
１０５、２０５ 制御部 １２０ 生成元選択部
１３０ 乱数生成部 １５０ 電子署名生成部
２２０ 判定部
【特許請求の範囲】
【請求項１】
登録装置と、電子署名装置と、検証装置からなる電子署名検証システムにおいて、
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）とし、
前記電子署名装置は、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択部と、
Ｚｑに属する乱数ｒｉ（但し、１≦ｉ≦ｎであり、ｎは、平文の個数を表す）、ｘ及びｙを生成する乱数生成部と、
前記公開パラメータｖと前記乱数ｒｉ、ｘ及びｙが記憶され、特にｘ、ｙは秘密鍵ｓｋとして秘密に記憶される記憶部と、
前記ｘ、ｙ、ｇ１及びｇ２が入力され、Ｘ＝ｇ２ｘ、Ｙ＝ｇ２ｙを計算し、公開鍵ｐｋを生成する公開鍵生成部と、
前記ｇ１、ｇ２、ｒｉ、ｘ、ｙ及び平文ｍｉが入力され、ｂｉ１＝ｇ１ｒｉ、ｂ３＝Πｎｉ＝１ｇ１ｒｉｘｍｉｒｉｘｙ、ｂｉ４＝ｍｉｒｉｙ、ｂｉ５＝ｇ２ｒｉｙを計算し、電子署名σ＝（ｂｉ１，ｂ３，ｂｉ４，ｂｉ５）を生成する電子署名生成部と、を有し、
前記検証装置は、前記公開鍵ｐｋ、電子署名σ及び平文ｍｉが記憶される記憶部と、
（１）ｅ（ｂｉ１，Ｙ）＝ｅ（ｇ１，ｂｉ５）
（２）ｅ（ｍｉ，ｂｉ５）＝ｅ（ｂｉ４，ｇ２）
（３）ｅ（ｂ３，ｇ２）＝ｅ（Πｎｉ＝１ｂｉ１ｂｉ４，Ｘ）
（１）〜（３）の等式全てが成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定部を有し、
前記登録装置は、前記公開パラメータｖ及び公開鍵ｐｋを記憶する記憶部を有し、
前記電子署名装置は、前記登録装置から前記公開パラメータｖを受け取り、前記公開鍵ｐｋを前記登録装置へ、電子署名σ及び平文ｍｉを検証装置へ、送り、
前記検証装置は、前記登録装置から前記公開鍵ｐｋを、前記電子署名装置から前記電子署名σ及び平文ｍｉを、受け取る、
ことを特徴とする電子署名検証システム。
【請求項２】
登録装置と、電子署名装置と、検証装置からなる電子署名検証システムにおいて、
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）とし、
前記電子署名装置は、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択部と、
Ｚｑに属する乱数ｒ、ｘ及びｙｉ（但し、１≦ｉ≦ｎであり、ｎは、平文の個数を表す）を生成する乱数生成部と、
前記公開パラメータｖと前記乱数ｒ、ｘ及びｙｉが記憶され、特にｘ、ｙｉは秘密鍵ｓｋ＝（ｘ，ｙｉ）として秘密に記憶される記憶部と、
前記ｘ、ｙｉ、ｇ１及びｇ２が入力され、Ｘ＝ｇ２ｘ、Ｙｉ＝ｇ２ｙｉを計算し、公開鍵ｐｋを生成する公開鍵生成部と、
前記ｇ１、ｇ２、ｒ、ｘ、ｙｉ及び平文ｍｉが入力され、ｂ１＝ｇ１ｒ、ｂ３＝ｇ１ｒｘΠｎｉ＝１ｍｉｒｘｙｉ、ｂｉ４＝ｍｉｒｙｉ、ｂｉ５＝ｇ２ｒｙｉを計算し、電子署名σ＝（ｂ１，ｂ３，ｂｉ４，ｂｉ５）を生成する電子署名生成部と、を有し、
前記検証装置は、前記公開鍵ｐｋ、電子署名σ及び平文ｍｉが記憶される記憶部と、
（１）ｅ（ｂ１，Ｙｉ）＝ｅ（ｇ１，ｂｉ５）
（２）ｅ（ｍｉ，ｂｉ５）＝ｅ（ｂｉ４，ｇ２）
（３）ｅ（ｂ３，ｇ２）＝ｅ（ｂ１Πｎｉ＝１ｂｉ４，Ｘ）
（１）〜（３）の等式全てが成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定部を有し、
前記登録装置は、前記公開パラメータｖ及び公開鍵ｐｋを記憶する記憶部を有し、
前記電子署名装置は、前記登録装置から前記公開パラメータｖを受け取り、前記公開鍵ｐｋを前記登録装置へ、電子署名σ及び平文ｍｉを検証装置へ、送り、
前記検証装置は、前記登録装置から前記公開鍵ｐｋを、前記電子署名装置から前記電子署名σ及び平文ｍｉを、受け取る、
ことを特徴とする電子署名検証システム。
【請求項３】
請求項１または２記載の電子署名検証システムであって、
ｎ＝１である、
ことを特徴とする電子署名検証システム。
【請求項４】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）とし、
Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択部と、
Ｚｑに属する乱数ｒｉ（但し、１≦ｉ≦ｎであり、ｎは、平文の個数を表す）、ｘ及びｙを生成する乱数生成部と、
前記公開パラメータｖと前記乱数ｒｉ、ｘ及びｙが記憶され、特にｘ、ｙは秘密鍵ｓｋとして秘密に記憶される記憶部と、
前記ｘ、ｙ、ｇ１及びｇ２が入力され、Ｘ＝ｇ２ｘ、Ｙ＝ｇ２ｙを計算し、公開鍵ｐｋを生成する公開鍵生成部と、
前記ｇ１、ｇ２、ｒｉ、ｘ、ｙ及び平文ｍｉが入力され、ｂｉ１＝ｇ１ｒｉ、ｂ３＝Πｎｉ＝１ｇ１ｒｉｘｍｉｒｉｘｙ、ｂｉ４＝ｍｉｒｉｙ、ｂｉ５＝ｇ２ｒｉｙを計算し、電子署名σ＝（ｂｉ１，ｂ３，ｂｉ４，ｂｉ５）を生成する電子署名生成部と、を有し、
登録装置から前記公開パラメータｖを受け取り、前記公開鍵ｐｋを前記登録装置へ、電子署名σ及び平文ｍｉを検証装置へ、送る、
ことを特徴とする電子署名装置。
【請求項５】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、
公開鍵ｐｋ、電子署名σ及び平文ｍｉ（但し、１≦ｉ≦ｎであり、ｎは、平文の個数を表す）が記憶される記憶部と、
（１）ｅ（ｂｉ１，Ｙ）＝ｅ（ｇ１，ｂｉ５）
（２）ｅ（ｍｉ，ｂｉ５）＝ｅ（ｂｉ４，ｇ２）
（３）ｅ（ｂ３，ｇ２）＝ｅ（Πｎｉ＝１ｂｉ１ｂｉ４，Ｘ）
（１）〜（３）の等式全てが成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定部を有し、
登録装置から前記公開鍵ｐｋを、電子署名装置から前記電子署名σ及び平文ｍｉを、受け取る、
ことを特徴とする検証装置。
【請求項６】
登録装置と、電子署名装置と、検証装置を用いる電子署名検証方法であって、
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）として、
前記電子署名装置が、前記登録装置から前記公開パラメータｖを受け取るステップと、
前記電子署名装置が、前記公開パラメータｖを記憶する公開パラメータ記憶ステップと、
前記電子署名装置が、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択ステップと、
前記電子署名装置が、Ｚｑに属する乱数ｒｉ（但し、１≦ｉ≦ｎであり、ｎは、平文の個数を表す）、ｘ及びｙを生成する乱数生成ステップと、
前記電子署名装置が、前記乱数ｒｉ、ｘ及びｙを記憶し、特にｘ、ｙは秘密鍵ｓｋとして秘密に記憶する秘密鍵記憶ステップと、
前記電子署名装置が、前記ｘ、ｙ、ｇ１及びｇ２を用いて、Ｘ＝ｇ２ｘ、Ｙ＝ｇ２ｙを計算し、公開鍵ｐｋを生成する公開鍵生成ステップと、
前記登録装置が、前記公開鍵ｐｋを登録及び公開するステップと、
前記電子署名装置が、前記ｇ１、ｇ２、ｒｉ、ｘ、ｙ及び平文ｍｉを用いて、ｂｉ１＝ｇ１ｒｉ、ｂ３＝Πｎｉ＝１ｇ１ｒｉｘｍｉｒｉｘｙ、ｂｉ４＝ｍｉｒｉｙ、ｂｉ５＝ｇ２ｒｉｙを計算し、電子署名σ＝（ｂｉ１，ｂ３，ｂｉ４，ｂｉ５）を生成する電子署名生成ステップと、
前記検証装置が、前記電子署名装置から前記電子署名σ及び平文ｍｉを、受け取るステップと、
前記検証装置が、前記登録装置から前記公開鍵ｐｋを受け取るステップと、
前記検証装置が、前記公開鍵ｐｋ、電子署名σ及び平文ｍｉを記憶する記憶ステップと、
前記検証装置が、
（１）ｅ（ｂｉ１，Ｙ）＝ｅ（ｇ１，ｂｉ５）
（２）ｅ（ｍｉ，ｂｉ５）＝ｅ（ｂｉ４，ｇ２）
（３）ｅ（ｂ３，ｇ２）＝ｅ（Πｎｉ＝１ｂｉ１ｂｉ４，Ｘ）
（１）〜（３）の等式全てが成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定ステップを有する、
ことを特徴とする電子署名検証方法。
【請求項７】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）として、
電子署名装置が、登録装置から前記公開パラメータｖを受け取るステップと、
前記電子署名装置が、前記公開パラメータｖを記憶する公開パラメータ記憶ステップと、
前記電子署名装置が、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択ステップと、
前記電子署名装置が、Ｚｑに属する乱数ｒｉ（但し、１≦ｉ≦ｎであり、ｎは、平文の個数を表す）、ｘ及びｙを生成する乱数生成ステップと、
前記電子署名装置が、前記乱数ｒ、ｘ及びｙを記憶し、特にｘ、ｙは秘密鍵ｓｋとして秘密に記憶する秘密鍵記憶ステップと、
前記電子署名装置が、前記ｘ、ｙ、ｇ１及びｇ２を用いて、Ｘ＝ｇ２ｘ、Ｙ＝ｇ２ｙを計算し、公開鍵ｐｋを生成する公開鍵生成ステップと、
前記電子署名装置が、前記ｇ１、ｇ２、ｒｉ、ｘ、ｙ及び平文ｍｉを用いて、ｂｉ１＝ｇ１ｒｉ、ｂ３＝Πｎｉ＝１ｇ１ｒｉｘｍｉｒｉｘｙ、ｂｉ４＝ｍｉｒｉｙ、ｂｉ５＝ｇ２ｒｉｙを計算し、電子署名σ＝（ｂｉ１，ｂ３，ｂｉ４，ｂｉ５）を生成する電子署名生成ステップと、
を有する電子署名方法。
【請求項８】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）として、
検証装置が、登録装置から公開鍵ｐｋを受け取るステップと、
前記検証装置が、電子署名装置から電子署名σ及び平文ｍｉ（但し、１≦ｉ≦ｎであり、ｎは、平文の個数を表す）を、受け取るステップと、
前記検証装置が、前記公開鍵ｐｋ、電子署名σ及び平文ｍｉを記憶する記憶ステップと、
前記検証装置が、
（１）ｅ（ｂｉ１，Ｙ）＝ｅ（ｇ１，ｂｉ５）
（２）ｅ（ｍｉ，ｂｉ５）＝ｅ（ｂｉ４，ｇ２）
（３）ｅ（ｂ３，ｇ２）＝ｅ（Πｎｉ＝１ｂｉ１ｂｉ４，Ｘ）
（１）〜（３）の等式全てが成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定ステップと、
を有する検証方法。
【請求項９】
請求項４記載の電子署名装置としてコンピュータを機能させるための電子署名プログラム。
【請求項１０】
請求項５記載の検証装置としてコンピュータを機能させるための検証プログラム。
【請求項１】
登録装置と、電子署名装置と、検証装置からなる電子署名検証システムにおいて、
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）とし、
前記電子署名装置は、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択部と、
Ｚｑに属する乱数ｒｉ（但し、１≦ｉ≦ｎであり、ｎは、平文の個数を表す）、ｘ及びｙを生成する乱数生成部と、
前記公開パラメータｖと前記乱数ｒｉ、ｘ及びｙが記憶され、特にｘ、ｙは秘密鍵ｓｋとして秘密に記憶される記憶部と、
前記ｘ、ｙ、ｇ１及びｇ２が入力され、Ｘ＝ｇ２ｘ、Ｙ＝ｇ２ｙを計算し、公開鍵ｐｋを生成する公開鍵生成部と、
前記ｇ１、ｇ２、ｒｉ、ｘ、ｙ及び平文ｍｉが入力され、ｂｉ１＝ｇ１ｒｉ、ｂ３＝Πｎｉ＝１ｇ１ｒｉｘｍｉｒｉｘｙ、ｂｉ４＝ｍｉｒｉｙ、ｂｉ５＝ｇ２ｒｉｙを計算し、電子署名σ＝（ｂｉ１，ｂ３，ｂｉ４，ｂｉ５）を生成する電子署名生成部と、を有し、
前記検証装置は、前記公開鍵ｐｋ、電子署名σ及び平文ｍｉが記憶される記憶部と、
（１）ｅ（ｂｉ１，Ｙ）＝ｅ（ｇ１，ｂｉ５）
（２）ｅ（ｍｉ，ｂｉ５）＝ｅ（ｂｉ４，ｇ２）
（３）ｅ（ｂ３，ｇ２）＝ｅ（Πｎｉ＝１ｂｉ１ｂｉ４，Ｘ）
（１）〜（３）の等式全てが成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定部を有し、
前記登録装置は、前記公開パラメータｖ及び公開鍵ｐｋを記憶する記憶部を有し、
前記電子署名装置は、前記登録装置から前記公開パラメータｖを受け取り、前記公開鍵ｐｋを前記登録装置へ、電子署名σ及び平文ｍｉを検証装置へ、送り、
前記検証装置は、前記登録装置から前記公開鍵ｐｋを、前記電子署名装置から前記電子署名σ及び平文ｍｉを、受け取る、
ことを特徴とする電子署名検証システム。
【請求項２】
登録装置と、電子署名装置と、検証装置からなる電子署名検証システムにおいて、
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）とし、
前記電子署名装置は、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択部と、
Ｚｑに属する乱数ｒ、ｘ及びｙｉ（但し、１≦ｉ≦ｎであり、ｎは、平文の個数を表す）を生成する乱数生成部と、
前記公開パラメータｖと前記乱数ｒ、ｘ及びｙｉが記憶され、特にｘ、ｙｉは秘密鍵ｓｋ＝（ｘ，ｙｉ）として秘密に記憶される記憶部と、
前記ｘ、ｙｉ、ｇ１及びｇ２が入力され、Ｘ＝ｇ２ｘ、Ｙｉ＝ｇ２ｙｉを計算し、公開鍵ｐｋを生成する公開鍵生成部と、
前記ｇ１、ｇ２、ｒ、ｘ、ｙｉ及び平文ｍｉが入力され、ｂ１＝ｇ１ｒ、ｂ３＝ｇ１ｒｘΠｎｉ＝１ｍｉｒｘｙｉ、ｂｉ４＝ｍｉｒｙｉ、ｂｉ５＝ｇ２ｒｙｉを計算し、電子署名σ＝（ｂ１，ｂ３，ｂｉ４，ｂｉ５）を生成する電子署名生成部と、を有し、
前記検証装置は、前記公開鍵ｐｋ、電子署名σ及び平文ｍｉが記憶される記憶部と、
（１）ｅ（ｂ１，Ｙｉ）＝ｅ（ｇ１，ｂｉ５）
（２）ｅ（ｍｉ，ｂｉ５）＝ｅ（ｂｉ４，ｇ２）
（３）ｅ（ｂ３，ｇ２）＝ｅ（ｂ１Πｎｉ＝１ｂｉ４，Ｘ）
（１）〜（３）の等式全てが成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定部を有し、
前記登録装置は、前記公開パラメータｖ及び公開鍵ｐｋを記憶する記憶部を有し、
前記電子署名装置は、前記登録装置から前記公開パラメータｖを受け取り、前記公開鍵ｐｋを前記登録装置へ、電子署名σ及び平文ｍｉを検証装置へ、送り、
前記検証装置は、前記登録装置から前記公開鍵ｐｋを、前記電子署名装置から前記電子署名σ及び平文ｍｉを、受け取る、
ことを特徴とする電子署名検証システム。
【請求項３】
請求項１または２記載の電子署名検証システムであって、
ｎ＝１である、
ことを特徴とする電子署名検証システム。
【請求項４】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）とし、
Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択部と、
Ｚｑに属する乱数ｒｉ（但し、１≦ｉ≦ｎであり、ｎは、平文の個数を表す）、ｘ及びｙを生成する乱数生成部と、
前記公開パラメータｖと前記乱数ｒｉ、ｘ及びｙが記憶され、特にｘ、ｙは秘密鍵ｓｋとして秘密に記憶される記憶部と、
前記ｘ、ｙ、ｇ１及びｇ２が入力され、Ｘ＝ｇ２ｘ、Ｙ＝ｇ２ｙを計算し、公開鍵ｐｋを生成する公開鍵生成部と、
前記ｇ１、ｇ２、ｒｉ、ｘ、ｙ及び平文ｍｉが入力され、ｂｉ１＝ｇ１ｒｉ、ｂ３＝Πｎｉ＝１ｇ１ｒｉｘｍｉｒｉｘｙ、ｂｉ４＝ｍｉｒｉｙ、ｂｉ５＝ｇ２ｒｉｙを計算し、電子署名σ＝（ｂｉ１，ｂ３，ｂｉ４，ｂｉ５）を生成する電子署名生成部と、を有し、
登録装置から前記公開パラメータｖを受け取り、前記公開鍵ｐｋを前記登録装置へ、電子署名σ及び平文ｍｉを検証装置へ、送る、
ことを特徴とする電子署名装置。
【請求項５】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、
公開鍵ｐｋ、電子署名σ及び平文ｍｉ（但し、１≦ｉ≦ｎであり、ｎは、平文の個数を表す）が記憶される記憶部と、
（１）ｅ（ｂｉ１，Ｙ）＝ｅ（ｇ１，ｂｉ５）
（２）ｅ（ｍｉ，ｂｉ５）＝ｅ（ｂｉ４，ｇ２）
（３）ｅ（ｂ３，ｇ２）＝ｅ（Πｎｉ＝１ｂｉ１ｂｉ４，Ｘ）
（１）〜（３）の等式全てが成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定部を有し、
登録装置から前記公開鍵ｐｋを、電子署名装置から前記電子署名σ及び平文ｍｉを、受け取る、
ことを特徴とする検証装置。
【請求項６】
登録装置と、電子署名装置と、検証装置を用いる電子署名検証方法であって、
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）として、
前記電子署名装置が、前記登録装置から前記公開パラメータｖを受け取るステップと、
前記電子署名装置が、前記公開パラメータｖを記憶する公開パラメータ記憶ステップと、
前記電子署名装置が、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択ステップと、
前記電子署名装置が、Ｚｑに属する乱数ｒｉ（但し、１≦ｉ≦ｎであり、ｎは、平文の個数を表す）、ｘ及びｙを生成する乱数生成ステップと、
前記電子署名装置が、前記乱数ｒｉ、ｘ及びｙを記憶し、特にｘ、ｙは秘密鍵ｓｋとして秘密に記憶する秘密鍵記憶ステップと、
前記電子署名装置が、前記ｘ、ｙ、ｇ１及びｇ２を用いて、Ｘ＝ｇ２ｘ、Ｙ＝ｇ２ｙを計算し、公開鍵ｐｋを生成する公開鍵生成ステップと、
前記登録装置が、前記公開鍵ｐｋを登録及び公開するステップと、
前記電子署名装置が、前記ｇ１、ｇ２、ｒｉ、ｘ、ｙ及び平文ｍｉを用いて、ｂｉ１＝ｇ１ｒｉ、ｂ３＝Πｎｉ＝１ｇ１ｒｉｘｍｉｒｉｘｙ、ｂｉ４＝ｍｉｒｉｙ、ｂｉ５＝ｇ２ｒｉｙを計算し、電子署名σ＝（ｂｉ１，ｂ３，ｂｉ４，ｂｉ５）を生成する電子署名生成ステップと、
前記検証装置が、前記電子署名装置から前記電子署名σ及び平文ｍｉを、受け取るステップと、
前記検証装置が、前記登録装置から前記公開鍵ｐｋを受け取るステップと、
前記検証装置が、前記公開鍵ｐｋ、電子署名σ及び平文ｍｉを記憶する記憶ステップと、
前記検証装置が、
（１）ｅ（ｂｉ１，Ｙ）＝ｅ（ｇ１，ｂｉ５）
（２）ｅ（ｍｉ，ｂｉ５）＝ｅ（ｂｉ４，ｇ２）
（３）ｅ（ｂ３，ｇ２）＝ｅ（Πｎｉ＝１ｂｉ１ｂｉ４，Ｘ）
（１）〜（３）の等式全てが成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定ステップを有する、
ことを特徴とする電子署名検証方法。
【請求項７】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）として、
電子署名装置が、登録装置から前記公開パラメータｖを受け取るステップと、
前記電子署名装置が、前記公開パラメータｖを記憶する公開パラメータ記憶ステップと、
前記電子署名装置が、Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択する生成元選択ステップと、
前記電子署名装置が、Ｚｑに属する乱数ｒｉ（但し、１≦ｉ≦ｎであり、ｎは、平文の個数を表す）、ｘ及びｙを生成する乱数生成ステップと、
前記電子署名装置が、前記乱数ｒ、ｘ及びｙを記憶し、特にｘ、ｙは秘密鍵ｓｋとして秘密に記憶する秘密鍵記憶ステップと、
前記電子署名装置が、前記ｘ、ｙ、ｇ１及びｇ２を用いて、Ｘ＝ｇ２ｘ、Ｙ＝ｇ２ｙを計算し、公開鍵ｐｋを生成する公開鍵生成ステップと、
前記電子署名装置が、前記ｇ１、ｇ２、ｒｉ、ｘ、ｙ及び平文ｍｉを用いて、ｂｉ１＝ｇ１ｒｉ、ｂ３＝Πｎｉ＝１ｇ１ｒｉｘｍｉｒｉｘｙ、ｂｉ４＝ｍｉｒｉｙ、ｂｉ５＝ｇ２ｒｉｙを計算し、電子署名σ＝（ｂｉ１，ｂ３，ｂｉ４，ｂｉ５）を生成する電子署名生成ステップと、
を有する電子署名方法。
【請求項８】
ｑを素数とし、Ｇ１、Ｇ２、ＧＴを位数ｑの群とし、ｅをバイリニアマップｅ：Ｇ１×Ｇ２→ＧTとし、公開パラメータをｖ＝（ｑ，Ｇ１，Ｇ２，ＧT，ｅ）として、
検証装置が、登録装置から公開鍵ｐｋを受け取るステップと、
前記検証装置が、電子署名装置から電子署名σ及び平文ｍｉ（但し、１≦ｉ≦ｎであり、ｎは、平文の個数を表す）を、受け取るステップと、
前記検証装置が、前記公開鍵ｐｋ、電子署名σ及び平文ｍｉを記憶する記憶ステップと、
前記検証装置が、
（１）ｅ（ｂｉ１，Ｙ）＝ｅ（ｇ１，ｂｉ５）
（２）ｅ（ｍｉ，ｂｉ５）＝ｅ（ｂｉ４，ｇ２）
（３）ｅ（ｂ３，ｇ２）＝ｅ（Πｎｉ＝１ｂｉ１ｂｉ４，Ｘ）
（１）〜（３）の等式全てが成立するか否かを判定し、成立する場合には受理し、成立しない場合には拒否する判定ステップと、
を有する検証方法。
【請求項９】
請求項４記載の電子署名装置としてコンピュータを機能させるための電子署名プログラム。
【請求項１０】
請求項５記載の検証装置としてコンピュータを機能させるための検証プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２０１０−１３４０４８（Ｐ２０１０−１３４０４８Ａ）
【公開日】平成２２年６月１７日（２０１０．６．１７）
【国際特許分類】
【出願番号】特願２００８−３０７８９４（Ｐ２００８−３０７８９４）
【出願日】平成２０年１２月２日（２００８．１２．２）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２２年６月１７日（２０１０．６．１７）
【国際特許分類】
【出願日】平成２０年１２月２日（２００８．１２．２）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]