(57)【特許請求の範囲】
【請求項１】
複数の署名データのバッチインスタンスを一括して検証する一括検証装置であって、
前記複数の署名データには、順番が特定されており、
前記バッチインスタンスは、第一の値と、第二の値と、を備え、
前記第一の値に対して前記順番に応じて異なる数を乗算した乗算値をべき指数として、有限乗法巡回群の生成元をべき乗した値を全てのバッチインスタンスにおいて算出し、算出した値を全て乗算した値と、
前記順番に応じて異なる数をべき指数として、前記第二の値をべき乗した値を全てのバッチインスタンスにおいて算出し、算出した値を全て乗算した値と、
が一致するか否かにより検証する処理部を備え、
前記処理部は、
特定された前記バッチインスタンスの順番を少なくとも一組以上入れ替えてから検証を行うこと、
を特徴とする一括検証装置。
【請求項２】
請求項１に記載の一括検証装置であって、
前記処理部は、
特定された前記バッチインスタンスの順番を入れ替える複数の入替方法を備えており、
前記複数の入替方法から選択された位置の入替方法を用いて、特定された前記バッチインスタンスの順番を予め入れ替えること、
を特徴とする一括検証装置。
【請求項３】
請求項２に記載の一括検証装置であって、
前記バッチインスタンスを（x1 , y1）,・・・,（xn , yn）、前記有限乗法巡回群の位数をq、生成元をg、集合｛1,・・・, n｝上の前記置換をεとし、予め定められた自然数をαとすると、
前記処理部は、
【数１】
0004988448.tif 000035
が成り立つか否かにより検証すること、
を特徴とする一括検証装置。
【請求項４】
コンピュータに、複数の署名データのバッチインスタンスを一括して検証する処理を行わせるプログラムであって、
前記複数の署名データには、順番が特定されており、
前記バッチインスタンスは、第一の値と、第二の値と、を備え、
前記コンピュータを、
前記第一の値に対して前記順番に応じて異なる数を乗算した乗算値をべき指数として、有限乗法巡回群の生成元をべき乗した値を全てのバッチインスタンスにおいて算出し、算出した値を全て乗算した値と、
前記順番に応じて異なる数をべき指数として、前記第二の値をべき乗した値を全てのバッチインスタンスにおいて算出し、算出した値を全て乗算した値と、
が一致するか否かにより検証する処理手段として機能させ、
前記処理手段は、
特定された前記バッチインスタンスの順番を少なくとも一組以上入れ替えてから検証を行うこと、
を特徴とするプログラム。
【請求項５】
請求項４に記載のプログラムであって、
前記処理手段は、
特定された前記バッチインスタンスの順番を入れ替える複数の入替方法を備えており、
前記複数の入替方法から選択された位置の入替方法を用いて、特定された前記バッチインスタンスの順番を予め入れ替えること、
を特徴とするプログラム。
【請求項６】
請求項５に記載のプログラムであって、
前記バッチインスタンスを（x1 , y1）,・・・,（xn , yn）、前記有限乗法巡回群の位数をq、生成元をg、集合｛1,・・・, n｝上の前記置換をεとし、予め定められた自然数をαとすると、
前記処理手段は、
【数２】
0004988448.tif 000036
が成り立つか否かにより検証すること、
を特徴とするプログラム。
【請求項７】
複数の署名データのバッチインスタンスを一括して検証する処理部を備える一括検証装置が行う一括検証方法であって、
前記複数の署名データには、順番が特定されており、
前記バッチインスタンスは、第一の値と、第二の値と、を備え、
前記処理部が、
前記第一の値に対して前記順番に応じて異なる数を乗算した乗算値をべき指数として、有限乗法巡回群の生成元をべき乗した値を全てのバッチインスタンスにおいて算出し、算出した値を全て乗算した値と、
前記順番に応じて異なる数をべき指数として、前記第二の値をべき乗した値を全てのバッチインスタンスにおいて算出し、算出した値を全て乗算した値と、
が一致するか否かにより検証する過程を備え、
前記処理部は、
特定された前記バッチインスタンスの順番を少なくとも一組以上入れ替えてから検証を行うこと、
を特徴とする一括検証方法。
【請求項８】
請求項７に記載の一括検証方法であって、
前記処理部は、
特定された前記バッチインスタンスの順番を入れ替える複数の入替方法を備えており、
前記複数の入替方法から選択された位置の入替方法を用いて、特定された前記バッチインスタンスの順番を予め入れ替えること、
を特徴とする一括検証方法。
【請求項９】
請求項８に記載の一括検証方法であって、
前記バッチインスタンスを（x1 , y1）,・・・,（xn , yn）、前記有限乗法巡回群の位数をq、生成元をg、集合｛1,・・・, n｝上の前記置換をεとし、予め定められた自然数をαとすると、
前記処理部は、
【数３】
0004988448.tif 000037
が成り立つか否かにより検証すること、
を特徴とする一括検証方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のデジタル署名を一括して検証する技術に関する。
【背景技術】
【０００２】
デジタル署名では、署名者は、署名対象の電子データに対し、署名者が秘密にしている署名生成鍵を用いて署名データを生成し、署名検証者は、公開されている署名検証鍵を用いて署名データを復号して、署名対象となっている電子データと比較することにより、署名者の真偽や電子データに対する改ざんの有無等を検出することができるようにしている。
【０００３】
このようなデジタル署名では、検証を行う際に複雑な処理（数学的な計算）を繰り返し行わなければならないが、例えば、非特許文献１に記載の技術では、複数のデジタル署名を一括して検証することで、デジタル署名の検証処理の効率性を向上させている。
【０００４】
以下、非特許文献１に記載の一括検証方法を説明する。
【０００５】
なお、以下では、Ｇを、位数をｑ（ｑは大きな素数）とする有限巡回群とし、ｇを群Ｇの生成元とする。さらに(ｘｉ，ｙｉ)(ｉは順番を示すインデックスであって、１≦ｉ≦ｎを満たす自然数)は、下記の（１）式を満たすか否かを検証するための組（バッチインスタンス）とする。
【０００６】
【数１】
0004988448.tif 000002
【０００７】
但し、各ｉ(ｉ=１，・・・，ｎ)に対してｘｉ，ｙｉはそれぞれ下記の（２）式及び（３）式を満たす。
【０００８】
【数２】
0004988448.tif 000003
【０００９】
【数３】
0004988448.tif 000004
【００１０】
バッチインスタンス(ｘｉ，ｙｉ)(ｉ=１，・・・，ｎ)は、各ｉ(ｉ=１，・・・，ｎ)に対して（１）式を満たすときに「有効」であるといい、そうでないとき「無効」であるという。なお、バッチインスタンスが有効である場合に、署名データも「有効」と判断され、バッチインスタンスが無効である場合に、署名データも無効と判断される。
【００１１】
なお、一括検証では、有効なバッチインスタンスを常に「有効」として受け入れるが、無効なバッチインスタンスも非常に小さな確率で「有効」として受け入れてしまう場合がある。そして、無効なバッチインスタンスを「有効」として受け入れる確率の上限が高々１／２ｍ(ｍは正の整数)であるとき、ｍはセキュリティレベルと呼ばれる。近年の計算機の能力からｍは８０程度に設定することが望ましいことが知られている。なお、セキュリティレベルｍが大きいほど、デジタル署名の安全性が高いことが知られている。
【００１２】
ここで、通常の署名検証では、各ｉ(ｉ=１，・・・，ｎ)に対応するデジタル署名に対して（１）式を満たすかどうかを各々別個に検証するのに対して、非特許文献１に記載のRandom Subset Testでは、下記の（４）式及び（５）を満たすか否かを検証する。
【００１３】
【数４】
0004988448.tif 000005
【００１４】
【数５】
0004988448.tif 000006
【００１５】
ここで、（５）式に示すように、各ｉ(ｉ=１，・・・，ｎ)に対して、ｓｉは、０又は１がランダムに選ばれたものとする。
【００１６】
また、非特許文献１に記載のSmall Exponents Testは、下記の（６）式及び（７）式を満たすかどうかを検証する。
【００１７】
【数６】
0004988448.tif 000007
【００１８】
【数７】
0004988448.tif 000008
【００１９】
ここで、ｓｉ(ｉ=１，・・・，ｎ)は、［０，・・・，２ｍ−１］からランダムに選ばれた整数である。ここで、ｍは任意の正の整数であり、このｍによってセキュリティレベルが定まる。
【００２０】
なお、Random Subset TestのRandomは、（５）式に記載されているように、各ｉ(ｉ＝１，２，３，・・・，ｎ)に対してｓｉをランダムに選択することに由来している。そして、Random Subset Testは「無効」なバッチインスタンスを高々１／２の確率で「有効」として受け入れてしまう。そこで実際には、セキュリティレベルをｍに設定するために、Random Subset Testをｍ回独立に実行するAtomic Random Subset Testを用いる。これにより、Random Subset Testをｍ回独立に実行するAtomic Random Subset Testは「無効」なバッチインスタンスを「有効」として受け入れてしまう確率は高々１／２ｍである。また、上述のSmall Exponents Testにおいても、「無効」なバッチインスタンスを「有効」として受け入れてしまう確率は高々１／２ｍである。
【００２１】
この点、非特許文献１に記載の一括検証の効率性は、バッチインスタンスの個数ｎとセキュリティレベルｍに依存する。
【００２２】
【非特許文献１】M. Bellare，J. Garay，and T. Rabin， "Fast Batch Verification for Modular Exponentiation and Digital Signatures"， Advances in Cryptology - EUROCRYPT 1998，LNCS 1403， pp. 236 - 250， 1998.
【発明の開示】
【発明が解決しようとする課題】
【００２３】
非特許文献１に記載の一括検証の効率性は、バッチインスタンスの個数ｎとセキュリティレベルｍに依存し、効率性と安全性（セキュリティレベルｍ）との間にはトレードオフの関係があり、高い安全性を求めると、高い効率性は望めないようになっている。
【００２４】
そこで、本発明は、高い安全性と高い効率性を兼ね備えた一括検証を実現することを目的とする。
【課題を解決するための手段】
【００２５】
以上の課題を解決するため、本発明は、複数の署名データに順番を特定し、特定した順番に応じた数を作用させる。
【００２６】
例えば、本発明は、複数の署名データのバッチインスタンスを一括して検証する一括検証装置であって、前記複数の署名データには、順番が特定されており、前記バッチインスタンスは、第一の値と、第二の値と、を備え、前記第一の値に対して前記順番に応じて異なる数を乗算した乗算値をべき指数として、有限乗法巡回群の生成元をべき乗した値を全てのバッチインスタンスにおいて算出し、算出した値を全て乗算した値と、前記順番に応じて異なる数をべき指数として、前記第二の値をべき乗した値を全てのバッチインスタンスにおいて算出し、算出した値を全て乗算した値と、が一致するか否かにより検証する処理部を備え、前記処理部は、特定された前記バッチインスタンスの順番を少なくとも一組以上入れ替えてから検証を行うこと、を特徴とする。
【発明の効果】
【００２７】
以上のように、本発明によれば、高い安全性と高い効率性を兼ね備えた一括検証を実現することができる。
【発明を実施するための最良の形態】
【００２８】
図１は、本発明の第一の実施形態である署名一括検証システム１００の概略図である。
【００２９】
図示するように、署名一括検証システム１００は、署名装置１１０と、検証装置１３０と、を備え、これらの署名装置１１０及び検証装置１３０は、ネットワーク１５０を介して相互に情報の送受信を行うことができるようにされている。そして、本実施形態である署名一括検証システム１００では、署名装置１１０でメッセージＭに対する署名の生成を行い、検証装置１３０で署名の一括検証を行う。
【００３０】
図２は、署名装置１１０の概略図である。
【００３１】
図示するように、署名装置１１０は、記憶部１１１と、処理部１１４と、入力部１１７と、出力部１１８と、通信部１１９と、を備える。
【００３２】
記憶部１１１には、署名生成鍵記憶領域１１２と、データ記憶領域１１３と、が設けられている。
【００３３】
署名生成鍵記憶領域１１２には、署名を行う際の鍵情報である署名生成鍵が記憶される。
【００３４】
データ記憶領域１１３には、署名を行う対象となるデータであるメッセージが記憶される。
【００３５】
処理部１１４は、署名生成処理部１１５と、数学関数計算部１１６と、を備える。
【００３６】
署名生成処理部１１５は、署名を行う対象となるデータであるメッセージに対する署名データを生成する処理を制御する。
【００３７】
例えば、本実施形態では、署名生成処理部１１５は、署名を行う対象となるデータであるメッセージを、予め定められたハッシュ関数に入力することで、入力データを生成する。
【００３８】
そして、署名生成処理部１１５は、署名生成鍵記憶領域１１２に記憶されている署名生成鍵を取得して、入力データとともに、数学関数計算部１１６に入力する。
【００３９】
そして、署名生成処理部１１５は、数学関数計算部１１６より生成された署名を取得して、署名とメッセージとを署名データとして、通信部１３９を介して検証装置１３０に送信する。
【００４０】
数学関数計算部１１６は、署名生成処理部１１５から入力された入力データに対して、署名生成処理部１１５から入力された署名生成鍵を用いて、予め定められたアルゴリズムによる暗号化を施して署名を生成する。
【００４１】
そして、数学関数計算部１１６は、このようにして生成した署名を署名生成処理部１１５に出力する。
【００４２】
入力部１１７は、情報の入力を受け付ける。
【００４３】
出力部１１８は、情報を出力する。
【００４４】
通信部１１９は、ネットワーク１５０を介して、情報の送受信を行う。
【００４５】
以上に記載した署名装置１１０は、例えば、図５（コンピュータ１６０の概略図）に示すような、ＣＰＵ１６１と、メモリ１６２と、ＨＤＤ等の外部記憶装置１６３と、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ等の可搬性を有する記憶媒体１６４から情報を読み出す読取装置１６５と、キーボードやマウスなどの入力装置１６６と、ディスプレイなどの出力装置１６７と、通信ネットワークに接続するためのＮＩＣ（Network Interface Card）等の通信装置１６８と、を備えた一般的なコンピュータ１６０で実現できる。
【００４６】
例えば、記憶部１１１は、ＣＰＵ１６１がメモリ１６２又は外部記憶装置１６３を利用することにより実現可能であり、処理部１１４は、外部記憶装置１６３に記憶されている所定のプログラムをメモリ１６２にロードしてＣＰＵ１６１で実行することで実現可能であり、入力部１１７は、ＣＰＵ１６１が入力装置１６６を利用することで実現可能であり、出力部１１８は、ＣＰＵ１６１が出力装置１６７を利用することで実現可能であり、通信部１１９は、ＣＰＵ１６１が通信装置１６８を利用することで実現可能である。
【００４７】
この所定のプログラムは、読取装置１６５を介して記憶媒体１６４から、あるいは、通信装置１６８を介してネットワークから、外部記憶装置１６３にダウンロードされ、それから、メモリ１６２上にロードされてＣＰＵ１６１により実行されるようにしてもよい。また、読取装置１６５を介して記憶媒体１６４から、あるいは、通信装置１６８を介してネットワークから、メモリ１６２上に直接ロードされ、ＣＰＵ１６１により実行されるようにしてもよい。
【００４８】
図３は、検証装置１３０の概略図である。
【００４９】
検証装置１３０は、記憶部１３１と、処理部１３４と、入力部１３７と、出力部１３８と、通信部１３９と、を備える。
【００５０】
記憶部１３１には、署名検証鍵記憶領域１３２と、署名データ記憶領域１３３と、が設けられている。
【００５１】
署名検証鍵記憶領域１３２には、署名装置１１０から送信されてきた署名データに含まれている署名を復号化して検証するための鍵情報である署名検証鍵が記憶される。
【００５２】
署名データ記憶領域１３３には、署名装置１１０から送信されてきた署名データを記憶する。
【００５３】
処理部１３４は、署名一括検証処理部１３５と、数学関数計算部１３６と、を備える。
【００５４】
署名一括検証処理部１３５は、署名装置１１０から送信されてきた署名データを一括して検証する処理を制御する。
【００５５】
例えば、本実施形態においては、署名一括検証処理部１３５は、署名検証鍵記憶領域１３２に記憶されている署名検証鍵ｐｋ及び署名データ記憶領域１３３に記憶されている署名データを記憶部１３１から取得し、数学関数計算部１３６に入力する。
【００５６】
そして、署名一括検証処理部１３５は、数学関数計算部１３６から一括検証の結果を取得して、記憶部１３１に記憶するか、または、出力部１３８や通信部１３９を介して、検証結果を出力する。
【００５７】
数学関数計算部１３６は、署名一括検証部１３５から入力された署名データに含まれている署名に対して、署名一括検証部１３５から入力された署名検証鍵を用いて、予め定められたアルゴリズムによる署名の一括検証を施して、署名の有効性を確認する。
【００５８】
例えば、本実施形態においては、数学関数計算部１３６は、図４（数学関数計算部１３６の概略図）に示されているように、バッチインスタンス生成部１３６ａと、置換部１３６ｂと、べき乗剰余計算部１３６ｆと、を備える。
【００５９】
バッチインスタンス生成部１３６ａは、署名一括検証部１３５から入力された署名データに含まれている署名から、バッチインスタンスを生成する。ここで、バッチインスタンスの生成方法は、署名装置１１０及び検証装置１３０で使用する署名方式に依存する。なお、署名装置１１０及び検証装置１３０で使用する署名方式により生成された署名がバッチインスタンスとなっている場合には、数学関数計算部１３６にバッチインスタンス生成部１３６ａを設ける必要はない。なお、バッチインスタンスの具体的な生成方法については、後述する実施形態２及び３で説明する。
【００６０】
置換部１３６ｂは、バッチインスタンスの順番を入れ替える処理を行う。
【００６１】
バッチインスタンスの順番の入れ替えは、任意の入れ替え方法を採用可能であるが、本実施形態においては、疑似乱数生成部１３６ｃと、中間状態格納部１３６ｄと、入れ替え部１３６ｅと、繰り返し判定部１３６ｆと、を用いて入れ替えを行う。なお、具体的な入れ替え方法については、図９を用いて詳細に説明する。
【００６２】
べき乗剰余計算部１３６ｆは、置換部１３６ｂで入れ替えられたバッチインスタンスをべき乗剰余演算することで、検証を行う。なお、べき乗剰余計算部１３６ｆでの処理については、図８を用いて詳細に説明する。
【００６３】
入力部１３７は、情報の入力を受け付ける。
【００６４】
出力部１３８は、情報を出力する。
【００６５】
通信部１３９は、ネットワーク１５０を介して、情報の送受信を行う。
【００６６】
以上に記載した検証装置１３０についても、例えば、図５（コンピュータ１６０の概略図）に示すような、一般的なコンピュータ１６０で実現できる。
【００６７】
例えば、記憶部１３１は、ＣＰＵ１６１がメモリ１６２又は外部記憶装置１６３を利用することにより実現可能であり、処理部１３４は、外部記憶装置１６３に記憶されている所定のプログラムをメモリ１６２にロードしてＣＰＵ１６１で実行することで実現可能であり、入力部１３７は、ＣＰＵ１６１が入力装置１６６を利用することで実現可能であり、出力部１３８は、ＣＰＵ１６１が出力装置１６７を利用することで実現可能であり、通信部１３９は、ＣＰＵ１６１が通信装置１６８を利用することで実現可能である。
【００６８】
この所定のプログラムは、読取装置１６５を介して記憶媒体１６４から、あるいは、通信装置１６８を介してネットワークから、外部記憶装置１６３にダウンロードされ、それから、メモリ１６２上にロードされてＣＰＵ１６１により実行されるようにしてもよい。また、読取装置１６５を介して記憶媒体１６４から、あるいは、通信装置１６８を介してネットワークから、メモリ１６２上に直接ロードされ、ＣＰＵ１６１により実行されるようにしてもよい。
【００６９】
図６は、署名装置１１０における署名生成処理を示すシーケンス図である。
【００７０】
まず、署名装置１１０の署名生成処理部１１５は、入力部１１７を介して入力された又はデータ記憶領域１１３に記憶されているメッセージＭを取得する（Ｓ１０）。ここで、メッセージＭは、デジタル化されたデータであればよく、テキスト、画像、映像、音等の種類は問わない。
【００７１】
次に、署名生成処理部１１５は、取得したメッセージＭから入力データＨを生成する（Ｓ１１）。入力データＨは、例えば、メッセージＭのハッシュ値等で、メッセージＭや使用する署名方式に依存するものである。
【００７２】
次に、署名生成処理部１１５は、記憶部１１１の署名生成鍵記憶領域１１２に記憶されている署名生成鍵ｓｋを読み出す（Ｓ１２）。
【００７３】
そして、署名生成処理部１１５は、読み出した署名生成鍵ｓｋ及びステップＳ１１で生成した入力データＨを数学関数計算部１１６に入力する（Ｓ１３）。
【００７４】
数学関数計算部１１６は、入力された署名生成鍵ｓｋと入力データＨとから、署名Ｓを計算する（Ｓ１４）。ここで、署名Ｓは、採用する署名方式に依存して計算される値である。
【００７５】
そして、数学関数計算部１１６は、計算した署名Ｓを署名生成処理部１１５に出力する（Ｓ１５）。
【００７６】
署名生成処理部１１５は、受け取った署名Ｓと、メッセージＭと、を署名データとして、通信部１１９を介して検証装置１３０に送信する（Ｓ１６）。
【００７７】
なお、ステップＳ１２において記憶部１１１からの署名生成鍵ｓｋの取得タイミングについては、数学関数計算部１１６へ署名生成鍵ｓｋを出力する前であればよく、例えば、メッセージＭを取得する（Ｓ１０）前であってもよい。
【００７８】
図７は、検証装置１３０における署名の一括検証処理を示すシーケンス図である。
【００７９】
まず、検証装置１３０の署名一括検証処理部１３５は、入力部１３７、通信部１３９を介して入力された、又は、記憶部１３１の署名データ記憶領域１３３に記憶されている署名データを任意の個数取得する（Ｓ２０）。
【００８０】
また、署名一括検証処理部１３５は、記憶部１３１の署名検証鍵記憶領域１３２に記憶されている署名検証鍵ｐｋを読み出す（Ｓ２１）。
【００８１】
そして、署名一括検証処理部１３５は、取得した複数の署名データ及び読み出した署名検証鍵ｐｋを数学関数計算部１３６に入力する（Ｓ２２）。
【００８２】
数学関数計算部１３６では、入力された複数の署名データに含まれる署名Ｓからバッチインスタンスを生成する（Ｓ２３）。なお、署名Ｓが既にバッチインスタンスとなっている場合には、バッチインスタンスを生成する必要はない。
【００８３】
そして、数学関数計算部１３６は、入力された署名検証鍵ｐｋとバッチインスタンスとから、予め定められた一括検証を行い（Ｓ２４）、その結果を検証結果として署名一括検証処理部１３５に出力する（Ｓ２５）。なお、数学関数計算部１３６での署名の一括検証処理については、後述の図８を用いた説明で詳述する。
【００８４】
このような検証結果を取得した署名一括検証処理部１３５は、記憶部１３１に記憶するか、または、出力部１３８や通信部１３９を介して、検証結果（署名データが有効か否か）を出力する（Ｓ２６）。
【００８５】
なお、記憶部１３１からの署名検証鍵ｐｋの読み出し（Ｓ２１）については、数学関数計算部１３６で一括検証を行う前であればよく、例えば、ステップＳ２０において署名データを受け取る前であってもよい。
【００８６】
図８は、数学関数計算部１３６での一括検証処理を示すフローチャートである。
【００８７】
ここで、本実施形態では、署名の一括検証において、Ｇを、位数をｑ（ｑは大きな素数）とする有限巡回群、ｇを群Ｇの生成元とし、署名検証鍵ｐｋを(Ｇ、ｇ、ｑ)とする。以下、複数の署名Ｓｉ（ｉ＝１，・・・，ｎ）(ｎは任意の正の整数)の一括検証方法を具体的に説明する。
【００８８】
数学関数計算部１３６での一括検証処理は、任意の個数の署名データの入力を署名一括検証処理部１３５より受けることで開始される（Ｓ３０）。
【００８９】
任意の個数の署名データの入力を署名一括検証処理部１３５より受けると、数学関数計算部１３６のバッチインスタンス生成部１３６ａは、入力された署名データに含まれる複数の署名Ｓｉ（ｉ＝１，・・・，ｎ）からバッチインスタンス(ｘｉ，ｙｉ)（ｉ＝１，・・・，ｎ）を生成する（Ｓ３１）。ここで、バッチインスタンスの変換方法は、使用する署名方式に依存する。なお、具体的なバッチインスタンスへの変換方法は後述する第二及び第三の実施形態で説明する。また、第二及び第三の実施形態で説明するように、バッチインスタンスへの変換が不要な署名方式として、例えば、非特許文献１に記載のＲＳＡ−ＦＤＨ署名、ＤＳＡ＊署名、ＥＣＤＳＡ＊署名があり、バッチインスタンスへの変換が必要な署名方式として、例えば非特許文献１に記載のＤＳＡ署名、ＥＣＤＳＡ署名等が知られている。
【００９０】
なお、ＥＣＤＳＡ＊署名及びＥＣＤＳＡ署名については、A. Antipa, D. Brown, R. Gallant, R. Lambert, R. Struik, and S. Vanstone, "Accelerated Verification of ECDSA Signatures", Selected Areas in Cryptography - SAC 2005, LNCS 3897, pp.307-318, 2006.（以下、非特許文献２という）に記載されている。
【００９１】
そして、数学関数計算部１３６の置換部１３６ｂは、置換群ＳＩＦＴｎから置換εをランダムに選び、即ち、任意の置き換え方法により、バッチインスタンス(ｘｉ，ｙｉ)（ｉ＝１，・・・，ｎ）の順番を(ｘε(ｉ)，ｙε(ｉ))（ｉ＝１，・・・，ｎ）に入れ替える（Ｓ３２）。ここで、置換群ＳＩＦＴｎは、集合｛１，２，・・・，ｎ｝から集合｛１，２，・・・，ｎ｝への置換全体の集合であり、当該置換は全単射であることが望ましい。なお、置換の具体例については、後述の図９を用いて詳述する。
【００９２】
次に、数学関数計算部１３６のべき乗剰余計算部１３６ｆは、入れ替えられた(ｘε(ｉ)，ｙε(ｉ))（ｉ＝１，・・・，ｎ）を用いて、下記の（８）式及び（９）式を計算する（Ｓ３３）。
【００９３】
【数８】
0004988448.tif 000009
【００９４】
【数４】
0004988448.tif 000010
【００９５】
ここで、（８）式及び（９）式におけるαは、任意の自然数であり、少なくとも一回の検証においては（８）式及び（９）式において同じ数になるように予め定めておく。なお、（８）式及び（９）式におけるαｉについては、このような形態に限定されず、順番ｉにより異なる数、例えば、ｉを変数とする任意の関数ｆ（ｉ）であってもよい。
【００９６】
そして、べき乗剰余計算部１３６ｆは、（８）式で計算されたｚと、（９）式で計算されたｗと、の間で下記の（１０）式を満たすか否かを検討し、満たす場合には（ステップＳ３４でＹｅｓ）、署名が有効であると判断し（Ｓ３５）、満たさない場合には（ステップＳ３４でＮｏ）、署名が無効であると判断する（Ｓ３６）。
【００９７】
【数１０】
0004988448.tif 000011
【００９８】
なお、本実施形態では、ｚ＝ｗで検証処理を行っているが、検証処理を行うことができれば、どのような検証式を用いてもよく、検証式の種類は問わない。
【００９９】
図９は、置換部１３６ｂにおける入れ替え処理を示すフローチャートである。
【０１００】
まず、置換部１３６ｂの中間状態格納部１３６ｄは、バッチインスタンス(ｘｉ，ｙｉ)（ｉ＝１，・・・，ｎ）を領域Ｔに格納する（Ｓ４０）。
【０１０１】
次に、置換部１３６ｂの擬似乱数生成部１３６ｃは、乱数ｋを生成する（Ｓ４１）。ここで、擬似乱数生成部１３６ｃは、乱数ｋと予め定められた初期ベクトルＩＶを擬似乱数生成器に入力し、予め定められた整数ｔに対して乱数列ｒ０，ｒ１，・・・，ｒ２ｔ−１を出力する（Ｓ４２）。ここで、整数ｔはバッチインスタンスを入れ替える回数を表すものであり、予め定めておく。
【０１０２】
繰り返し判定部１３６ｆは、ｉを初期化する（ｉに１を格納する）（Ｓ４３）。
【０１０３】
次に、繰り返し判定部１３６ｆは、ｉ≦ｔであるかどうかを判定する（Ｓ４４）。そして、ｉ≦ｔである場合には（ステップＳ４４においてＹｅｓ）、ステップＳ４５に進み、ｉ≦ｔではない場合には（ステップＳ４４においてＮｏ）、処理を終了する。
【０１０４】
ステップ４５では、入れ替え部１３６ｅは、領域Ｔに格納されているバッチインスタンスの（ｒ２ｉｍｏｄ ｎ）番目と（ｒ２ｉ＋１ｍｏｄ ｎ）番目とを入れ替える（Ｓ４５）。
【０１０５】
なお、擬似乱数生成器については、例えば、D. Wanatabe, S. Furuya, H. Yoshida, K. Takaragi, and B. Preneel, "A New Keystream Generator MUGI", IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E87-A, No.1, 2004. に詳細に記載されている。
【０１０６】
そして、ｉをインクリメント（ｉ←ｉ＋１）して（Ｓ４６）、ステップＳ４４に戻り処理を繰り返す。
【０１０７】
なお、整数ｔの値については、予め定められた固定値でもよいし、一括検証のたびに変更してもよい。
【０１０８】
また、置換の作成方法はこのような態様に限定されるわけではなく、例えば、事前に入れ替えを表すテーブル（入れ替え前の順番と入れ替え後の順番とを対応付けて格納したテーブル）を作成しておき、当該テーブルに基づいて入れ替えを行うようにしてもよく、実現可能であればその方法は問わない。
【０１０９】
さらに、置換方法は、一括検証のたびに変更してもよいし、複数回使用してから変更してもよい。ただし、特定の置換方法を複数回にわたって使用する場合は、安全性の観点から署名検証者に当該置換方法を知られないようにする必要がある。
【０１１０】
なお、バッチインスタンス(ｘｉ，ｙｉ)（ｉ＝１，・・・，ｎ）において、各ｉ（ｉ＝１，・・・，ｎ）に対して上述の（１）式を満たせば、上述の（１０）式を満たす。つまり、上述の署名一括検証方法は有効なバッチインスタンスを常に「有効」として受け入れる。この理由は以下の通りである。
【０１１１】
各ｉ（ｉ＝１，・・・，ｎ）に対して（１）式を満たせば、各ｉ（ｉ＝１，・・・，ｎ）に対して、下記の（１１）が成立する。
【０１１２】
【数１１】
0004988448.tif 000012
【０１１３】
そして、（１１）式より下記の（１２）式が成立するからである。
【０１１４】
【数１２】
0004988448.tif 000013
【０１１５】
そして、上述の署名の一括検証方法が無効なバッチインスタンスを「有効」として受け入れる確率の上限は高々１／ｑである。この理由は以下の通りである。
【０１１６】
ｉ０（１≦ｉ０≦ｎ）以外のｉ（ｉ＝１，・・・，ｎ）に対応する整数ｊ（ｉ）（１≦ｊ≦ｎ）が決まっているとき、下記の（１３）式及び（１４）式を満たすｊ（ｉ０）が存在する確立は、高々１／ｑだからである。但し、１≦ｊ（ｉ０）≦ｎである。
【０１１７】
【数１３】
0004988448.tif 000014
【０１１８】
【数１４】
0004988448.tif 000015
【０１１９】
また、非特許文献１に記載の一括検証と本実施形態に記載の一括検証（図１０ではRandom Shuffle Testという）における計算コスト（計算時間）との比較図を図１０に示す。
【０１２０】
上述のとおり、非特許文献１に記載の一括検証の計算コストは、検証したいバッチインスタンスの個数ｎとセキュリティパラメータｍの２つに依存するのに対し、本発明であるRandom Shuffle Testの計算コストは、検証したいバッチインスタンスの個数ｎにのみ依存する。
【０１２１】
従って、本実施形態に記載の一括検証は非特許文献１に記載の一括検証と比較して、より効率的に一括検証が可能であることがわかる。
【０１２２】
また、本実施形態に記載の一括検証が高い安全性を備える理由は以下の通りである。
【０１２３】
上述の通り、近年の計算機の能力からｍは８０程度に設定することが望ましいことが知られている。一方、近年の計算機の能力、及び現在までに知られている数学関数に対する攻撃方法からｑは１６０ビット程度以上の素数を用いる必要がある。
【０１２４】
このとき、非特許文献１に記載の一括検証におけるセキュリティレベルは８０程度なのに対し、本実施形態に記載の一括検証におけるセキュリティレベルは１６０程度となる。上述の通り、セキュリティレベルは大きいほど、安全性が高いことが知られている。したがって、本実施形態に記載の一括検証は高い安全性も有することがわかる。
【０１２５】
以上の通り、本実施形態の一括検証によれば、置換を行うこと、および、効率的に計算可能な検証式を用いること、により高い安全性と高い効率性を兼ね備えた署名一括検証が可能になる。
【０１２６】
なお、以上に記載した実施形態においては、下記の（１５）式を検証する代わりに、（１６）式を検証するようにしているが、このような態様には限定されない。
【０１２７】
【数１５】
0004988448.tif 000016
【０１２８】
【数１６】
0004988448.tif 000017
【０１２９】
例えば、下記の（１７）式を検証する代わりに、（１８）式を検証するようにしてもよい。
【０１３０】
【数１７】
0004988448.tif 000018
【０１３１】
【数１８】
0004988448.tif 000019
【０１３２】
但し、有限群Ｇは、加法群とする。
【０１３３】
ここで、（１７）式及び（１８）式におけるαは、上述と同様、任意の自然数であるが、このような形態に限定されず、順番ｉにより異なる数、例えば、ｉを変数とする任意の関数ｆ（ｉ）であってもよい。
【０１３４】
次に、第二の実施形態である署名一括検証システムについて説明する。第二の実施形態は、本発明をＤＳＡ署名に適用した例である。ここで、本実施形態における署名一括兼用システムも、第一の実施形態と同様に、署名装置２１０及び検証装置２３０を備える。
【０１３５】
図１１は、本実施形態で用いられる署名装置２１０の概略図である。
【０１３６】
図示するように、署名装置２１０は、記憶部２１１と、処理部２１４と、入力部１１７と、出力部１１８と、通信部１１９と、を備え、入力部１１７、出力部１１８及び通信部１１９については第一の実施形態と同様であるため、説明を省略する。
【０１３７】
記憶部２１１には、署名生成鍵記憶領域２１２と、データ記憶領域２１３と、が設けられている。
【０１３８】
署名生成鍵記憶領域２１２には、署名を行う際の鍵情報である署名生成鍵が記憶される。ここで、ＤＳＡ署名における署名生成鍵ｘは、ｘ：ｘ∈Ｚｑ−１なる整数である。
【０１３９】
データ記憶領域２１３には、署名を行う対象となるデータであるメッセージが記憶される。
【０１４０】
処理部２１４は、署名生成処理部２１５と、数学関数計算部２１６と、を備える。
【０１４１】
署名生成処理部２１５は、署名を行う対象となるデータであるメッセージに対する署名データを生成する処理を制御する。
【０１４２】
例えば、本実施形態では、署名生成処理部２１５は、署名を行う対象となるデータであるメッセージを、予め定められたハッシュ関数に入力することで、入力データを生成する。
【０１４３】
そして、署名生成処理部２１５は、署名生成鍵記憶領域２１２に記憶されている署名生成鍵を取得して、入力データとともに、数学関数計算部２１６に入力する。
【０１４４】
そして、署名生成処理部２１５は、数学関数計算部２１６より生成された署名を取得して、署名とメッセージとを署名データとして、通信部１３９を介して検証装置２３０に送信する。
【０１４５】
数学関数計算部２１６は、署名生成処理部２１５から入力された入力データに対して、署名生成処理部２１５から入力された署名生成鍵を用いて、予め定められたアルゴリズムによる暗号化を施して署名を生成する。
【０１４６】
ＤＳＡ署名において、上述の署名生成鍵ｘを用いたメッセージＭｉ（ｉ＝１，・・・，ｎ）に対する署名Ｓｉは、下記の（１９）式及び（２０）式で計算される。
【０１４７】
【数１９】
0004988448.tif 000020
【０１４８】
【数２０】
0004988448.tif 000021
【０１４９】
但し、ｋｉは署名生成時に生成した乱数であり、下記の（２１）式を満たす。
【０１５０】
【数２１】
0004988448.tif 000022
【０１５１】
また、σｉは、下記の（２２）式を満たす。
【０１５２】
【数２２】
0004988448.tif 000023
【０１５３】
ここで、Ｈは暗号学的ハッシュ関数を意味する。
【０１５４】
また、ＤＳＡ署名におけるシステムパラメータである（ｐ、ｑ、ｇ）は、下記の通りである。
【０１５５】
ｐ：２Ｌ−１＜ｐ＜２Ｌ、５１２≦Ｌ≦１０２４、Ｌｍｏｄ６４≡０なる素数。
【０１５６】
ｑ：ｑ｜（ｐ−１）、２１５９＜ｑ＜２１６０なる素数。
【０１５７】
ｇ：あるｈ∈Ｚｐ＊に対してｇ＝ｈ（ｐ−１）／ｑｍｏｄｐ。
【０１５８】
これらのシステムパラメータは、ネットワーク上に公開される。
【０１５９】
ここで、Ｚｑ＊は、ｘとｑとの最大公約数が１となるようなｑより小さい正の整数全体の集合である。
【０１６０】
そして、数学関数計算部２１６は、このようにして生成した署名を署名生成処理部２１５に出力する。
【０１６１】
以上に記載した署名装置２１０も、例えば、図５に示すような一般的なコンピュータ１６０で実現できる。
【０１６２】
例えば、記憶部２１１は、ＣＰＵ１６１がメモリ１６２又は外部記憶装置１６３を利用することにより実現可能であり、処理部２１４は、外部記憶装置１６３に記憶されている所定のプログラムをメモリ１６２にロードしてＣＰＵ１６１で実行することで実現可能であり、入力部１１７は、ＣＰＵ１６１が入力装置１６６を利用することで実現可能であり、出力部１１８は、ＣＰＵ１６１が出力装置１６７を利用することで実現可能であり、通信部１１９は、ＣＰＵ１６１が通信装置１６８を利用することで実現可能である。
【０１６３】
この所定のプログラムは、読取装置１６５を介して記憶媒体１６４から、あるいは、通信装置１６８を介してネットワークから、外部記憶装置１６３にダウンロードされ、それから、メモリ１６２上にロードされてＣＰＵ１６１により実行されるようにしてもよい。また、読取装置１６５を介して記憶媒体１６４から、あるいは、通信装置１６８を介してネットワークから、メモリ１６２上に直接ロードされ、ＣＰＵ１６１により実行されるようにしてもよい。
【０１６４】
図１２は、本実施形態で用いられる検証装置２３０の概略図である。
【０１６５】
検証装置２３０は、記憶部２３１と、処理部２３４と、入力部１３７と、出力部１３８と、通信部１３９と、を備え、入力部１３７、出力部１３８及び通信部１３９は、第一の実施形態と同様であるため、説明を省略する。
【０１６６】
記憶部２３１には、署名検証鍵記憶領域２３２と、署名データ記憶領域２３３と、が設けられている。
【０１６７】
署名検証鍵記憶領域２３２には、署名装置２１０から送信されてきた署名データに含まれている署名を復号化して検証するための鍵情報である署名検証鍵が記憶される。ここで、ＤＳＡ署名における署名検証鍵は、（ｙ、ｇ、ｐ、ｑ）である。なお、ｙ＝ｇｘである。
【０１６８】
署名データ記憶領域２３３には、署名装置２１０から送信されてきた署名データを記憶する。
【０１６９】
処理部２３４は、署名一括検証処理部２３５と、数学関数計算部２３６と、を備える。
【０１７０】
署名一括検証処理部２３５は、署名装置２１０から送信されてきた署名データを一括して検証する処理を制御する。
【０１７１】
例えば、本実施形態においては、署名一括検証処理部２３５は、署名検証鍵記憶領域２３２に記憶されている署名検証鍵及び署名データ記憶領域２３３に記憶されている署名データを記憶部２３１から取得し、数学関数計算部２３６に入力する。
【０１７２】
そして、署名一括検証処理部２３５は、数学関数計算部２３６から一括検証の結果を取得して、記憶部２３１に記憶するか、または、出力部１３８や通信部１３９を介して、検証結果を出力する。
【０１７３】
数学関数計算部２３６は、署名一括検証部２３５から入力された署名データに含まれている署名に対して、署名一括検証部２３５から入力された署名検証鍵を用いて、予め定められたアルゴリズムによる署名の一括検証を施して、署名の有効性を確認する。
【０１７４】
ここで、数学関数計算部２３６は、図示してはいないが、第一の実施形態と同様に、バッチインスタンス生成部と、置換部と、べき乗剰余計算部と、を備える。
【０１７５】
ＤＳＡ署名方式で生成された署名については、一括検証方式を適用できるように変形する必要があるため、数学関数計算部２３６のバッチインスタンス生成部は、署名装置２１０から取得した署名をバッチインスタンスに変形する。
【０１７６】
具体的には、数学関数計算部２３６のバッチインスタンス生成部は、上述の（１９）式で算出された署名Ｓｉを、上述の（２０）式、（２１）式及び（２２）式を満たすλｉ、ｋｉ、σｉを用いて、下記の（２３）式、（２４）式及び（２５）式によりバッチインスタンスを算出する。
【０１７７】
【数２３】
0004988448.tif 000024
【０１７８】
【数２４】
0004988448.tif 000025
【０１７９】
【数２５】
0004988448.tif 000026
【０１８０】
数学関数計算部２３６の置換部は、バッチインスタンス生成部で変換されたバッチインスタンスを任意の方法で入れ替えを行う。ここでは、第一の実施形態と同様の方法で入れ替えを行うものとする。
【０１８１】
例えば、バッチインスタンス(λｉ，ａｉ，ｂｉ)（ｉ＝１，・・・，ｎ）の順番を(λτ（ｉ），ａτ（ｉ），ｂτ（ｉ）)（ｉ＝１，・・・，ｎ）に入れ替える。ここで、τは、入れ替え方法を識別するための記号である。
【０１８２】
そして、数学関数計算部２３６のべき乗剰余計算部は、下記の（２６）式を満たすかどうかで検証を行う。
【０１８３】
【数２６】
0004988448.tif 000027
【０１８４】
即ち、（２６）式を満たす場合は「有効」として署名Ｓｉを受け入れ、（２６）式を満たさない場合は「無効」として署名Ｓｉを拒否する。なお、（２６）式におけるαは任意の自然数である。ここで、（２６）式におけるαｉについては、このような形態に限定されず、順番ｉにより異なる数、例えば、ｉを変数とする任意の関数ｆ（ｉ）であってもよい。
【０１８５】
以上に記載した検証装置２３０についても、図５に示すような、一般的なコンピュータ１６０で実現できる。
【０１８６】
例えば、記憶部２３１は、ＣＰＵ１６１がメモリ１６２又は外部記憶装置１６３を利用することにより実現可能であり、処理部２３４は、外部記憶装置１６３に記憶されている所定のプログラムをメモリ１６２にロードしてＣＰＵ１６１で実行することで実現可能であり、入力部１３７は、ＣＰＵ１６１が入力装置１６６を利用することで実現可能であり、出力部１３８は、ＣＰＵ１６１が出力装置１６７を利用することで実現可能であり、通信部１３９は、ＣＰＵ１６１が通信装置１６８を利用することで実現可能である。
【０１８７】
この所定のプログラムは、読取装置１６５を介して記憶媒体１６４から、あるいは、通信装置１６８を介してネットワークから、外部記憶装置１６３にダウンロードされ、それから、メモリ１６２上にロードされてＣＰＵ１６１により実行されるようにしてもよい。また、読取装置１６５を介して記憶媒体１６４から、あるいは、通信装置１６８を介してネットワークから、メモリ１６２上に直接ロードされ、ＣＰＵ１６１により実行されるようにしてもよい。
【０１８８】
図１３は、本実施形態における数学関数計算部２３６での一括検証処理を示すフローチャートである。
【０１８９】
数学関数計算部２３６での一括検証処理は、任意の個数の署名データの入力を署名一括検証処理部２３５より受けることで開始される（Ｓ５０）。
【０１９０】
任意の個数の署名データの入力を署名一括検証処理部２３５より受けると、数学関数計算部２３６のバッチインスタンス生成部は、入力された署名データに含まれる複数の署名Ｓｉ（ｉ＝１，・・・，ｎ）からバッチインスタンス(λｉ，ａｉ，ｂｉ)（ｉ＝１，・・・，ｎ）を生成する（Ｓ５１）。
【０１９１】
そして、数学関数計算部２３６の置換部は、置換群ＳＩＦＴｎから置換τをランダムに選び、即ち、任意の置き換え方法により、バッチインスタンス(λｉ，ａｉ，ｂｉ)（ｉ＝１，・・・，ｎ）の順番を(λτ（ｉ），ａτ（ｉ），ｂτ（ｉ）)（ｉ＝１，・・・，ｎ）に入れ替える（Ｓ５２）。
【０１９２】
次に、数学関数計算部２３６のべき乗剰余計算部は、入れ替えられた(λτ（ｉ），ａτ（ｉ），ｂτ（ｉ）)を用いて、上述の（２６）式を計算する（Ｓ５３）。
【０１９３】
そして、べき乗剰余計算部は、（２６）式を満たすか否かを検討し、満たす場合には（ステップＳ５３でＹｅｓ）、署名が有効であると判断し（Ｓ５４）、満たさない場合には（ステップＳ５３でＮｏ）、署名が無効であると判断する（Ｓ５５）。
【０１９４】
なお、本実施形態では、（２６）式で検証処理を行っているが、検証処理を行うことができれば、どのような検証式を用いてもよく、検証式の種類は問わない。
【０１９５】
本実施形態では、ある署名者によって署名された複数の署名（乃至はバッチインスタンス）を一括検証する場合を説明したが、複数の署名者がそれぞれ署名した複数の署名（又はバッチインスタンス）を一括検証することも可能である。
【０１９６】
例えば、署名生成鍵ｓｋｉと署名検証鍵ｐｋｉの組｛ｓｋｉ＝ｘｉ，ｐｋｉ＝（ｙｉ，ｇ，ｐ，ｑ）｝（ここで、ｙｉ＝ｇｘｉ）をもつ少なくとも一人以上のユーザＡｉ（１≦ｉ≦ｒ）がそれぞれ生成したバッチインスタンス（λｊ（ｉ），ａｊ（ｉ），ｂｊ（ｉ））｛１≦ｊ≦ｎ（ｉ）｝に対する一括検証として次の方法がある。
【０１９７】
一つ目の方法は、各ユーザのバッチインスタンスを入れ替えて、各々のユーザ毎に上述の（２３）式の両辺をそれぞれ掛け合わせた式を満たすか否かを検証する方法である。
【０１９８】
二つ目の方法は、二つ目は全ユーザＡｉ（１≦ｉ≦ｒ）のバッチインスタンスを入れ替えた後、（２６）式を満たすかどうかを検証する方法である。ただし、この方法の場合、（２６）式の右辺のｙの部分は、ｂｉがどのユーザによって生成されたバッチインスタンスであるかどうかによって変更する必要がある。
【０１９９】
本実施形態に記載の一括検証が非特許文献１に記載の一括検証と比較して、より効率的に一括検証が可能である理由は第一の実施形態と同様である。
【０２００】
また、本実施形態に記載の一括検証が高い安全性を有する理由も第一の実施形態と同様である。
【０２０１】
以上の通り、本実施形態の一括検証によれば、置換を用いること、及び効率的に計算可能な検証式を用いることにより、高い安全性と高い効率性を兼ね備えたＤＳＡ署名の一括検証が可能になる。
【０２０２】
なお、以上に記載した一括検証方式では、ＤＳＡ署名方式を利用したが、ＤＳＡ署名の代わりに、ＤＳＡ＊署名を利用することも可能である。
【０２０３】
ＤＳＡ＊署名では、上述の（２３）式、（２４）式及び（２５）式で算出されるバッチインスタンスが署名となっているため（署名装置で計算されるため）、検証装置２３０においてバッチインスタンスを生成する必要がなくなる。
【０２０４】
なお、ＤＳＡ＊署名は、非特許文献１に記載されており、その安全性はＤＳＡ署名と等価である。
【０２０５】
次に、第三の実施形態である署名一括検証システムについて説明する。第三の実施形態は、本発明をＥＣＤＳＡ署名に適用した例である。ここで、本実施形態における署名一括兼用システムも、第一の実施形態と同様に、署名装置３１０及び検証装置３３０を備える。
【０２０６】
図１４は、本実施形態で用いられる署名装置３１０の概略図である。
【０２０７】
図示するように、署名装置３１０は、記憶部３１１と、処理部３１４と、入力部１１７と、出力部１１８と、通信部１１９と、を備え、入力部１１７、出力部１１８及び通信部１１９については第一の実施形態と同様であるため、説明を省略する。
【０２０８】
記憶部３１１には、署名生成鍵記憶領域３１２と、データ記憶領域３１３と、が設けられている。
【０２０９】
署名生成鍵記憶領域３１２には、署名を行う際の鍵情報である署名生成鍵が記憶される。ここで、ＥＣＤＳＡ署名における署名生成鍵ｄは、ｄ：ｄ∈Ｚｎ−１なる整数である。
【０２１０】
データ記憶領域３１３には、署名を行う対象となるデータであるメッセージが記憶される。
【０２１１】
処理部３１４は、署名生成処理部３１５と、数学関数計算部３１６と、を備える。
【０２１２】
署名生成処理部３１５は、署名を行う対象となるデータであるメッセージに対する署名データを生成する処理を制御する。
【０２１３】
例えば、本実施形態では、署名生成処理部３１５は、署名を行う対象となるデータであるメッセージを、予め定められたハッシュ関数に入力することで、入力データを生成する。
【０２１４】
そして、署名生成処理部３１５は、署名生成鍵記憶領域３１２に記憶されている署名生成鍵を取得して、入力データとともに、数学関数計算部３１６に入力する。
【０２１５】
そして、署名生成処理部３１５は、数学関数計算部３１６より生成された署名を取得して、署名とメッセージとを署名データとして、通信部１３９を介して検証装置３３０に送信する。
【０２１６】
数学関数計算部３１６は、署名生成処理部３１５から入力された入力データに対して、署名生成処理部３１５から入力された署名生成鍵を用いて、予め定められたアルゴリズムによる暗号化を施して署名を生成する。
【０２１７】
ＥＣＤＳＡ署名において、上述の署名生成鍵ｄを用いたメッセージＭｉ（ｉ＝１，・・・，ｎ）に対する署名Ｓｉは、下記の（２７）式、（２８）式、（２９）式及び（３０）式で計算される。
【０２１８】
【数２７】
0004988448.tif 000028
【０２１９】
【数２８】
0004988448.tif 000029
【０２２０】
【数２９】
0004988448.tif 000030
【０２２１】
【数３０】
0004988448.tif 000031
【０２２２】
ここで、Ｈは暗号学的ハッシュ関数を意味する。また、ｘ（Ｒｉ）は楕円曲線Ｅ（Ｆｑ）上の点Ｒｉのｘ座標を表す。
【０２２３】
また、ｋｉは署名生成時に生成した乱数であり、下記の（３１）式を満たす。
【０２２４】
【数３１】
0004988448.tif 000032
【０２２５】
なお、ＥＣＤＳＡ署名におけるシステムパラメータは、下記の通りである。
【０２２６】
Ｅ／Ｆｑ：有限体Ｆｑ上定義された楕円曲線。
【０２２７】
ｑ：ビットサイズが１６０以上である素数ｐのべき。
【０２２８】
#Ｅ（Ｆｑ）＝ｎ×ｈ（但し、ｈは小さな整数、ｎは大きな素数）。
【０２２９】
Ｐ：位数がｎであるようなＥ（Ｆｑ）上の点。
【０２３０】
これらのシステムパラメータは、ネットワーク上に公開される。
【０２３１】
そして、数学関数計算部３１６は、このようにして生成した署名を署名生成処理部３１５に出力する。
【０２３２】
以上に記載した署名装置３１０も、例えば、図５に示すような一般的なコンピュータ１６０で実現できる。
【０２３３】
例えば、記憶部３１１は、ＣＰＵ１６１がメモリ１６２又は外部記憶装置１６３を利用することにより実現可能であり、処理部３１４は、外部記憶装置１６３に記憶されている所定のプログラムをメモリ１６２にロードしてＣＰＵ１６１で実行することで実現可能であり、入力部１１７は、ＣＰＵ１６１が入力装置１６６を利用することで実現可能であり、出力部１１８は、ＣＰＵ１６１が出力装置１６７を利用することで実現可能であり、通信部１１９は、ＣＰＵ１６１が通信装置１６８を利用することで実現可能である。
【０２３４】
この所定のプログラムは、読取装置１６５を介して記憶媒体１６４から、あるいは、通信装置１６８を介してネットワークから、外部記憶装置１６３にダウンロードされ、それから、メモリ１６２上にロードされてＣＰＵ１６１により実行されるようにしてもよい。また、読取装置１６５を介して記憶媒体１６４から、あるいは、通信装置１６８を介してネットワークから、メモリ１６２上に直接ロードされ、ＣＰＵ１６１により実行されるようにしてもよい。
【０２３５】
図１５は、本実施形態で用いられる検証装置３３０の概略図である。
【０２３６】
検証装置３３０は、記憶部３３１と、処理部３３４と、入力部１３７と、出力部１３８と、通信部１３９と、を備え、入力部１３７、出力部１３８及び通信部１３９は、第一の実施形態と同様であるため、説明を省略する。
【０２３７】
記憶部３３１には、署名検証鍵記憶領域３３２と、署名データ記憶領域３３３と、が設けられている。
【０２３８】
署名検証鍵記憶領域３３２には、署名装置３１０から送信されてきた署名データに含まれている署名を復号化して検証するための鍵情報である署名検証鍵が記憶される。ここで、ＥＣＤＳＡ署名における署名検証鍵Ｑは、Ｑ＝ｄＰである。
【０２３９】
署名データ記憶領域３３３には、署名装置３１０から送信されてきた署名データを記憶する。
【０２４０】
処理部３３４は、署名一括検証処理部３３５と、数学関数計算部３３６と、を備える。
【０２４１】
署名一括検証処理部３３５は、署名装置３１０から送信されてきた署名データを一括して検証する処理を制御する。
【０２４２】
例えば、本実施形態においては、署名一括検証処理部３３５は、署名検証鍵記憶領域３３２に記憶されている署名検証鍵及び署名データ記憶領域３３３に記憶されている署名データを記憶部３３１から取得し、数学関数計算部３３６に入力する。
【０２４３】
そして、署名一括検証処理部３３５は、数学関数計算部３３６から一括検証の結果を取得して、記憶部３３１に記憶するか、または、出力部１３８や通信部１３９を介して、検証結果を出力する。
【０２４４】
数学関数計算部３３６は、署名一括検証部３３５から入力された署名データに含まれている署名に対して、署名一括検証部３３５から入力された署名検証鍵を用いて、予め定められたアルゴリズムによる署名の一括検証を施して、署名の有効性を確認する。
【０２４５】
ここで、数学関数計算部３３６は、図示してはいないが、第一の実施形態とは異なり、バッチインスタンス生成部と、置換部と、スカラー倍数計算部と、を備える。
【０２４６】
なお、スカラー倍数計算部は、置換部で入れ替えられたバッチインスタンスをスカラー倍数計算することで、検証を行う。
【０２４７】
ＥＣＤＳＡ署名方式で生成された署名については、一括検証方式を適用できるように変形する必要があるため、数学関数計算部３３６のバッチインスタンス生成部は、署名装置３１０から取得した署名をバッチインスタンスに変形する。
【０２４８】
具体的には、数学関数計算部３３６のバッチインスタンス生成部は、上述の（２７）式で算出された署名Ｓｉを、上述の（２８）式、（２９）式及び（３０）式を用いて、下記の（３２）式に示すバッチインスタンスを算出する。
【０２４９】
【数３２】
0004988448.tif 000033
【０２５０】
数学関数計算部３３６の置換部は、バッチインスタンス生成部で変換されたバッチインスタンスを任意の方法で入れ替えを行う。ここでは、第一の実施形態と同様の方法で入れ替えを行うものとする。
【０２５１】
例えば、バッチインスタンス(σｉ，Ｒｉ)（ｉ＝１，・・・，ｎ）の順番を(στ（ｉ），Ｒτ（ｉ）)（ｉ＝１，・・・，ｎ）に入れ替える。ここで、τは、入れ替え方法を示す記号である。
【０２５２】
そして、数学関数計算部３３６のスカラー倍数計算部は、下記の（３３）式を満たすかどうかで検証を行う。
【０２５３】
【数３３】
0004988448.tif 000034
【０２５４】
即ち、（３３）式を満たす場合は「有効」として署名Ｓｉを受け入れ、（３３）式を満たさない場合は「無効」として署名Ｓｉを拒否する。なお、（３３）式におけるαは任意の自然数である。ここで、（３３）式におけるαｉについては、このような形態に限定されず、順番ｉによりなる数、例えば、ｉを変数とする任意の関数ｆ（ｉ）であってもよい。
【０２５５】
以上に記載した検証装置３３０についても、図５に示すような、一般的なコンピュータ１６０で実現できる。
【０２５６】
例えば、記憶部３３１は、ＣＰＵ１６１がメモリ１６２又は外部記憶装置１６３を利用することにより実現可能であり、処理部３３４は、外部記憶装置１６３に記憶されている所定のプログラムをメモリ１６２にロードしてＣＰＵ１６１で実行することで実現可能であり、入力部１３７は、ＣＰＵ１６１が入力装置１６６を利用することで実現可能であり、出力部１３８は、ＣＰＵ１６１が出力装置１６７を利用することで実現可能であり、通信部１３９は、ＣＰＵ１６１が通信装置１６８を利用することで実現可能である。
【０２５７】
この所定のプログラムは、読取装置１６５を介して記憶媒体１６４から、あるいは、通信装置１６８を介してネットワークから、外部記憶装置１６３にダウンロードされ、それから、メモリ１６２上にロードされてＣＰＵ１６１により実行されるようにしてもよい。また、読取装置１６５を介して記憶媒体１６４から、あるいは、通信装置１６８を介してネットワークから、メモリ１６２上に直接ロードされ、ＣＰＵ１６１により実行されるようにしてもよい。
【０２５８】
図１６は、本実施形態における数学関数計算部３３６での一括検証処理を示すフローチャートである。
【０２５９】
数学関数計算部３３６での一括検証処理は、任意の個数の署名データの入力を署名一括検証処理部３３５より受けることで開始される（Ｓ６０）。
【０２６０】
任意の個数の署名データの入力を署名一括検証処理部３３５より受けると、数学関数計算部３３６のバッチインスタンス生成部は、入力された署名データに含まれる複数の署名Ｓｉ（ｉ＝１，・・・，ｎ）からバッチインスタンス(σｉ，Ｒｉ)（ｉ＝１，・・・，ｎ）を生成する（Ｓ６１）。
【０２６１】
そして、数学関数計算部３３６の置換部は、置換群ＳＩＦＴｎから置換τをランダムに選び、即ち、任意の置き換え方法により、バッチインスタンス(σｉ，Ｒｉ)（ｉ＝１，・・・，ｎ）の順番を(στ（ｉ），Ｒτ（ｉ）)（ｉ＝１，・・・，ｎ）に入れ替える（Ｓ６２）。
【０２６２】
次に、数学関数計算部３３６のスカラー倍数計算部は、入れ替えられたバッチインスタンス(στ（ｉ），Ｒτ（ｉ）)（ｉ＝１，・・・，ｎ）を用いて、上述の（３３）式を計算する（Ｓ６３）。
【０２６３】
そして、スカラー倍数計算部は、（３３）式を満たすか否かを検討し、満たす場合には（ステップＳ６３でＹｅｓ）、署名が有効であると判断し（Ｓ６４）、満たさない場合には（ステップＳ５３でＮｏ）、署名が無効であると判断する（Ｓ６５）。
【０２６４】
なお、本実施形態では、（３３）式で検証処理を行っているが、検証処理を行うことができれば、どのような検証式を用いてもよく、検証式の種類は問わない。
【０２６５】
本実施形態では、ある署名者によって署名された複数の署名（乃至はバッチインスタンス）を一括検証する場合を説明したが、複数の署名者がそれぞれ署名した複数の署名（又はバッチインスタンス）を一括検証することも可能である。
【０２６６】
例えば、署名生成鍵ｓｋｉと署名検証鍵ｐｋｉの組（ｓｋｉ＝ｄｉ，ｐｋｉ＝Ｑｉ）（ここで、Ｑｉ＝ｄｉＰ）をもつ少なくとも一人以上のユーザＡｉ（１≦ｉ≦ｒ）がそれぞれ生成したバッチインスタンス（σｊ（ｉ），ａｊ（ｉ），ｂｊ（ｉ））｛１≦ｊ≦ｎ（ｉ）｝に対する一括検証として次の方法がある。
【０２６７】
一つ目の方法は、各ユーザのバッチインスタンスを入れ替えて、各ユーザ毎に上述の（３３）式の両辺をそれぞれ掛け合わせた式を満たすか否かを検証する方法である。
【０２６８】
二つ目の方法は、二つ目は全ユーザＡｉ（１≦ｉ≦ｒ）のバッチインスタンスを入れ替えた後、（３３）式を満たすかどうかを検証する方法である。ただし、この方法の場合、（３３）式の右辺のＱの部分は、Ｒｉがどのユーザによって生成されたバッチインスタンスであるかどうかによって変更する必要がある。
【０２６９】
本実施形態に記載の一括検証が非特許文献１に記載の一括検証と比較して、より効率的に一括検証が可能である理由は第一の実施形態と同様である。
【０２７０】
また、本実施形態に記載の一括検証が高い安全性を有する理由も第一の実施形態と同様である。
【０２７１】
以上の通り、本実施形態の一括検証によれば、置換を用いること、及び効率的に計算可能な検証式を用いることにより、高い安全性と高い効率性を兼ね備えたＥＣＤＳＡ署名の一括検証が可能になる。
【０２７２】
なお、以上に記載した一括検証方式では、ＥＣＤＳＡ署名方式を利用したが、ＥＣＤＳＡ署名の代わりに、ＥＣＤＳＡ＊署名を利用することも可能である。
【０２７３】
ＥＣＤＳＡ＊署名では、上述の（３２）式で算出されるバッチインスタンスが署名となっているため（署名装置で計算されるため）、検証装置３３０においてバッチインスタンスを生成する必要がなくなる。
【０２７４】
なお、ＥＣＤＳＡ＊署名は、非特許文献２に記載されており、その安全性はＥＣＤＳＡ署名と等価である。
【０２７５】
なお、上記各実施形態では、署名生成処理部、署名一括検証処理部を、ソフトウェアで実現するものとして説明したが、専用のハードウェアを用いて実現してもよい。また、数学関数計算部を専用ハードウェアで実現しても良い。
【０２７６】
以上に記載した署名一括検証システムについては、署名装置１１０、２１０、３１０から大量の署名データが検証装置１３０、２３０、３３０に送られてくるようなシステムで利用することができる。
【０２７７】
例えば、図１７（リアルタイム監視システム１７０の概略図）に示すような監視カメラを用いたリアルタイム監視システム１７０に利用することができる。
【０２７８】
図示するように、リアルタイム監視システム１７０は、監視カメラ１７１と、署名装置１１０、２１０、３１０と、検証装置１３０、２３０、３３０と、モニタ１７２と、を備えており、署名装置１１０、２１０、３１０及び検証装置１３０、２３０、３３０はネットワーク１５０に接続されている。
【０２７９】
そして、例えば、監視対象とするエリアに監視カメラ１７１を設置し、撮像映像を署名装置１１０、２１０、３１０で署名データにして、ネットワーク１５０を介して、警備会社等の監視センタに設置されている検証装置１３０、２３０、３３０に送信し、検証装置１３０、２３０、３３０に蓄積しておく。
【０２８０】
検証装置１３０、２３０、３３０では、蓄積した署名データに含まれている撮像映像を確認する必要が出てきた場合に、蓄積された署名データの内必要な部分を一括して検証することで、特定の監視カメラ１７１で撮像され、データに改ざんがなされていないことを検証することができる。
【０２８１】
このような検証を行う際に、本発明による一括検証を行うことで、安全性の高い検証を効率的に行うことができるようになる。
【図面の簡単な説明】
【０２８２】
【図１】第一の実施形態である署名一括検証システムの概略図。
【図２】署名装置の概略図。
【図３】検証装置の概略図。
【図４】数学関数計算部の概略図。
【図５】コンピュータの概略図。
【図６】署名装置における署名生成処理を示すシーケンス図。
【図７】検証装置における署名の一括検証処理を示すシーケンス図。
【図８】数学関数計算部での一括検証処理を示すフローチャート。
【図９】置換部における入れ替え処理を示すフローチャート。
【図１０】計算コスト（計算時間）の比較図。
【図１１】署名装置の概略図。
【図１２】検証装置の概略図。
【図１３】数学関数計算部での一括検証処理を示すフローチャート。
【図１４】署名装置の概略図。
【図１５】検証装置の概略図。
【図１６】数学関数計算部での一括検証処理を示すフローチャート。
【図１７】リアルタイム監視システムの概略図。
【符号の説明】
【０２８３】
１００  署名一括検証システム
１１０、２１０、３１０  署名装置
１１１、２１１、３１１  記憶部
１１４、２１４、３１４  処理部
１３０、２３０、３３０  検証装置
１３１、２３１、３３１  記憶部
１３４、２３４、３３４  処理部
【図１】
0004988448.tif 000038
【図２】
0004988448.tif 000039
【図３】
0004988448.tif 000040
【図４】
0004988448.tif 000041
【図５】
0004988448.tif 000042
【図６】
0004988448.tif 000043
【図７】
0004988448.tif 000044
【図８】
0004988448.tif 000045
【図９】
0004988448.tif 000046
【図１０】
0004988448.tif 000047
【図１１】
0004988448.tif 000048
【図１２】
0004988448.tif 000049
【図１３】
0004988448.tif 000050
【図１４】
0004988448.tif 000051
【図１５】
0004988448.tif 000052
【図１６】
0004988448.tif 000053
【図１７】
0004988448.tif 000054