(57)【要約】  【課題】  検証する署名の個数が多い場合であっても、高い安全性と高い効率性を兼ね備える一括検証を実現すること。  【解決手段】  署名装置１１０から送信されてくる複数の署名データを検証装置１３０で一括して検証する。検証装置１３０では、複数の署名データを二重スカラー倍算により算出される値と、多重スカラー倍算により算出される値と、が対応しているか否かで一括して検証し、この多重スカラー倍算のスカラー値に対して、Frobenius展開を行い、展開値を算出し、この展開値において共通因数をくくりだして計算する。【選択図】図１
2010020189.tif 000002
【特許請求の範囲】
【請求項１】
楕円曲線に基づく署名方式により生成された複数の署名データを、二重スカラー倍算により算出される値と、多重スカラー倍算により算出される値と、が対応しているか否かで一括して検証する一括検証装置であって、
前記多重スカラー倍算のスカラー値に対して、Frobenius展開を行い、展開値を算出する処理と、
前記展開値を、共通因数を係数とする値の第一の値と、その他の値の第二の値と、からなる第一の加算値に分解する処理と、
前記第一の加算値を、前記第一の値において共通因数をくくりだし、第二の加算値とする処理と、
前記第二の加算値により前記多重スカラー倍算を行う処理と、を行う制御部を備えること、
を特徴とする一括検証装置。
【請求項２】
請求項１に記載の一括検証装置であって、
前記Frobenius展開は、ｘ２＋１＝０の根となる複素数λに対し、（０，±１，±λ）を係数とするFrobenius展開であって、
前記制御部は、前記第一の加算値を、前記第一の値においてλを共通因数としてくくりだし、前記第二の加算値とする処理を行うこと、
を特徴とする一括検証装置。
【請求項３】
請求項１に記載の一括検証装置であって、
前記Frobenius展開は、ｘ２＋ｘ＋１＝０の根となる複素数ωに対し、（０，±１，±ω，±ω２）を係数とするFrobenius展開であって、
前記制御部は、前記第一の加算値を、前記第一の値においてω及びω２を共通因数としてくくりだし、前記第二の加算値とする処理を行うこと、
を特徴とする一括検証装置。
【請求項４】
請求項２に記載の一括検証装置であって、
前記楕円曲線は、Ｅａ｛ｙ２＝ｘ３＋ａｘ（ａ≠０は有限体Ｆ５の元）｝であり、
前記λは、前記楕円曲線Ｅａにおける自己同型写像λ（Ｅａ｛（ｘ，ｙ）→（−ｘ，αｙ）｝、但し、αは位数４であるような有限体Ｆ５の元）であること、
を特徴とする一括検証装置。
【請求項５】
請求項３に記載の一括検証装置であって、
前記楕円曲線は、Ｅｂ｛ｙ２＝ｘ３＋ｂ（ｂ≠０は有限体Ｆ７の元）｝であり、
前記ωは、前記楕円曲線Ｅｂにおける自己同型写像ω（Ｅｂ｛（ｘ，ｙ）→（βｘ，ｙ）｝、但し、βは位数３であるような有限体Ｆ７の元）であること、
を特徴とする一括検証装置。
【請求項６】
コンピュータを、楕円曲線に基づく署名方式により生成された複数の署名データを、二重スカラー倍算により算出される値と、多重スカラー倍算により算出される値と、が対応しているか否かで一括して検証する一括検証装置として機能させるプログラムであって、
前記コンピュータを、
前記多重スカラー倍算のスカラー値に対して、（０，±１，±α）を係数とするFrobenius展開を行い、展開値を算出する処理と、
前記展開値を、αを係数とする値の第一の値と、その他の値の第二の値と、からなる第一の加算値に分解する処理と、
前記第一の加算値を、前記第一の値においてαを共通因数としてくくりだし、第二の加算値とする処理と、
前記第二の加算値により前記多重スカラー倍算を行う処理と、を行う制御手段として機能させること、
を特徴とするプログラム。
【請求項７】
請求項６に記載のプログラムであって、
前記Frobenius展開は、ｘ２＋１＝０の根となる複素数λに対し、（０，±１，±λ）を係数とするFrobenius展開であって、
前記制御手段に、前記第一の加算値を、前記第一の値においてλを共通因数としてくくりだし、前記第二の加算値とする処理を行わせること、
を特徴とするプログラム。
【請求項８】
請求項６に記載のプログラムであって、
前記Frobenius展開は、ｘ２＋ｘ＋１＝０の根となる複素数ωに対し、（０，±１，±ω，±ω２）を係数とするFrobenius展開であって、
前記制御手段に、前記第一の加算値を、前記第一の値においてω及びω２を共通因数としてくくりだし、前記第二の加算値とする処理を行わせること、
を特徴とするプログラム。
【請求項９】
請求項７に記載のプログラムであって、
前記楕円曲線は、Ｅａ｛ｙ２＝ｘ３＋ａｘ（ａ≠０は有限体Ｆ５の元）｝であり、
前記λは、前記楕円曲線Ｅａにおける自己同型写像λ（Ｅａ｛（ｘ，ｙ）→（−ｘ，αｙ）｝、但し、αは位数４であるような有限体Ｆ５の元）であること、
を特徴とするプログラム。
【請求項１０】
請求項８に記載のプログラムであって、
前記楕円曲線は、Ｅｂ｛ｙ２＝ｘ３＋ｂ（ｂ≠０は有限体Ｆ７の元）｝であり、
前記ωは、前記楕円曲線Ｅｂにおける自己同型写像ω（Ｅｂ｛（ｘ，ｙ）→（βｘ，ｙ）｝、但し、βは位数３であるような有限体Ｆ７の元）であること、
を特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、署名データを一括して検証する技術に関する。
【背景技術】
【０００２】
デジタル署名の技術では、署名者は、署名対象の電子データに対し、署名者が秘密にしている署名鍵を用いて署名データを生成し、署名検証者は、公開されている検証鍵を用いて署名データを復号して、署名対象となっている電子データと比較することにより、署名者の真偽や電子データに対する改ざんの有無等を検出することができるようにしている。
【０００３】
このようなデジタル署名の技術では、検証を行う際に重い処理（数学的な計算）を繰り返し行わなければならないが、例えば、非特許文献１に記載の技術では、複数のデジタル署名を一括して検証することで、デジタル署名の検証処理の効率性を向上させている。
【０００４】
例えば、通常の署名検証では、各ｉ(ｉは順番を示すインデックスであって、１≦ｉ≦ｕ（ｕ：２以上の自然数）を満たす自然数)に対応するデジタル署名に対して、下記の（１）式を満たすかどうかを各々別個に検証する。
【０００５】
【数１】
2010020189.tif 000003
【０００６】
但し、各ｉ(ｉ=１，・・・，ｕ)に対してｘｉ、ｙｉはそれぞれ下記の（２）式及び（３）式を満たす。
【０００７】
【数２】
2010020189.tif 000004
【０００８】
【数３】
2010020189.tif 000005
【０００９】
ここで、Ｇは、位数をｎ（ｎは大きな素数）とする有限巡回群であり、ｇは、群Ｇの生成元である。さらに、(ｘｉ，ｙｉ)は、（１）式を満たすか否かを検証するための組（バッチインスタンス）である。
【００１０】
このようなデジタル署名の技術では、検証を行う際に重い処理（数学的な計算）を繰り返し行わなければならないが、例えば、非特許文献１に記載のRandom Subset Testでは、下記の（４）式及び（５）式を満たすか否かを検証することで、複数のデジタル署名を一括して検証することで（重い処理を一回だけ行うことで）、デジタル署名を効率的に検証することができるようにしている。
【００１１】
【数４】
2010020189.tif 000006
【００１２】
【数５】
2010020189.tif 000007
【００１３】
ここで、（５）式に示すように、各ｉ（ｉ=１,・・・,ｕ）に対してｓｉは０又は１がランダムに選ばれたものである。
【００１４】
また、非特許文献１に記載のSmall Exponents Testでは、下記の（６）式及び（７）式を満たすか否かを検証することで、デジタル署名を効率的に検証することができるようにしている。
【００１５】
【数６】
2010020189.tif 000008
【００１６】
【数７】
2010020189.tif 000009
【００１７】
ここで、ｓｉは０又は２ｍ−１からランダムに選ばれた整数である。なお、ｍ（ｍは任意に選択された正の整数）はセキュリティレベルであり、このｍによってセキュリティレベルが定まる。
【００１８】
そして、非特許文献１に記載の一括検証における効率性は、バッチインスタンスの個数ｎとセキュリティレベルｍに依存する。
【００１９】
また、楕円曲線に基づく署名方式における一括検証では、多重スカラー倍算を行う処理が、処理全体の大部分を占める。そのため、Frobenius展開を用いた効率的な一括検証を行う技術が、非特許文献２、非特許文献３に記載されている。
【００２０】
【非特許文献１】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.
【非特許文献２】J. Cheon and D. Lee, "Use of Sparse and/or Complex Exponents in Batch Verification of Exponentiation", IEEE. T. on Computers, Vol.55, No.12, 2006.
【非特許文献３】J. Cheon and J. Yi, "Fast Batch Verification of Multiple Signature"，PKC’07，LNCS  4450，Springer-Verlag，pp．442-457，2007．
【発明の開示】
【発明が解決しようとする課題】
【００２１】
以上に記載したように、非特許文献１に記載の一括検証処理の技術では、通常の署名検証処理と比較して効率性を向上させることができるが、楕円曲線に基づく署名方式への適用に関しては記載がなされておらず、楕円曲線に基づく署名方式において十分な効率性を発揮することはできないものと思われる。
【００２２】
また、非特許文献２及び非特許文献３に記載の一括検証方法は、検証する署名の個数が増えると、多重スカラー倍算の中間値の更新が頻繁に発生するため、この中間値の更新が処理性能のボトルネックとなっており、十分な処理性能を達成することが困難である。さらに、このような中間値の更新を避けるためには、中間値の結果すべてを記憶領域に格納しておく方法もあるが、この場合、大きな記憶領域を必要とするため、実システムにおいて様々なアプリケーションが実行されているような環境では、アプリケーションの処理時間に大きな影響を及ぼす。
【００２３】
そこで、本発明は、検証する署名の個数が多い場合であっても、高い安全性と高い効率性を兼ね備える一括検証を実現することを目的とする。
【課題を解決するための手段】
【００２４】
以上の課題を解決するため、本発明は、スカラー値をFrobinius展開した値において共通因数をくくり出すことで、乗算回数を減らす。
【００２５】
例えば、本発明は、楕円曲線に基づく署名方式により生成された複数の署名データを、二重スカラー倍算により算出される値と、多重スカラー倍算により算出される値と、が対応しているか否かで一括して検証する一括検証装置であって、前記多重スカラー倍算のスカラー値に対して、Frobinius展開を行い、展開値を算出する処理と、前記展開値を、共通因数を係数とする値の第一の値と、その他の値の第二の値と、からなる第一の加算値に分解する処理と、前記第一の加算値を、前記第一の値において共通因数をくくりだし、第二の加算値とする処理と、前記第二の加算値により前記多重スカラー倍算を行う処理と、を行う制御部を備えること、を特徴とする。
【発明の効果】
【００２６】
以上のように、本発明によれば、検証する署名の個数が多い場合であっても、高い安全性と高い効率性を兼ね備える一括検証を実現することができる。
【発明を実施するための最良の形態】
【００２７】
図１は、本発明の第一の実施形態である署名一括検証システム１００の概略図である。
【００２８】
図示するように、署名一括検証システム１００は、署名装置１１０と、検証装置１３０と、を備え、これらの署名装置１１０及び検証装置１３０は、ネットワーク１５０を介して相互に情報の送受信を行うことができるようにされている。
【００２９】
そして、本実施形態である署名一括検証システム１００では、署名装置１１０でメッセージＭに対する署名Ｓの生成を行い、検証装置１３０で署名Ｓの一括検証を行う。
【００３０】
図２は、署名装置１１０の概略図である。
【００３１】
ここで、本実施形態における署名方式は、ＥＣＤＳＡ署名、または、ＥＣＤＳＡ＊署名を用いるが、このような態様に限定されるわけではない。
【００３２】
図示するように、署名装置１１０は、記憶部１１１と、制御部１１４と、入力部１１７と、出力部１１８と、通信部１１９と、を備える。
【００３３】
記憶部１１１は、署名鍵記憶領域１１２と、データ記憶領域１１３と、を備える。
【００３４】
署名鍵記憶領域１１２には、署名を行う際の鍵情報である署名鍵を特定する情報が記憶される。
【００３５】
ここで、ＥＣＤＳＡ署名（または、ＥＣＤＳＡ＊署名）における署名鍵ｄは、下記の（８）式で示される整数である。
【００３６】
【数８】
2010020189.tif 000010
【００３７】
データ記憶領域１１３には、署名を行う対象となるデータであるメッセージを特定する情報が記憶される。
【００３８】
制御部１１４は、署名生成処理部１１５と、数学関数計算部１１６と、を備える。
【００３９】
署名生成処理部１１５は、署名を行う対象となるデータであるメッセージＭに対する署名データを生成する処理を制御する。
【００４０】
例えば、本実施形態では、署名生成処理部１１５は、署名を行う対象となるデータであるメッセージＭを、予め定められたハッシュ関数Ｈに入力することで、入力データを生成する。
【００４１】
そして、署名生成処理部１１５は、署名鍵記憶領域１１２に記憶されている署名鍵を取得して、入力データとともに、数学関数計算部１１６に入力する。
【００４２】
また、署名生成処理部１１５は、数学関数計算部１１６より生成された署名Ｓを取得して、署名ＳとメッセージＭとを署名データとして、通信部１１９を介して検証装置１３０に送信する。
【００４３】
数学関数計算部１１６は、署名生成処理部１１５から入力された入力データに対して、署名生成処理部１１５から入力された署名鍵を用いて、予め定められたアルゴリズムによる暗号化を施して署名を生成する。
【００４４】
例えば、ＥＣＤＳＡ署名において、上述の署名鍵ｄを用いたメッセージＭｉ（ｉ＝１，・・・，ｕ）に対する署名Ｓｉは、下記の（９）式、（１０）式、（１１）式及び（１２）式で計算される。
【００４５】
【数９】
2010020189.tif 000011
【００４６】
【数１０】
2010020189.tif 000012
【００４７】
【数１１】
2010020189.tif 000013
【００４８】
【数１２】
2010020189.tif 000014
【００４９】
ここで、Ｈは暗号学的ハッシュ関数を意味する。また、ｘ（Ｒｉ）は楕円曲線Ｅ（Ｆｑｅ）上の点Ｒｉのｘ座標を表す。
【００５０】
また、ｋｉは署名生成時に生成した乱数であり、下記の（１３）式を満たす。
【００５１】
【数１３】
2010020189.tif 000015
【００５２】
なお、ＥＣＤＳＡ署名（または、ＥＣＤＳＡ＊署名）におけるシステムパラメータは、下記の通りである。
【００５３】
Ｅ／Ｆｑ：有限体Ｆｑ上において定義された楕円曲線。
【００５４】
＃Ｅ（Ｆｑ）＝ｎ×ｈ（但し、ｈは小さな整数、ｎは大きな素数）。
【００５５】
ｑ：ｎのビットサイズが１６０以上である素数ｐのべき(ｑ＝ｐｒ)。
【００５６】
Ｐ：位数がｎであるようなＥ（Ｆｑ）上の点。
【００５７】
これらのシステムパラメータは、ネットワーク上に公開される。
【００５８】
そして、数学関数計算部１１６は、このようにして生成した署名を署名生成処理部１１５に出力する。
【００５９】
入力部１１７は、情報の入力を受け付ける。
【００６０】
出力部１１８は、情報を出力する。
【００６１】
通信部１１９は、ネットワーク１５０を介して、情報の送受信を行う。
【００６２】
以上に記載した署名装置１１０は、例えば、図３（コンピュータ９００の概略図）に示すような、ＣＰＵ（Central Processing Unit）９０１と、メモリ９０２と、ＨＤＤ（Hard Disk Drive）等の外部記憶装置９０３と、ＣＤ−ＲＯＭ（Compact Disk Read Only Memory）やＤＶＤ−ＲＯＭ（Digital Versatile Disk Read Only Memory）等の可搬性を有する記憶媒体９０４に対して情報を読み書きする読書装置９０５と、キーボードやマウスなどの入力装置９０６と、ディスプレイなどの出力装置９０７と、通信ネットワークに接続するためのＮＩＣ（Network Interface Card）等の通信装置９０８と、を備えた一般的なコンピュータ９００で実現できる。
【００６３】
例えば、記憶部１１１は、ＣＰＵ９０１がメモリ９０２又は外部記憶装置９０３を利用することにより実現可能であり、制御部１１４は、外部記憶装置９０３に記憶されている所定のプログラムをメモリ９０２にロードしてＣＰＵ９０１で実行することで実現可能であり、入力部１１７は、ＣＰＵ９０１が入力装置９０６を利用することで実現可能であり、出力部１１８は、ＣＰＵ９０１が出力装置９０７を利用することで実現可能であり、通信部１１９は、ＣＰＵ９０１が通信装置９０８を利用することで実現可能である。
【００６４】
この所定のプログラムは、読書装置９０５を介して記憶媒体９０４から、あるいは、通信装置９０８を介してネットワークから、外部記憶装置９０３にダウンロードされ、それから、メモリ９０２上にロードされてＣＰＵ９０１により実行されるようにしてもよい。また、読書装置９０５を介して記憶媒体９０４から、あるいは、通信装置９０８を介してネットワークから、メモリ９０２上に直接ロードされ、ＣＰＵ９０１により実行されるようにしてもよい。
【００６５】
図４は、検証装置１３０の概略図である。
【００６６】
図示するように、検証装置１３０は、記憶部１３１と、制御部１３４と、入力部１３７と、出力部１３８と、通信部１３９と、を備える。
【００６７】
記憶部１３１は、検証鍵記憶領域１３２と、署名データ記憶領域１３３と、を備える。
【００６８】
検証鍵記憶領域１３２には、署名装置１１０から送信されてきた署名データに含まれている署名を復号化して検証するための鍵情報である検証鍵を特定する情報が記憶される。
【００６９】
署名データ記憶領域１３３には、署名装置１１０から送信されてきた署名データを特定する情報が記憶される。
【００７０】
制御部１３４は、署名一括検証処理部１３５と、数学関数計算部１３６と、を備える。
【００７１】
署名一括検証処理部１３５は、署名装置１１０から送信されてきた署名データを一括して検証する処理を制御する。
【００７２】
例えば、本実施形態においては、署名一括検証処理部１３５は、検証鍵記憶領域１３２に記憶されている検証鍵及び署名データ記憶領域１３３に記憶されている署名データを記憶部１３１から取得し、数学関数計算部１３６に入力する。
【００７３】
そして、署名一括検証処理部１３５は、数学関数計算部１３６から一括検証の結果を取得して、記憶部１３１に記憶するか、または、出力部１３８や通信部１３９を介して、検証結果を出力する。
【００７４】
数学関数計算部１３６は、署名一括検証部１３５から入力された署名データに含まれている署名に対して、署名一括検証部１３５から入力された検証鍵を用いて、予め定められたアルゴリズムによる署名の一括検証を施して、署名の有効性を確認する。
【００７５】
例えば、本実施形態においては、数学関数計算部１３６は、バッチインスタンス生成部１３６ａと、多重スカラー倍算計算部１３６ｂと、を備える。
【００７６】
バッチインスタンス生成部１３６ａは、署名一括検証部１３５から入力された署名データに含まれている署名から、バッチインスタンスを生成する。
【００７７】
ここで、バッチインスタンスの生成方法は、署名装置１１０及び検証装置１３０で使用する署名方式に依存する。なお、署名装置１１０及び検証装置１３０で使用する署名方式により生成された署名がバッチインスタンスとなっている場合には、数学関数計算部１３６にバッチインスタンス生成部１３６ａを設ける必要はない。
【００７８】
例えば、ＥＣＤＳＡ署名方式で生成された署名については、一括検証方式を適用できるように変形する必要があるため、数学関数計算部１３６のバッチインスタンス生成部１３６ａは、署名装置１１０から取得した署名をバッチインスタンスに変形する。
【００７９】
具体的には、数学関数計算部１３６のバッチインスタンス生成部１３６ａは、上述の（９）式で算出された署名Ｓｉを、上述の（１０）式、（１１）式及び（１２）式を用いて、下記の（１４）式に示すバッチインスタンスを算出する。
【００８０】
【数１４】
2010020189.tif 000016
【００８１】
多重スカラー倍算計算部１３６ｂは、多重スカラー倍計算処理を行う。
【００８２】
そして、多重スカラー倍算計算部１３６ｂは、下記の（１５）式を満たすかどうかで検証を行う。
【００８３】
【数１５】
2010020189.tif 000017
【００８４】
即ち、（１５）式を満たす場合は「有効」として署名Ｓｉを受け入れ、（１５）式を満たさない場合は「無効」として署名Ｓｉを拒否する。
【００８５】
ここで、Ｌｉ（ｉ＝１，・・・，ｕ）は、下記の（１６）式を満たす集合ＳＥＴからランダムに選択された数である。なお、集合ＳＥＴについては、下記の（１６）式を満たす。
【００８６】
【数１６】
2010020189.tif 000018
【００８７】
但し、＃Ｓは、集合ＳＥＴの要素数である。
【００８８】
多重スカラー倍算計算部１３６ｂが行う多重スカラー倍計算の概略は下記のとおりである。
【００８９】
まず、多重スカラー倍算計算部１３６ｂは、スカラー値を、ｘ２＋１＝０の根となる複素数λに対し、（０，±１，±λ）を係数とするFrobenius展開を施す。このFrobenius展開については、公知のものを用いればよいため詳細な説明は省略する。
【００９０】
次に、多重スカラー倍算計算部１３６ｂは、Frobenius展開された値を、λを係数とする値と、他の値と、の加算値に分解する。
【００９１】
例えば、Frobenius展開された値が（１，λ，０，−１，−λ）である場合、この値を（１，０，０，−１，０）＋（０，λ，０，０，−λ）という加算値に分解する。
【００９２】
そして、多重スカラー倍算計算部１３６ｂは、λを係数とする値において、λを共通因数としてくくることで、乗算回数を減らすことができる。
【００９３】
例えば、上述の加算値（１，０，０，−１，０）＋（０，λ，０，０，−λ）を（１，０，０，−１，０）＋λ（０，１，０，０，−１）として多重スカラー倍算を行う。
【００９４】
なお、多重スカラー倍計算における具体的な計算方法については、図８を用いて詳細に説明する。
【００９５】
入力部１１７は、情報の入力を受け付ける。
【００９６】
出力部１１８は、情報を出力する。
【００９７】
通信部１１９は、ネットワーク１５０を介して、情報の送受信を行う。
【００９８】
以上に記載した署名装置１３０も、例えば、図３に示すような一般的なコンピュータ９００で実現できる。
【００９９】
例えば、記憶部１３１は、ＣＰＵ９０１がメモリ９０２又は外部記憶装置９０３を利用することにより実現可能であり、制御部１３４は、外部記憶装置９０３に記憶されている所定のプログラムをメモリ９０２にロードしてＣＰＵ９０１で実行することで実現可能であり、入力部１３７は、ＣＰＵ９０１が入力装置９０６を利用することで実現可能であり、出力部１３８は、ＣＰＵ９０１が出力装置９０７を利用することで実現可能であり、通信部１３９は、ＣＰＵ９０１が通信装置９０８を利用することで実現可能である。
【０１００】
この所定のプログラムは、読書装置９０５を介して記憶媒体９０４から、あるいは、通信装置９０８を介してネットワークから、外部記憶装置９０３にダウンロードされ、それから、メモリ９０２上にロードされてＣＰＵ９０１により実行されるようにしてもよい。また、読書装置９０５を介して記憶媒体９０４から、あるいは、通信装置９０８を介してネットワークから、メモリ９０２上に直接ロードされ、ＣＰＵ９０１により実行されるようにしてもよい。
【０１０１】
図５は、署名装置１１０における署名生成処理を示すシーケンス図である。
【０１０２】
まず、署名装置１１０の署名生成処理部１１５は、入力部１１７を介して入力された、または、記憶部１１１のデータ記憶領域１１３に記憶されているメッセージＭを取得する（Ｓ１０）。ここで、メッセージＭは、デジタル化されたデータであればよく、テキスト、画像、映像、音等の種類は問わない。
【０１０３】
次に、署名生成処理部１１５は、取得したメッセージＭから入力データＨ（Ｍ）を生成する（Ｓ１１）。入力データＨ（Ｍ）は、例えば、メッセージＭのハッシュ値等で、メッセージＭや使用する署名方式に依存するものである。
【０１０４】
次に、署名生成処理部１１５は、記憶部１１１の署名鍵記憶領域１１２に記憶されている署名鍵ｓｋを読み出す（Ｓ１２）。
【０１０５】
そして、署名生成処理部１１５は、読み出した署名鍵ｓｋ及びステップＳ１１で生成した入力データＨ（Ｍ）を数学関数計算部１１６に入力する（Ｓ１３）。
【０１０６】
数学関数計算部１１６は、入力された署名鍵ｓｋと入力データＨ（Ｍ）とから、署名Ｓを計算する（Ｓ１４）。ここで、署名Ｓは、採用する署名方式に依存して計算される値である。
【０１０７】
そして、数学関数計算部１１６は、計算した署名Ｓを署名生成処理部１１５に出力する（Ｓ１５）。
【０１０８】
署名生成処理部１１５は、受け取った署名Ｓと、メッセージＭと、を少なくとも含む署名データを生成して、通信部１１９を介して検証装置１３０に送信する（Ｓ１６）。
【０１０９】
なお、ステップＳ１２において記憶部１１１からの署名鍵ｓｋの取得タイミングについては、数学関数計算部１１６へ署名鍵ｓｋを出力する前であればよく、例えば、メッセージＭを取得する（Ｓ１０）前であってもよい。
【０１１０】
図６は、検証装置１３０における署名の一括検証処理を示すシーケンス図である。
【０１１１】
まず、検証装置１３０の署名一括検証処理部１３５は、入力部１３７又は通信部１３９を介して入力された、または、記憶部１３１の署名データ記憶領域１３３に記憶されている署名データを任意の個数取得する（Ｓ２０）。
【０１１２】
また、署名一括検証処理部１３５は、記憶部１３１の検証鍵記憶領域１３２に記憶されている検証鍵ｐｋを読み出す（Ｓ２１）。
【０１１３】
そして、署名一括検証処理部１３５は、取得した複数の署名データ及び読み出した検証鍵ｐｋを数学関数計算部１３６に入力する（Ｓ２２）。
【０１１４】
数学関数計算部１３６では、入力された複数の署名データに含まれる署名ＳからバッチインスタンスＳ’を生成する（Ｓ２３）。なお、署名Ｓが既にバッチインスタンスとなっている場合には、バッチインスタンスを生成する必要はない。
【０１１５】
そして、数学関数計算部１３６は、入力された検証鍵ｐｋとバッチインスタンスＳ’とから、予め定められた一括検証を行い（Ｓ２４）、その結果を検証結果として署名一括検証処理部１３５に出力する（Ｓ２５）。なお、数学関数計算部１３６での署名の一括検証処理については、後述する図７を用いて詳述する。
【０１１６】
このような検証結果を取得した署名一括検証処理部１３５は、記憶部１３１に記憶するか、または、出力部１３８や通信部１３９を介して、検証結果（署名データが有効か否か）を出力する（Ｓ２６）。
【０１１７】
なお、記憶部１３１からの検証鍵ｐｋの読み出し（Ｓ２１）については、数学関数計算部１３６で一括検証を行う前であればよく、例えば、ステップＳ２０において署名データを受け取る前であってもよい。
【０１１８】
図７は、本実施形態における数学関数計算部１３６での一括検証処理を示すフローチャートである。
【０１１９】
まず、数学関数計算部１３６は、メッセージＭｉ（ｉ＝１，・・・，ｕ）、バッチインスタンスＳｉ’＝（Ｒｉ、σｉ）（ｉ＝１，・・・，ｕ）、公開鍵Ｑ、楕円曲線補助情報ξ、および、セキュリティパラメータｍの入力を受け付ける（Ｓ３０）。ここで、楕円曲線補助情報ξとは、後述するように楕円曲線上の自己同型写像等である。
【０１２０】
次に、数学関数計算部１３６は、すべてのｉ（ｉ＝１，・・・，ｕ）に対して、下記の（１７）式及び（１８）式が成り立つか否かを判定する（Ｓ３１）。ここで、ｒｉは、上述の（１１）式を満たす。
【０１２１】
【数１７】
2010020189.tif 000019
【０１２２】
【数１８】
2010020189.tif 000020
【０１２３】
すべてのｉに対して、（１７）式及び（１８）式が成り立つ場合には（ステップＳ３１でＹｅｓ）、ステップＳ３２に進み、成り立たない場合には（ステップＳ３１でＮｏ）、ステップＳ３６に進む。
【０１２４】
次に、数学関数計算部１３６は、各ｉに対して、メッセージＭｉのハッシュ値Ｈ（Ｍｉ）を計算し、その結果をｍｉに代入する（Ｓ３２）。
【０１２５】
そして、数学関数計算部１３６は、集合ＳＥＴからＬｉ（ｉ＝１，・・・，ｕ）をランダムに選択する（Ｓ３３）。
【０１２６】
そして、数学関数計算部１３６は、下記（１９）式が成り立つか否かを判定する（Ｓ３４）。
【０１２７】
【数１９】
2010020189.tif 000021
【０１２８】
そして、（１９）式が成り立つ場合には（ステップＳ３４でＹｅｓ）、ステップＳ３５に進み、（１９）式が成り立たない場合には（ステップＳ３４でＮｏ）、ステップＳ３６に進む。
【０１２９】
ステップＳ３５では、数学関数計算部１３６は、入力された署名が有効であると判定する。
【０１３０】
ステップＳ３６では、数学関数計算部１３６は、入力された署名が無効であると判定する。
【０１３１】
次に、本実施形態における多重すらカー倍算の概要を説明する。
【０１３２】
ここで、本実施形態においては、Ｅａは、下記の（２０）式に示すように、有限体Ｆ５上において定義された楕円曲線である。
【０１３３】
【数２０】
2010020189.tif 000022
【０１３４】
また、λは、下記の（２１）式に示すような楕円曲線Ｅａ上の自己同型写像である。
【０１３５】
【数２１】
2010020189.tif 000023
【０１３６】
ただし、αは位数４であるような有限体Ｆ５の元である
図８は、上述した（１９）式における多重スカラー倍算の計算処理を示すフローチャートである。
【０１３７】
まず、検証装置１３０の制御部１３４の数学関数計算部１３６の多重スカラー倍算計算部１３６ｂは、楕円曲線Ｅａ上の点Ｐ、Ｑ（Ｑ＝ｄＰ、ｄ：秘密鍵）、Ｒｉ（ｉ＝１，・・・，ｕ）、スカラー値ｗｉ、ｚｉ、下記の（２２）式に示す乱数ｔｉ、下記の（２３）式に示す乱数ｔｉｊ、および、楕円曲線Ｅａ上の自己同型写像λの入力を受け付ける（Ｓ４０）。
【０１３８】
【数２２】
2010020189.tif 000024
【０１３９】
【数２３】
2010020189.tif 000025
【０１４０】
ここで、スカラー値ｗｉ，ｚｉは、それぞれ、（１９）式の右辺のＰの係数Ｌｉσｉ−１ｍｉ、（１９）式の右辺のＱの係数Ｌｉσｉ−１ｒｉを表す。
【０１４１】
また、集合ＳＧ（ｅ，ｋ，ｑ）は、下記の（２４）式に示されているように、集合ＤＧの元を係数とするｅ桁以下のFrobenius展開であって、そのHamming Weightがｋ以下の元全体の集合を表している。
【０１４２】
【数２４】
2010020189.tif 000026
【０１４３】
なお、図７のステップＳ３３における集合ＳＥＴは、ここでは、ＳＧ（ｅ，ｋ，ｑ）を表している。
【０１４４】
また、上述のＤＧのように、展開の桁となる元全体の集合は桁集合(digit set)と呼ばれる。
【０１４５】
ここで、上述の乱数ｔｉを、下記の（２５）式に示すように変形する方法について説明する。
【０１４６】
【数２５】
2010020189.tif 000027
【０１４７】
まず、楕円曲線Ｅ上の点に対して、Frobenius写像φと呼ばれる自己準同型写像を施すことが可能である。点（ｘ１，ｙ１）に対してFrobenius写像φを施すとは、下記の（２６）式を計算することである。
【０１４８】
【数２６】
2010020189.tif 000028
【０１４９】
また、下記の（２７）式が成り立つことが知られており、下記の（２８）式の性質により、φを（２８）式を満たす複素数と考えることができる。
【０１５０】
【数２７】
2010020189.tif 000029
【０１５１】
【数２８】
2010020189.tif 000030
【０１５２】
ここで、ｔは楕円曲線Ｅのトレースと呼ばれる整数である。上述のFrobenius写像φのみならず、すべての自己準同型写像は、ある複素数と考えることができることが知られている。
【０１５３】
本実施形態においては、（２０）式の楕円曲線Ｅａにおいて、λの値は、下記の（２９）式に示すとおりである。
【０１５４】
【数２９】
2010020189.tif 000031
【０１５５】
（２０）式の楕円曲線Ｅａにおいて、ａ＝１のとき、（２８）式のｔは、ｔ＝２であることが知られており、さらにFrobenius写像φは（３０）式に示される複素数とみなすことができ、φとλの関係式は（３１）式に示される。
【０１５６】
【数３０】
2010020189.tif 000032
【０１５７】
【数３１】
2010020189.tif 000033
【０１５８】
この関係式を使うと、ｔｉ＝１２の場合は、（３２）式のように変形することによって、上述の乱数ｔｉの変形が可能となる。
【０１５９】
【数３２】
2010020189.tif 000034
【０１６０】
一般のａに対して上述のような変換を行う場合にも、（３１）式と類似するφとλの関係式を用いつつ、Frobenius展開を行えばよい。上記変換の詳細については下記の文献４に記載されている。
【０１６１】
文献４：T. J. Park, M. K. Lee, and K. Park, "New Frobenius Expansions for Elliptic Curves with Efficient Endomorphisms, " International Conference on Information Security and Cryptology − ICISC 2002, LNCS 2587, Springer-Verlag, pp.264-282, 2003.
図８のフローチャートに戻り、多重スカラー倍算計算部１３６ｂは、上述の（１９）式の右辺の二重スカラー倍算を計算し、その結果をＧに代入する（Ｓ４１）。
【０１６２】
次に、多重スカラー倍算計算部１３６ｂは、ｉに１を、ｊにｅ−１を、Ａに無限遠点０を、Ｂに無限遠点０を、それぞれ代入する（Ｓ４２）。
【０１６３】
次に、多重スカラー倍算計算部１３６ｂは、ｉ≦ｕであるか否かを判定する（Ｓ４３）。
【０１６４】
そして、ｉ≦ｕが成立する場合には（ステップＳ４３でＹｅｓ）、ステップＳ４４に進み、ｉ≦ｕが成立しない場合には（ステップＳ４３でＮｏ）、ステップＳ４９に進む。
【０１６５】
ステップＳ４４では、多重スカラー倍算計算部１３６ｂは、ｊ≧０であるか否かを判定する。
【０１６６】
そして、ｊ≧０が成立する場合には（ステップＳ４４でＹｅｓ）、ステップＳ４５に進み、ｊ≧０が成立しない場合には（ステップＳ４４でＮｏ）、ステップＳ４８に進む。
【０１６７】
ステップＳ４５では、多重スカラー倍算計算部１３６ｂは、Ｂにφ（Ｂ）を代入する。
【０１６８】
そして、多重スカラー倍算計算部１３６ｂは、もし、ｔｉｊ＝±１であるならば、ＢにＢ±Ｒｉを代入する（Ｓ４６）。なお、ｔｉｊ＝±１が成立しない場合には、ステップＳ４６は、スキップする。
【０１６９】
次に、多重スカラー倍算計算部１３６ｂは、ｊにｊ−１を代入し（Ｓ４７）、ステップＳ４４に戻り処理を繰り返す。
【０１７０】
一方、ステップＳ４４において、ｊ≧０が成立しない場合には（ステップＳ４４でＮｏ）、多重スカラー倍算計算部１３６ｂは、ｉにｉ＋１を、ｊにｅ−１を、ＡにＡ＋Ｂを、Ｂに無限遠点０を、それぞれ代入し（Ｓ４８）、ステップＳ４３に戻り処理を繰り返す。
【０１７１】
また、ステップＳ４３において、ｉ≦ｕが成立しない場合には（ステップＳ４３でＮｏ）、多重スカラー倍算計算部１３６ｂは、ｉに１を代入する（Ｓ４９）。
【０１７２】
そして、多重スカラー倍算計算部１３６ｂは、ｉ≦ｕであるか否かを判定する（Ｓ５０）。
【０１７３】
そして、ｉ≦ｕが成立する場合には（ステップＳ５０でＹｅｓ）、ステップＳ５１に進み、ｉ≦ｕが成立しない場合には（ステップＳ５０でＮｏ）、ステップＳ５６に進む。
【０１７４】
ステップＳ５１では、多重スカラー倍算計算部１３６ｂは、ｊ≧０であるか否かを判定する。
【０１７５】
そして、ｊ≧０が成立する場合には（ステップＳ５１でＹｅｓ）、ステップＳ５２に進み、ｊ≧０が成立しない場合には（ステップＳ５１でＮｏ）、ステップＳ５５に進む。
【０１７６】
ステップＳ５２では、多重スカラー倍算計算部１３６ｂは、Ｂにφ（Ｂ）を代入する。
【０１７７】
そして、多重スカラー倍算計算部１３６ｂは、もし、ｔｉｊ＝±λであるならば、ＢにＢ±Ｒｉを代入する（Ｓ５３）。なお、ｔｉｊ＝±λが成立しない場合には、ステップＳ５３は、スキップする。
【０１７８】
次に、多重スカラー倍算計算部１３６ｂは、ｊにｊ−１を代入し（Ｓ５４）、ステップＳ５１に戻り処理を繰り返す。
【０１７９】
一方、ステップＳ５１において、ｊ≧０が成立しない場合には（ステップＳ５１でＮｏ）、多重スカラー倍算計算部１３６ｂは、ｉにｉ＋１を、ｊにｅ−１を、それぞれ代入し（Ｓ５５）、ステップＳ５０に戻り処理を繰り返す。
【０１８０】
また、ステップＳ５０において、ｉ≦ｕが成立しない場合には（ステップＳ５０でＮｏ）、多重スカラー倍算計算部１３６ｂは、Ｂにλ（Ｂ）を、ＡにＡ＋Ｂを代入し（Ｓ５６）、処理を終了する。
【０１８１】
なお、上述の多重スカラー倍算（（１９）式の左辺）の計算方法は、上述の図８の多重スカラー倍計算方法でもよいし、その他の方法で計算してもよい。
【０１８２】
上述した多重スカラー倍の計算方法が、非特許文献１、非特許文献２、および、非特許文献３と比較して、効率的である（中間値の更新回数を大幅に削減できる）理由は、以下のとおりである。
【０１８３】
非特許文献１、非特許文献２、および、非特許文献３に記載の署名一括検証の場合、符号付き２進展開、または、Frobenius展開の桁集合が大きいため、（桁集合の要素数）×（検証したい署名の個数）の回数だけ中間値を更新する必要がある。そのため、検証したい署名の個数が大きい場合は、中間値の更新回数が多くなり、結果として処理性能のボトルネックとなる。
【０１８４】
これに対し、本実施形態においては、（２０）式の楕円曲線Ｅａ、および、（２４）式のFrobenius展開を用いた場合、桁集合が小さく、上述の自己同型写像λは（２１）式に記載のとおり、乗算一回（α×ｙ）と符号変換一回（ｘ→−ｘ）で実施できる。
【０１８５】
符号変換一回の処理時間は乗算一回と比較して無視できるほど小さいため、上述の自己同型写像λは、実際には乗算一回の処理時間で計算可能である。
【０１８６】
さらに、自己同型写像は群の準同型性を満たすことから、下記の（３３）式に示すように、楕円曲線上の各点に写像λを施した点の和と、楕円曲線上の各点の和に対して写像λを施した点は等しいという性質を持っている。
【０１８７】
【数３３】
2010020189.tif 000035
【０１８８】
例えば、ｕ＝２、Ｌ１＝λ−Φ＋λΦ２、Ｌ１＝１＋λΦ２とすると、下記の（３４）式に示すようになる。
【０１８９】
【数３４】
2010020189.tif 000036
【０１９０】
これより、図８に記載の多重スカラー倍計算方法を用いた場合、中間値λＲ１、λＲ２を更新する必要はなく、係数が±λとなっている点をすべて加算し、最後に自己同型写像λを施せばよい。
【０１９１】
また、楕円曲線上の整数倍算も上述の群の準同型性を満たす。例えば、４Ｐ＋４Ｑ＝４（Ｐ＋Ｑ）の計算は、Ｐ＋Ｑを計算し、最後に４倍算を実施すればよい。
【０１９２】
しかしながら、上述の自己同型写像λとは異なり、一回の乗算で実施することはできず、複数回の乗算が必要となる。したがって、非特許文献１、非特許文献２、および、非特許文献３に記載の署名一括検証の場合は、（桁集合の要素数）×（検証したい署名の個数）の回数だけ中間値を更新する必要がある。これに対して、図８に記載の多重スカラー倍計算方法を用いた場合、非特許文献１、非特許文献２、および、非特許文献３と比較して、中間値の更新回数を大幅に削減できる。
【０１９３】
さらに、上述の中間値を事前に計算する方法を用いる場合、事前計算テーブル（桁集合の元をスカラー値とするスカラー倍点）を保持する記憶領域を大量に必要とするのに対し、図８に記載の多重スカラー倍計算方法を用いる場合は事前計算結果を保持する記憶領域が不要であり、使用するメモリ量の削減が可能となる。
【０１９４】
第一の実施形態に記載の署名一括検証が高い安全性を持つ理由は以下のとおりである。
【０１９５】
上述のとおり、一括検証のセキュリティレベルをｍに設定するには、集合Ｓの要素数＃Ｓが、（１６）式を満たさなければならないことが知られている。
【０１９６】
一般にFrobenius展開は、表現方法が異なっても、値としては同じものが存在することは容易にわかる（例えば、楕円曲線の特性多項式と呼ばれる（２８）式より、二つのFrobenius展開φ２＋ｑ、ｔφは、表現方法は異なるが、値としては同じものである）。つまり、集合ＳＥＴとして（ある桁集合に関する）Frobenius展開を用いる場合は、そのFrobenius展開の元の個数を正確に求める（もしくは、Frobenius展開の元の個数の上限と下限を求める）必要があり、これができなければ、一括検証のセキュリティレベルｍを正確に設定することはできない。そのため、集合ＳＥＴとしてFrobenius展開を用いる場合は、その元の個数を正確に求める（もしくは、Frobenius展開の元の個数の上限と下限を求める）ことができるような桁集合を用いることが望ましい。本実施形態に記載の集合ＳＧ（ｅ，ｋ，ｑ）は、そのFrobenius展開が一意であることを証明することができる。
【０１９７】
Frobenius展開が一意であることから、表現方法は異なり、かつ値としては同じとなることはない。さらに、ＳＧ（ｅ，ｋ，ｑ）の要素数＃ＳＧ（ｅ，ｋ，ｑ）が、下記の（３５）式を満たすことも確かめることができる。
【０１９８】
【数３５】
2010020189.tif 000037
ここで、ｅＣｉは組合せの個数を表す記号であり、異なるｅ個からｉ個を選択する場合の組合せの総数を表す。
【０１９９】
したがって、（３５）式の値が２ｍとなるように（ｅ，ｋ，ｑ）を定めればよい。具体的には、第一の実施形態では、ｑ＝５であり、ｅは使用する楕円曲線の安全性を示すビット長（１６０−ｂｉｔ、１９２−ｂｉｔ、２５６−ｂｉｔ等）が、５ｅと同程度になるように設定すればよい。そして、定まったｅとｑを（３５）式に代入し、２ｍと同程度になるようｋを決めればよい。
【０２００】
本実施形態では、ある署名者によって署名された複数の署名（または、バッチインスタンス）を一括検証する場合を説明したが、複数の署名者がそれぞれ署名した複数の署名（または、バッチインスタンス）を一括検証することも可能である。
【０２０１】
例えば、署名生成鍵ｓｋｉと署名検証鍵ｐｋｉの組（ｓｋｉ＝ｄｉ、ｐｋｉ＝Ｑｉ）（ここで、Ｑｉ＝ｄｉＰ）をもつ少なくとも一人以上のユーザＡｉ（１≦ｉ≦ｒ）がそれぞれ生成したバッチインスタンス（Ｒｉ（ｊ）、σｉ（ｊ））｛１≦ｉ≦ｒ、１≦ｊ≦ｎ（ｉ）｝に対する一括検証は、下記の（３６）式を満たすか否かで検証を行う。
【０２０２】
【数３６】
2010020189.tif 000038
【０２０３】
また、以上に記載した一括検証方式では、ＥＣＤＳＡ署名方式を利用したが、ＥＣＤＳＡ署名の代わりに、ＥＣＤＳＡ＊署名を利用することも可能である。
【０２０４】
ＥＣＤＳＡ＊署名では、上述の（１４）式で算出されるバッチインスタンスが署名となっているため（署名装置１１０で計算されるため）、検証装置１３０においてバッチインスタンスを生成する必要がなくなる。
【０２０５】
なお、ＥＣＤＳＡ＊署名は、下記の文献５に記載されており、その安全性はＥＣＤＳＡ署名と等価である。
【０２０６】
文献５：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.
本実施形態では、ＥＣＤＳＡ署名、および、ＥＣＤＳＡ＊署名に関する一括検証方法を説明したが、下記の文献６に記載のＳｃｈｎｏｒｒ署名を、楕円曲線上の離散対数問題に基づく署名方式に拡張した楕円Ｓｃｈｎｏｒｒ署名などへの適用が可能であることも知られている。
【０２０７】
文献６：C. P. Schnorr, "Efficient Signature Generation by Smart Cards", Journal of Cryptology 4(3), pp.161-174, 1991.
次に、第一の実施形態とは異なる楕円曲線を用いた署名一括検証を第二の実施形態として説明する。
【０２０８】
本発明の第二の実施形態である署名一括検証システムも第一の実施形態と同様に、署名装置１１０と、検証装置１３０と、を備え、これらの署名装置１１０及び検証装置１３０は、ネットワーク１５０を介して相互に情報の送受信を行うことができるようにされている。
【０２０９】
そして、署名装置１１０については、第一の実施形態と同様に構成される。
【０２１０】
また、検証装置１３０についても、第一の実施形態と同様に構成されるが、制御部１３４の数学関数計算部１３６での署名の一括検証処理が異なるため、以下、この異なる点に関連する事項について説明する。
【０２１１】
本実施形態の多重スカラー倍計算の概要は、以下のとおりである。
【０２１２】
第二の実施形態では、第一の実施形態で用いた楕円曲線とは異なる曲線を用いる。以下、本実施形態においてＥｂは、下記の（３７）式のように有限体Ｆ７上定義された楕円曲線である。
【０２１３】
【数３７】
2010020189.tif 000039
【０２１４】
ここで、ωは、下記の（３８）式で示される楕円曲線Ｅｂ上の自己同型写像である。
【０２１５】
【数３８】
2010020189.tif 000040
【０２１６】
但し、βは位数３であるような有限体Ｆ７の元である。
【０２１７】
そして、多重スカラー倍算計算部１３６ｂは、スカラー値を、ｘ２＋ｘ＋１＝０の根となる複素数ωに対し、（０，±１，±ω，±ω２）を係数とするFrobenius展開を施す。このFrobenius展開については、公知のものを用いればよいため詳細な説明は省略する。
【０２１８】
次に、多重スカラー倍算計算部１３６ｂは、Frobenius展開された値を、ωを係数とする値と、ω２を係数とする値と、他の値と、の加算値に分解する。
【０２１９】
例えば、Frobenius展開された値が（１，ω，０，−１，−ω２）である場合、この値を（１，０，０，−１，０）＋（０，ω，０，０，０）＋（０，０，０，０，−ω２）という加算値に分解する。
【０２２０】
そして、多重スカラー倍算計算部１３６ｂは、ω又はω２を係数とする値において、ω又はω２を共通因数としてくくることで、乗算回数を減らすことができる。
【０２２１】
例えば、上述の加算値（１，０，０，−１，０）＋（０，ω，０，０，０）＋（０，０，０，０，−ω２）を（１，０，０，−１，０）＋ω（０，１，０，０，０）＋ω２（０，０，０，０，−１）として多重スカラー倍算を行う。
【０２２２】
図９及び図１０は、上述した（１９）式における多重スカラー倍算の計算処理を示すフローチャートである。
【０２２３】
まず、検証装置１３０の制御部１３４の数学関数計算部１３６の多重スカラー倍算計算部１３６ｂは、楕円曲線Ｅｂ上の点Ｐ、Ｑ（Ｑ＝ｄＰ、ｄ：秘密鍵）、Ｒｉ（ｉ＝１，・・・，ｕ）、スカラー値ｗｉ、ｚｉ、下記の（３９）式に示す乱数ｔｉ、下記の（４０）式に示す乱数ｔｉｊ、および、楕円曲線Ｅｂ上の自己同型写像ωの入力を受け付ける（Ｓ６０）。
【０２２４】
【数３９】
2010020189.tif 000041
【０２２５】
【数４０】
2010020189.tif 000042
【０２２６】
ここで、スカラー値ｗｉ，ｚｉは、それぞれ、（１９）式の右辺のＰの係数Ｌｉσｉ−１ｍｉ、（１９）式の右辺のＱの係数Ｌｉσｉ−１ｒｉを表す。
【０２２７】
また、集合ＳＥ（ｅ，ｋ，ｑ）は、下記の（４１）式に示されているように、集合ＤＥの元を係数とするｅ桁以下のFrobenius展開であって、そのHamming Weightがｋ以下の元全体の集合を表している。
【０２２８】
【数４１】
2010020189.tif 000043
【０２２９】
なお、図７のステップＳ３３における集合ＳＥＴは、ここでは、ＳＥ（ｅ，ｋ，ｑ）を表している。
【０２３０】
ここで、上述の乱数ｔｉを、下記の（４２）式に示すように変形する方法について説明する。
【０２３１】
【数４２】
2010020189.tif 000044
【０２３２】
本実施形態においては、（３７）式の楕円曲線Ｅｂにおいて、ωの値は、下記の（４３）式に示すとおりである。
【０２３３】
【数４３】
2010020189.tif 000045
【０２３４】
（３７）式の楕円曲線Ｅｂにおいて、ｂ＝１のとき、（４３）式のｔは、ｔ＝５であることが知られており、さらにFrobenius写像φは（４４）式に示される複素数とみなすことができ、φとλの関係式は（４５）式に示される。
【０２３５】
【数４４】
2010020189.tif 000046
【０２３６】
【数４５】
2010020189.tif 000047
【０２３７】
この関係式を使うと、ｔｉ＝１６φ−１０の場合は、（４６）式のように変形することによって、上述の乱数ｔｉの変形が可能となる。
【０２３８】
【数４６】
2010020189.tif 000048
【０２３９】
一般のｂに対して上述のような変換を行う場合にも、（４５）式と類似するφとωの関係式を用いつつ、Frobenius展開を行えばよい。上記変換の詳細については上記の文献４に記載されている。
【０２４０】
図９のフローチャートに戻り、多重スカラー倍算計算部１３６ｂは、上述の（１９）式の右辺の二重スカラー倍算を計算し、その結果をＧに代入する（Ｓ６１）。
【０２４１】
次に、多重スカラー倍算計算部１３６ｂは、ｉに１を、ｊにｅ−１を、Ａに無限遠点０を、Ｂに無限遠点０を、それぞれ代入する（Ｓ６２）。
【０２４２】
次に、多重スカラー倍算計算部１３６ｂは、ｉ≦ｕであるか否かを判定する（Ｓ６３）。
【０２４３】
そして、ｉ≦ｕが成立する場合には（ステップＳ６３でＹｅｓ）、ステップＳ６４に進み、ｉ≦ｕが成立しない場合には（ステップＳ６３でＮｏ）、ステップＳ６９に進む。
【０２４４】
ステップＳ６４では、多重スカラー倍算計算部１３６ｂは、ｊ≧０であるか否かを判定する。
【０２４５】
そして、ｊ≧０が成立する場合には（ステップＳ６４でＹｅｓ）、ステップＳ６５に進み、ｊ≧０が成立しない場合には（ステップＳ６４でＮｏ）、ステップＳ６８に進む。
【０２４６】
ステップＳ６５では、多重スカラー倍算計算部１３６ｂは、Ｂにφ（Ｂ）を代入する。
【０２４７】
そして、多重スカラー倍算計算部１３６ｂは、もし、ｔｉｊ＝±１であるならば、ＢにＢ±Ｒｉを代入する（Ｓ６６）。なお、ｔｉｊ＝±１が成立しない場合には、ステップＳ６６は、スキップする。
【０２４８】
次に、多重スカラー倍算計算部１３６ｂは、ｊにｊ−１を代入し（Ｓ６７）、ステップＳ６４に戻り処理を繰り返す。
【０２４９】
一方、ステップＳ６４において、ｊ≧０が成立しない場合には（ステップＳ６４でＮｏ）、多重スカラー倍算計算部１３６ｂは、ｉにｉ＋１を、ｊにｅ−１を、ＡにＡ＋Ｂを、Ｂに無限遠点０を、それぞれ代入し（Ｓ６８）、ステップＳ６３に戻り処理を繰り返す。
【０２５０】
また、ステップＳ６３において、ｉ≦ｕが成立しない場合には（ステップＳ６３でＮｏ）、多重スカラー倍算計算部１３６ｂは、ｉに１を代入する（Ｓ６９）。
【０２５１】
そして、多重スカラー倍算計算部１３６ｂは、ｉ≦ｕであるか否かを判定する（Ｓ７０）。
【０２５２】
そして、ｉ≦ｕが成立する場合には（ステップＳ７０でＹｅｓ）、ステップＳ７１に進み、ｉ≦ｕが成立しない場合には（ステップＳ７０でＮｏ）、ステップＳ７６に進む。
【０２５３】
ステップＳ７１では、多重スカラー倍算計算部１３６ｂは、ｊ≧０であるか否かを判定する。
【０２５４】
そして、ｊ≧０が成立する場合には（ステップＳ７１でＹｅｓ）、ステップＳ７２に進み、ｊ≧０が成立しない場合には（ステップＳ７１でＮｏ）、ステップＳ７５に進む。
【０２５５】
ステップＳ７２では、多重スカラー倍算計算部１３６ｂは、Ｂにφ（Ｂ）を代入する。
【０２５６】
そして、多重スカラー倍算計算部１３６ｂは、もし、ｔｉｊ＝±ωであるならば、ＢにＢ±Ｒｉを代入する（Ｓ７３）。なお、ｔｉｊ＝±ωが成立しない場合には、ステップＳ７３は、スキップする。
【０２５７】
次に、多重スカラー倍算計算部１３６ｂは、ｊにｊ−１を代入し（Ｓ７４）、ステップＳ７１に戻り処理を繰り返す。
【０２５８】
一方、ステップＳ７１において、ｊ≧０が成立しない場合には（ステップＳ７１でＮｏ）、多重スカラー倍算計算部１３６ｂは、ｉにｉ＋１を、ｊにｅ−１を、それぞれ代入し（Ｓ７５）、ステップＳ７０に戻り処理を繰り返す。
【０２５９】
また、ステップＳ７０において、ｉ≦ｕが成立しない場合には（ステップＳ７０でＮｏ）、多重スカラー倍算計算部１３６ｂは、Ｂにω（Ｂ）を、ＡにＡ＋Ｂを、ｉに１を、Ｂに０を、代入し（Ｓ７６）、図１０のステップＳ７７に進む。
【０２６０】
ステップＳ７７では、多重スカラー倍算計算部１３６ｂは、ｉ≦ｕであるか否かを判定する。
【０２６１】
そして、ｉ≦ｕが成立する場合には（ステップＳ７７でＹｅｓ）、ステップＳ７８に進み、ｉ≦ｕが成立しない場合には（ステップＳ７７でＮｏ）、ステップＳ８３に進む。
【０２６２】
ステップＳ７８では、多重スカラー倍算計算部１３６ｂは、ｊ≧０であるか否かを判定する。
【０２６３】
そして、ｊ≧０が成立する場合には（ステップＳ７８でＹｅｓ）、ステップＳ７９に進み、ｊ≧０が成立しない場合には（ステップＳ７８でＮｏ）、ステップＳ８２に進む。
【０２６４】
ステップＳ７９では、多重スカラー倍算計算部１３６ｂは、Ｂにφ（Ｂ）を代入する。
【０２６５】
そして、多重スカラー倍算計算部１３６ｂは、もし、ｔｉｊ＝±ω２であるならば、ＢにＢ±Ｒｉを代入する（Ｓ８０）。なお、ｔｉｊ＝±ωが成立しない場合には、ステップＳ８０は、スキップする。
【０２６６】
次に、多重スカラー倍算計算部１３６ｂは、ｊにｊ−１を代入し（Ｓ８１）、ステップＳ７８に戻り処理を繰り返す。
【０２６７】
一方、ステップＳ７８において、ｊ≧０が成立しない場合には（ステップＳ７８でＮｏ）、多重スカラー倍算計算部１３６ｂは、ｉにｉ＋１を、ｊにｅ−１を、それぞれ代入し（Ｓ８２）、ステップＳ７７に戻り処理を繰り返す。
【０２６８】
また、ステップＳ７７において、ｉ≦ｕが成立しない場合には（ステップＳ７７でＮｏ）、多重スカラー倍算計算部１３６ｂは、Ｂにω２（Ｂ）を、ＡにＡ＋Ｂを、代入し（Ｓ８３）、処理を終了する。
【０２６９】
なお、上述の多重スカラー倍算の計算方法は、上述の図９及び図１０の多重スカラー倍計算方法でもよいし、その他の方法で計算してもよい。例えば、ωとω２を係数として有する部分をωで因数分解することで、ω２の乗算を避けるようにすることも可能である。
【０２７０】
第二の実施形態における多重スカラー倍計算方法が、非特許文献１、非特許文献２及び非特許文献３と比較して、中間値の更新回数を大幅に削減できる理由は第一の実施形態と同様である。
【０２７１】
また、中間値を事前に計算する方法を用いる場合、事前計算テーブル（桁集合の元をスカラー値とするスカラー倍点）を保持する記憶領域を大量に必要とするのに対し、第二の実施形態における多重スカラー倍計算方法を用いる場合は、事前計算結果を保持する記憶領域が不要であり、使用するメモリ量の削減が可能となることも第一の実施形態と同様である。
【０２７２】
第二の実施形態に記載の署名一括検証が高い安全性を持つ理由も第一の実施形態と同様である。すなわち集合ＳＥ（ｅ，ｋ，ｑ）は、そのFrobenius展開が一意であることを証明することができる。
【０２７３】
さらに、ＳＥ（ｅ，ｋ，ｑ）の要素数#ＳＥ（ｅ，ｋ，ｑ）が、下記の（４７）式を満たすことも確かめることができる。
【０２７４】
【数４７】
2010020189.tif 000049
【０２７５】
したがって、４７式の値が２ｍとなるように(ｅ，ｋ，ｑ)を定めればよい。具体的には、第二の実施形態では、ｑ＝７であり、ｅは使用する楕円曲線の安全性を示すビット長（１６０−ｂｉｔ、１９２−ｂｉｔ、２５６−ｂｉｔ等）が７ｅと同程度になるように設定すればよい。そして、定まったｅとｑを４７式に代入し、２ｍと同程度になるようｋを決めればよい。
【０２７６】
なお、上記各実施形態では、署名生成処理部１１５、署名一括検証処理部１３５を、ソフトウェアで実現するものとして説明したが、専用のハードウェアを用いて実現してもよい。また、数学関数計算部１１６、１３６を専用ハードウェアで実現しても良い。
【図面の簡単な説明】
【０２７７】
【図１】署名一括検証システムの概略図。
【図２】署名装置の概略図。
【図３】コンピュータの概略図。
【図４】検証装置の概略図。
【図５】署名装置における署名生成処理を示すシーケンス図。
【図６】検証装置における署名の一括検証処理を示すシーケンス図。
【図７】数学関数計算部での一括検証処理を示すフローチャート。
【図８】多重スカラー倍算の計算処理を示すフローチャート。
【図９】多重スカラー倍算の計算処理を示すフローチャート。
【図１０】多重スカラー倍算の計算処理を示すフローチャート。
【符号の説明】
【０２７８】
１００  署名一括検証システム
１１１  記憶部
１１２  署名鍵記憶領域
１１３  データ記憶領域
１１４  制御部
１１５  署名生成処理部
１１６  数学関数計算部
１１７  入力部
１１８  出力部
１１９  通信部
１３０  検証装置
１３１  記憶部
１３２  検証鍵記憶領域
１３３  署名データ記憶領域
１３４  制御部
１３５  署名一括検証処理部
１３６  数学関数計算部
１３７  入力部
１３８  出力部
１３９  通信部
【図１】
2010020189.tif 000050
【図２】
2010020189.tif 000051
【図３】
2010020189.tif 000052
【図４】
2010020189.tif 000053
【図５】
2010020189.tif 000054
【図６】
2010020189.tif 000055
【図７】
2010020189.tif 000056
【図８】
2010020189.tif 000057
【図９】
2010020189.tif 000058
【図１０】
2010020189.tif 000059