"あるノードから別のノードへの順序付きの多重署名を行う多重署名システムであって、各ノードには、所定の自然数からなる署名鍵と、第1のGDHGAP-Diffie-Hellmanグループに属する第1の値に対して当該署名鍵により演算を行って生成される当該第1のGDHグループに属する第1の検証鍵、及び第2のGDHグループに属する第2の値に対して当該署名鍵により演算を行って生成される当該第2のGDHグループに属する第2の検証鍵とがそれぞれ割り当てられており、当該各ノードは、署名対象であるメッセージに対して一方向性ハッシュ関数演算を行って、当該メッセージの前記第2のGDHグループに属するハッシュ値を生成する署名ノード一方向性ハッシュ関数演算部と、直後のノードが存在する場合、前記メッセージのハッシュ値に対して自身の署名鍵により演算を行って、自身の署名情報を生成する署名情報生成部と、前記直後のノードが存在する場合、自身の署名情報及び第1の検証鍵を、当該直後のノードへ送信する送信部と、直前のノードが存在する場合、当該直前のノードの署名情報及び第1の検証鍵を受信する受信部と、前記直前のノードが存在する場合、当該直前のノードの署名情報に対して自身の署名鍵により演算を行って、隣接するノード間の多重署名情報を生成する多重署名情報生成部と、前記直前のノードが存在する場合、当該直前のノードの第1の検証鍵に対して自身の署名鍵により演算を行って、隣接するノード間の多重検証鍵情報を生成する多重検証鍵情報生成部と、を備え、多重署名情報を公開する公開ノードは、前記隣接するノード間の多重署名情報の総和である公開多重署名情報、及び前記隣接するノード間の多重検証鍵情報の総和である公開多重検証鍵情報を公開する公開部を備える多重署名システム。前記受信部は、前記直前のノードが存在する場合、当該直前のノードまでで生成された多重署名情報の総和及び多重検証鍵情報の総和を、さらに受信し、前記送信部は、前記直後のノードが存在する場合、前記直後のノードへ、自身のノードまでで生成された多重署名情報の総和及び多重検証鍵情報の総和を、さらに送信する請求項1に記載の多重署名システム。前記公開部は、順序の始点であり直前のノードが存在しない始点ノードの署名情報を前記公開多重署名情報に加算し、当該始点ノードの第1の検証鍵を前記公開多重検証鍵情報に加算して公開する請求項1又は請求項2に記載の多重署名システム。前記公開部は、順序の終点であり直後のノードが存在しない終点ノードの署名情報を前記公開多重署名情報に加算し、当該終点ノードの第1の検証鍵を前記公開多重検証鍵情報に加算して公開する請求項1又は請求項2に記載の多重署名システム。前記公開部は、前記公開ノードの署名情報を前記公開多重署名情報に加算し、当該公開ノードの第1の検証鍵を前記公開多重検証鍵情報に加算して公開する請求項1又は請求項2に記載の多重署名システム。前記各ノードは、木構造に構成され、前記公開ノードは、前記木構造におけるルートノードである請求項5に記載の多重署名システム。前記各ノードは、メッシュ構造に構成され、前記公開ノードは、前記メッシュ構造に含まれない前記各ノードを統括するノードである請求項5に記載の多重署名システム。前記公開部は、前記各ノードの順序情報をさらに公開する請求項1から請求項7のいずれかに記載の多重署名システム。請求項1から請求項8のいずれかに記載の多重署名システムに備えられている前記公開部により公開された公開多重署名情報を検証する検証システムであって、前記公開多重署名情報が生成された過程の全てのノードの第1の検証鍵及び第2の検証鍵を収集する収集部と、前記メッセージに対して一方向性ハッシュ関数演算を行って、当該メッセージの前記第2のGDHグループに属するハッシュ値を生成する検証ノード一方向性ハッシュ関数演算部と、前記収集部により収集された前記全てのノードの第1の検証鍵及び第2の検証鍵、並びに前記第2の値に基づいて、前記公開多重検証鍵情報の正当性を検証する第1の検証部と、前記第1の検証部により正当性が検証された前記公開多重検証鍵情報、前記メッセージのハッシュ値及び前記第1の値に基づいて、前記公開多重署名情報の正当性を検証する第2の検証部と、を備える検証システム。あるノードから別のノードへの順序付きの多重署名を行う多重署名方法であって、各ノードには、所定の自然数からなる署名鍵と、第1のGDHGAP-Diffie-Hellmanグループに属する第1の値に対して当該署名鍵により演算を行って生成される当該第1のGDHグループに属する第1の検証鍵、及び第2のGDHグループに属する第2の値に対して当該署名鍵により演算を行って生成される当該第2のGDHグループに属する第2の検証鍵とがそれぞれ割り当てられており、当該各ノードが、署名対象であるメッセージに対して一方向性ハッシュ関数演算を行って、当該メッセージの前記第2のGDHグループに属するハッシュ値を生成する署名ノード一方向性ハッシュ関数演算工程と、直後のノードが存在する場合、前記メッセージのハッシュ値に対して自身の署名鍵により演算を行って、自身の署名情報を生成する署名情報生成工程と、前記直後のノードが存在する場合、自身の署名情報及び第1の検証鍵を、当該直後のノードへ送信する送信工程と、直前のノードが存在する場合、当該直前のノードの署名情報及び第1の検証鍵を受信する受信工程と、前記直前のノードが存在する場合、当該直前のノードの署名情報に対して自身の署名鍵により演算を行って、隣接するノード間の多重署名情報を生成する多重署名情報生成工程と、前記直前のノードが存在する場合、当該直前のノードの第1の検証鍵に対して自身の署名鍵により演算を行って、隣接するノード間の多重検証鍵情報を生成する多重検証鍵情報生成工程と、を実行し、多重署名情報を公開する公開ノードが、前記隣接するノード間の多重署名情報の総和である公開多重署名情報、及び前記隣接するノード間の多重検証鍵情報の総和である公開多重検証鍵情報を公開する公開工程を実行する多重署名方法。あるノードから別のノードへの順序付きの多重署名を行う多重署名方法をコンピュータに実行させるための多重署名プログラムであって、各ノードには、所定の自然数からなる署名鍵と、第1のGDHGAP-Diffie-Hellmanグループに属する第1の値に対して当該署名鍵により演算を行って生成される当該第1のGDHグループに属する第1の検証鍵、及び第2のGDHグループに属する第2の値に対して当該署名鍵により演算を行って生成される当該第2のGDHグループに属する第2の検証鍵とがそれぞれ割り当てられており、当該各ノードに、署名対象であるメッセージに対して一方向性ハッシュ関数演算を行って、当該メッセージの前記第2のGDHグループに属するハッシュ値を生成する署名ノード一方向性ハッシュ関数演算工程と、直後のノードが存在する場合、前記メッセージのハッシュ値に対して自身の署名鍵により演算を行って、自身の署名情報を生成する署名情報生成工程と、前記直後のノードが存在する場合、自身の署名情報及び第1の検証鍵を、当該直後のノードへ送信する送信工程と、直前のノードが存在する場合、当該直前のノードの署名情報及び第1の検証鍵を受信する受信工程と、前記直前のノードが存在する場合、当該直前のノードの署名情報に対して自身の署名鍵により演算を行って、隣接するノード間の多重署名情報を生成する多重署名情報生成工程と、前記直前のノードが存在する場合、当該直前のノードの第1の検証鍵に対して自身の署名鍵により演算を行って、隣接するノード間の多重検証鍵情報を生成する多重検証鍵情報生成工程と、を実行させ、多重署名情報を公開する公開ノードに、前記隣接するノード間の多重署名情報の総和である公開多重署名情報、及び前記隣接するノード間の多重検証鍵情報の総和である公開多重検証鍵情報を公開する公開工程を実行させるための多重署名プログラム。しかしながら、これらの多重署名やグループ署名では署名者が全て等価な関係で表現される。したがって、一例として示した多重署名システムにおいて電子データがどのように流通してきたのかを、この署名方式だけで表現することができない。これに対し、順序や上下関係を証明する方式としては順序付き多重署名方式例えば、特許文献2、3を参照があげられる。これにより署名者の順番が保証され、個人の上下関係が表現できる。しかしながら、これら既存の順序付き多重署名方式は、RSARivestShamirAdleman問題ベースのものか、離散対数問題ベースのものが提案されている。RSA問題ベースでは、署名する人数が増えるほど署名サイズが大きくなってしまい、また、離散対数問題ベースでは、ゼロ知識証明を利用するために演算処理に負荷がかかり、効率的な処理にならない。本発明は、上記課題を解決するため、署名する人数が増えても署名サイズを一定値に抑制し、かつ効率的な演算処理によって順序付き電子署名を行うことができる多重署名システム、検証システム、多重署名方法及び多重署名プログラムを提供することを目的とする。本発明では、以下のような解決手段を提供する。1本発明に係る多重署名システムは、あるノードから別のノードへの順序付きの多重署名を行う多重署名システムであって、各ノードには、所定の自然数からなる署名鍵と、第1のGDHGAP-Diffie-Hellmanグループに属する第1の値に対して当該署名鍵により演算を行って生成される当該第1のGDHグループに属する第1の検証鍵、及び第2のGDHグループに属する第2の値に対して当該署名鍵により演算を行って生成される当該第2のGDHグループに属する第2の検証鍵とがそれぞれ割り当てられており、当該各ノードは、署名対象であるメッセージに対して一方向性ハッシュ関数演算を行って、当該メッセージの前記第2のGDHグループに属するハッシュ値を生成する署名ノード一方向性ハッシュ関数演算部と、直後のノードが存在する場合、前記メッセージのハッシュ値に対して自身の署名鍵により演算を行って、自身の署名情報を生成する署名情報生成部と、前記直後のノードが存在する場合、自身の署名情報及び第1の検証鍵を、当該直後のノードへ送信する送信部と、直前のノードが存在する場合、当該直前のノードの署名情報及び第1の検証鍵を受信する受信部と、前記直前のノードが存在する場合、当該直前のノードの署名情報に対して自身の署名鍵により演算を行って、隣接するノード間の多重署名情報を生成する多重署名情報生成部と、前記直前のノードが存在する場合、当該直前のノードの第1の検証鍵に対して自身の署名鍵により演算を行って、隣接するノード間の多重検証鍵情報を生成する多重検証鍵情報生成部と、を備え、多重署名情報を公開する公開ノードは、前記隣接するノード間の多重署名情報の総和である公開多重署名情報、及び前記隣接するノード間の多重検証鍵情報の総和である公開多重検証鍵情報を公開する公開部を備える。このような構成によれば、多重署名システムは、隣接するノード間で署名鍵の積を用いてGDHグループ内の演算により多重署名情報及び多重検証鍵情報を生成し、これらの総和である公開多重署名情報及び公開多重検証鍵情報を公開する。多重署名システムは、この公開多重署名情報及び公開多重検証鍵情報により、ノード間の隣接関係を表現することができる。また、このように構成されることにより、多重署名システムは、署名鍵を知らない第三者がGDHグループの要素である楕円曲線上の点から署名鍵を求めることを、計算量的に困難にすることができる。また、署名者の数ノードの数が増えても、生成される署名情報は楕円曲線上の点であるため、署名情報のサイズ容量は増大せず一定値以下に抑制することができ、効率的に多重署名を生成することができる。2また、上記多重署名システムでは、前記受信部は、前記直前のノードが存在する場合、当該直前のノードまでで生成された多重署名情報の総和及び多重検証鍵情報の総和を、さらに受信し、前記送信部は、前記直後のノードが存在する場合、前記直後のノードへ、自身のノードまでで生成された多重署名情報の総和及び多重検証鍵情報の総和を、さらに送信することを特徴とする。このような構成によれば、多重署名システムは、各ノードにおいて、自身のノードに至るまでの多重署名情報の総和が得られる。したがって、多重署名システムは、公開ノードにおける処理負荷を低減し、また、各ノードに至るまでの経路を保証する多重署名を生成できる。3また、上記多重署名システムでは、前記公開部は、順序の始点であり直前のノードが存在しない始点ノードの署名情報を前記公開多重署名情報に加算し、当該始点ノードの第1の検証鍵を前記公開多重検証鍵情報に加算して公開することを特徴とする。このような構成によれば、多重署名システムは、始点ノードの署名情報により、経路の始点を示すので、公開多重署名情報及び公開多重検証鍵情報により、始点ノードから終点ノードに至るまでの署名順序を表現できる。4また、上記多重署名システムでは、前記公開部は、順序の終点であり直後のノードが存在しない終点ノードの署名情報を前記公開多重署名情報に加算し、当該終点ノードの第1の検証鍵を前記公開多重検証鍵情報に加算して公開することを特徴とする。このような構成によれば、多重署名システムは、終点ノードの署名情報により、経路の終点を示すので、公開多重署名情報及び公開多重検証鍵情報により、始点ノードから終点ノードに至るまでの署名順序を表現できる。5また、上記多重署名システムでは、前記公開部は、前記公開ノードの署名情報を前記公開多重署名情報に加算し、当該公開ノードの第1の検証鍵を前記公開多重検証鍵情報に加算して公開することを特徴とする。このような構成によれば、多重署名システムは、公開ノードの署名情報により、署名経路内又は経路外の公開ノードを示すので、公開多重署名情報及び公開多重検証鍵情報により、公開ノードの配置を表現できる。6また、上記多重署名システムでは、前記各ノードは、木構造に構成され、前記公開ノードは、前記木構造におけるルートノードであることを特徴とする。このような構成によれば、多重署名システムは、隣接するノードが多対1の関係にある木構造において、隣接関係及びルートノードの配置により署名順序を表現できる。7また、上記多重署名システムでは、前記各ノードは、メッシュ構造に構成され、前記公開ノードは、前記メッシュ構造に含まれない前記各ノードを統括するノードであることを特徴とする。このような構成によれば、多重署名システムは、隣接するノードが多対多の関係にあるメッシュ構造において、その隣接関係及び公開ノードの配置を表現できる。8また、上記多重署名システムでは、前記公開部は、前記各ノードの順序情報をさらに公開することを特徴とする。このような構成によれば、多重署名システムは、署名情報と共に、この署名情報が生成されるまでの過程で署名が行われたノードの順序を公開できる。9また、本発明に係る検証システムは、上記多重署名システムに備えられている前記公開部により公開された公開多重署名情報を検証する検証システムであって、前記公開多重署名情報が生成された過程の全てのノードの第1の検証鍵及び第2の検証鍵を収集する収集部と、前記メッセージに対して一方向性ハッシュ関数演算を行って、当該メッセージの前記第2のGDHグループに属するハッシュ値を生成する検証ノード一方向性ハッシュ関数演算部と、前記収集部により収集された前記全てのノードの第1の検証鍵及び第2の検証鍵、並びに前記第2の値に基づいて、前記公開多重検証鍵情報の正当性を検証する第1の検証部と、前記第1の検証部により正当性が検証された前記公開多重検証鍵情報、前記メッセージのハッシュ値及び前記第1の値に基づいて、前記公開多重署名情報の正当性を検証する第2の検証部と、を備える。このような構成によれば、検証システムは、全てのノードの検証鍵を用いて、公開された署名情報の正当性を検証する。よって、検証システムでは、各ノードにて生成される個々の署名情報等を検証することなく、公開された署名情報を検証することにより、署名順序を証明することができる。すなわち、検証システムでは、検証ノードの処理負荷を低減して検証作業を実行することができる。10本発明に係る多重署名方法は、あるノードから別のノードへの順序付きの多重署名を行う多重署名方法であって、各ノードには、所定の自然数からなる署名鍵と、第1のGDHGAP-Diffie-Hellmanグループに属する第1の値に対して当該署名鍵により演算を行って生成される当該第1のGDHグループに属する第1の検証鍵、及び第2のGDHグループに属する第2の値に対して当該署名鍵により演算を行って生成される当該第2のGDHグループに属する第2の検証鍵とがそれぞれ割り当てられており、当該各ノードが、署名対象であるメッセージに対して一方向性ハッシュ関数演算を行って、当該メッセージの前記第2のGDHグループに属するハッシュ値を生成する署名ノード一方向性ハッシュ関数演算工程と、直後のノードが存在する場合、前記メッセージのハッシュ値に対して自身の署名鍵により演算を行って、自身の署名情報を生成する署名情報生成工程と、前記直後のノードが存在する場合、自身の署名情報及び第1の検証鍵を、当該直後のノードへ送信する送信工程と、直前のノードが存在する場合、当該直前のノードの署名情報及び第1の検証鍵を受信する受信工程と、前記直前のノードが存在する場合、当該直前のノードの署名情報に対して自身の署名鍵により演算を行って、隣接するノード間の多重署名情報を生成する多重署名情報生成工程と、前記直前のノードが存在する場合、当該直前のノードの第1の検証鍵に対して自身の署名鍵により演算を行って、隣接するノード間の多重検証鍵情報を生成する多重検証鍵情報生成工程と、を実行し、多重署名情報を公開する公開ノードが、前記隣接するノード間の多重署名情報の総和である公開多重署名情報、及び前記隣接するノード間の多重検証鍵情報の総和である公開多重検証鍵情報を公開する公開工程を実行する。11本発明に係る多重署名プログラムは、あるノードから別のノードへの順序付きの多重署名を行う多重署名方法をコンピュータに実行させるための多重署名プログラムであって、各ノードには、所定の自然数からなる署名鍵と、第1のGDHGAP-Diffie-Hellmanグループに属する第1の値に対して当該署名鍵により演算を行って生成される当該第1のGDHグループに属する第1の検証鍵、及び第2のGDHグループに属する第2の値に対して当該署名鍵により演算を行って生成される当該第2のGDHグループに属する第2の検証鍵とがそれぞれ割り当てられており、当該各ノードに、署名対象であるメッセージに対して一方向性ハッシュ関数演算を行って、当該メッセージの前記第2のGDHグループに属するハッシュ値を生成する署名ノード一方向性ハッシュ関数演算工程と、直後のノードが存在する場合、前記メッセージのハッシュ値に対して自身の署名鍵により演算を行って、自身の署名情報を生成する署名情報生成工程と、前記直後のノードが存在する場合、自身の署名情報及び第1の検証鍵を、当該直後のノードへ送信する送信工程と、直前のノードが存在する場合、当該直前のノードの署名情報及び第1の検証鍵を受信する受信工程と、前記直前のノードが存在する場合、当該直前のノードの署名情報に対して自身の署名鍵により演算を行って、隣接するノード間の多重署名情報を生成する多重署名情報生成工程と、前記直前のノードが存在する場合、当該直前のノードの第1の検証鍵に対して自身の署名鍵により演算を行って、隣接するノード間の多重検証鍵情報を生成する多重検証鍵情報生成工程と、を実行させ、多重署名情報を公開する公開ノードに、前記隣接するノード間の多重署名情報の総和である公開多重署名情報、及び前記隣接するノード間の多重検証鍵情報の総和である公開多重検証鍵情報を公開する公開工程を実行させるための多重署名プログラム。本発明によれば、署名する人数が増えても署名サイズを一定値に抑制し、かつ効率的な演算処理によって順序付き多重署名を行うことができる。<第1実施形態>以下、本発明の実施形態の一例である第1実施形態について説明する。本実施形態に係る多重署名システムは、複数のノードが一列に構成され、署名対象である電子データメッセージに対して、順序の始点であり直前のノードが存在しない始点ノードから順序の終点であり直後のノードが存在しない終点ノードへ順に、順序付きの多重署名を行うシステムである。また、終点ノードにより公開された公開順序付き多重署名情報は、検証システムにおける検証ノードにより正当性が検証される。ところで、各ノードには、予め重複しない署名鍵と検証鍵とが認証局CAによってそれぞれ割り当てられている。署名鍵は、所定の自然数xからなる。検証鍵は、第1の検証鍵及び第2の検証鍵からなる。第1の検証鍵v1は、第1のGDHGAP-Diffie-HellmanグループG1の要素である楕円曲線上の点g1と固有署名鍵xとに基づいて生成される楕円曲線上の点v1=xg1からなる。また、第2の検証鍵v2は、第2のGDHGAP-Diffie-HellmanグループG2の要素である楕円曲線上の点g2と固有署名鍵xとに基づいて生成される楕円曲線上の点v2=xg2からなる。このように構成されることにより、署名鍵xを知らない第三者がv1、v2、g1、g2等の値から署名鍵xを求めることは計算量的に困難となる。ここで、本実施形態で採用される具体的な署名方式について説明する。多重署名システムでは、ベースとなる署名方式としてGAP-Diffie-HellmanGDH署名を採用する。GDH署名とは、Decision-Diffie-HellmanDDH問題をペアリングと呼ばれるある種のブラックボックス関数eP,Qを用いることで、解くことが可能であることを利用した署名である。次に、ペアリング演算を用いたGDH署名について説明する。楕円曲線上のDiffie-Hellman問題に関連して、GDHグループが定義されている。GDHグループについて簡単に説明する。G1及びG2をそれぞれ異なる楕円曲線上の点の集合とする。g1を集合G1の、g2を集合G2の要素としたとき、楕円曲線上のDecisionalDiffie-HellmanDDH問題とComputationalDiffie-HellmanCDH問題が以下のように定義される。DDH問題:あるa、b、cという自然数があり、gx、agx、bgx、cgxxは1及び2が与えられた時、c=abかどうかを判定する問題。CDH問題:あるa、b、cという自然数があり、gx、agx、bgxが与えられた時、abgyを計算する問題xは1及び2、yは1又は2。このとき、DDH問題は、計算量的に簡単であるが、CDH問題は、計算量的に難問である場合、この集合GxをGDHグループと定義する。これに対し、ある楕円曲線上の点をP,Qとし、そのP,Qによっては次にあげる性質を持つことができるペアリングと呼ばれるブラックボックス関数eP,Qを定義できるものが存在する。eP,Q1Q2=eP,Q1eP,Q21eP1P2,Q=eP1,QeP2,Q2eaP,bQ=ebP,aQ=eabP,Q=eP,abQ=eP,Qab3よって、gxがペアリング演算の可能な楕円曲線上の点である場合には、上記の性質から、3式にgx、agx、bgx、cgxを入力すると、例えば、eag1,bg2=eg1,g2ab4eg1,cg2=eg1,g2c5となる。したがって、両者の値が一致するかどうかにより、ab=cであるかどうかを判定でき、g1及びg2は、GDHグループG1又はG2の要素となりうる。この性質を利用してGDH署名が構成される。集合G1及びG2は、GDHグループであり、g1及びg2は、それぞれ集合G1及びG2の要素となる点とする。また、一方向性ハッシュ関数H2を、通常使用される任意のビット長のサイズの数値データが固定のビット長のサイズの数値データに写像変換される方式とは異なり、H2:{0,1}→G2のように、任意のビット長のサイズの数値データを楕円曲線上の点として表現されるGDHグループG2の要素に写像変換する方式であると定義する。このとき、GDH署名は以下のように定義される。鍵生成:自然数xを選び、g1からv=xg1を計算する。xを署名鍵、楕円曲線上の点vを検証鍵とする。署名:署名者は、メッセージm∈{0,1}に対しh=H2mを計算し、さらに自分の署名鍵を用いてσ=xhを計算する。σをmに対する署名として公開する。検証:検証者は、メッセージmからh=H2mを計算し、集合G1に属するg1及びvと、集合G2に属するh及びσを準備する。eg1,σとev,hを計算し、両者の値が一致したら、署名σは、正しい署名と判定する。このとき、hの値は集合G2の要素となるので、ある自然数yを用いてh=yg2と表現できる。その結果、正しく署名が行われていればg1,v,h,σ=g1,xg1,yg2,xyg2となる。したがって、正当な署名であれば上記の検証でのペアリング演算は、eg1,σ=eg1,xyg2=eg1,g2xy=exg1,yg2=ev,hとなり、値が一致することから、検証可能となる。なお、GDHグループの条件であるCDH問題の困難性から、署名鍵xを知らない第三者がg1、g2、v、hの値から署名σを導出することは不可能である。以下、集合G1に属する値には添字1を付し、集合G2に属する値には添字2を付して表現する。例えば、集合G1に属する第1の値上記g1はg1、第1の検証鍵上記v1はv1とする。始点ノード110は、図1に示すように、記憶部111と、始点ノード一方向性ハッシュ関数演算部112と、始点ノード多重署名情報生成部113と、始点ノード署名情報生成部114と、始点ノード多重検証鍵情報生成部115と、始点ノード送信部116とを備える。記憶部111は、始点ノード110の署名鍵x1と、第1の検証鍵v11=x1g1及び第2の検証鍵v21=x1g2とを記憶している。始点ノード一方向性ハッシュ関数演算部112は、メッセージmに対して一方向性ハッシュ関数演算を行って、集合G2に属するハッシュ値h2=H2mを生成する。始点ノード多重署名情報生成部113は、一方向性ハッシュ関数演算により得られたハッシュ値h2に対して始点ノード110自身の署名鍵x1により演算を行って、始点ノード順序付き多重署名情報σ21=x1h2を生成する。始点ノード署名情報生成部114は、一方向性ハッシュ関数演算により得られたハッシュ値h2に対して始点ノード110自身の署名鍵x1により演算を行って、始点ノード署名情報uniσ21=x1h2を生成する。始点ノード多重検証鍵情報生成部115は、始点ノード110自身の第1の検証鍵v11=x1g1から始点ノード順序付き多重検証鍵情報vm11=x1g1を生成する。始点ノード送信部116は、メッセージmと、始点ノード順序付き多重署名情報σ21と、始点ノード110自身の第1の検証鍵v11と、始点ノード署名情報uniσ21と、始点ノード順序付き多重検証鍵情報vm11を、直後のノード中間ノード120又は終点ノード130へ送信する。始点ノード110と終点ノード130の間に位置している署名順序がi番目の中間ノード120は、図2に示すように、記憶部121と、中間ノード受信部122と、中間ノード多重署名情報生成部123と、中間ノード多重検証鍵情報生成部124と、中間ノード一方向性ハッシュ関数演算部125と、中間ノード署名情報生成部126と、中間ノード送信部127とを備える。記憶部121は、中間ノード120の署名鍵xiと、第1の検証鍵v1i=xig1及び第2の検証鍵v2i=xig2とを記憶している。中間ノード受信部122は、メッセージmと、直前のノードi-1番目の中間ノード120又は始点ノード110により生成された直前ノード署名情報uniσ2i-1と、直前のノードにより生成された直前ノード順序付き多重署名情報σ2i-1と、直前のノードにより生成された直前ノード順序付き多重検証鍵情報vm1i-1と、直前のノードの第1の検証鍵v1i-1=xi-1g1を受信する。中間ノード多重署名情報生成部123は、直前ノード署名情報uniσ2i-1に対して中間ノード120自身の署名鍵x2により演算を行い、当該演算の結果に直前ノード順序付き多重署名情報σ2i-1を用いて中間ノード順序付き多重署名情報σ2i=σ2i-1xiuniσ2i-1を生成する。中間ノード多重検証鍵情報生成部124は、直前のノード自身の第1の検証鍵v1i-1=xi-1g1に対して中間ノード120自身の署名鍵xiにより演算を行い、当該演算の結果に直前ノード順序付き多重検証鍵情報vm1i-1を用いて中間ノード順序付き多重検証鍵情報vm1i=vm1i-1xi-1xig1を生成する。中間ノード一方向性ハッシュ関数演算部125は、メッセージmに対して一方向性ハッシュ関数演算を行って、集合G2に属するハッシュ値h2=H2mを生成する。中間ノード署名情報生成部126は、一方向性ハッシュ関数演算により得られたハッシュ値h2に対して中間ノード120自身の署名鍵xiにより演算を行って、中間ノード署名情報uniσ2i=xih2を生成する。中間ノード送信部127は、メッセージmと、中間ノード順序付き多重署名情報σ2iと、中間ノード120自身の第1の検証鍵v1iと、中間ノード署名情報uniσ2iと、中間ノード順序付き多重検証鍵情報vm1iを、直後のノード中間ノード120又は終点ノード130へ送信する。また、メッセージが回覧される最後k番目のノードである終点ノード130は、図3に示すように、記憶部131と、終点ノード受信部132と、終点ノード多重署名情報生成部133と、終点ノード多重検証鍵情報生成部134と、公開部135とを備える。なお、終点ノード受信部132は、中間ノード受信部122と同一の構成であり、終点ノード多重署名情報生成部133は、中間ノード多重署名情報生成部123と同一の構成であり、終点ノード多重検証鍵情報生成部134は、中間ノード多重検証鍵情報生成部124と同一の構成である。記憶部131は、終点ノード130の署名鍵xkと、第1の検証鍵v1k=xkg1及び第2の検証鍵v2k=xkg2とを記憶している。公開部135は、終点ノード多重署名情報生成部133により生成された終点ノード順序付き多重署名情報σ2kと、終点ノード多重検証鍵情報生成部134により生成された終点ノード順序付き多重検証鍵情報vm1kを公開する。このような構成によれば、終点ノード130は、順序付き多重署名情報と順序付き多重検証鍵情報とを、他のノード例えば、後述の検証ノード140に対して公開することができる。次に、多重署名システムに備えられている公開部135により公開された多重署名情報を検証する検証システムについて説明する。なお、以下では、検証システムとしての検証ノード140の構成と動作について説明する。検証ノード140は、図4に示すように、検証ノード一方向性ハッシュ関数演算部141と、収集部142と、第1の検証部143と、第2の検証部144とを備え、公開部135により公開された多重署名情報を検証する。検証ノード一方向性ハッシュ関数演算部141は、メッセージmに対して一方向性ハッシュ関数演算を行って、集合G2に属するハッシュ値h2=H2mを生成する。収集部142は、メッセージmに署名を行った全てのノードの第1の検証鍵v1i及び第2の検証鍵v2iを収集する。このとき、収集部142は、署名順序における各署名者の配置に関する情報順序情報を、必ずしも入手しなくてもよいが、終点ノード130から入手するようにしておくことも好ましい。収集部142がこれらの情報を入手しない場合でも、第1の検証部143は、署名者の配置に関して、全ての組合せを演算することにより、公開された順序付き多重検証鍵情報の正当性を検証することができる。その結果、第2の検証部144は、公開された順序付き多重署名情報の正当性を検証することができる。しかし、収集部142がこれらの情報を入手し第1の検証部143へ受け渡すようにしておくと、これらの情報がない場合に比べて第1の検証部143の演算量が少なくてすむ。第1の検証部143は、収集部142により収集された全てのノードの第1の検証鍵v1i及び第2の検証鍵v2iに基づいて、公開された順序付き多重検証鍵情報vm1kの正当性を検証する。第2の検証部144は、第1の検証部143により正当性が検証された順序付き多重検証鍵情報vm1kに基づいて、公開された順序付き多重署名情報σ2kの正当性を検証する。なお、検証ノード140が有する各構成要件は、始点ノード110や中間ノード120に備えられていてもよい。このような構成の場合には、始点ノード110や中間ノード120は、終点ノード130又は任意のノードにより生成された順序付き多重署名情報の検証を行うので、始点ノード110から終点ノード130まで、又は始点ノードから任意のノードまでの順序付き多重署名の検証を行うことができる。次に、多重署名システムにおいて、署名情報を生成する方法と、検証システムにおいて、署名情報の正当性を検証する方法について説明する。始点ノード110署名者u1は、図5に示すように、始点ノード一方向性ハッシュ関数演算工程ST101と、始点ノード署名情報生成工程ST102と、始点ノード多重署名情報生成工程ST103と、始点ノード多重検証鍵情報生成工程ST104と、始点ノード送信工程ST105とにより、始点ノード順序付き多重署名情報及び始点ノード順序付き多重検証鍵情報を生成して直後のノード中間ノード120又は終点ノード130へ送信する。始点ノード一方向性ハッシュ関数演算工程ST101において、始点ノード一方向性ハッシュ関数演算部112は、メッセージmに対して一方向性ハッシュ関数演算を行う。始点ノード署名情報生成工程ST102において、始点ノード署名情報生成部114は、始点ノード一方向性ハッシュ関数演算工程ST101により得られたハッシュ値h2に対して、始点ノード110自身の署名鍵x1により演算を行い、始点ノード署名情報uniσ21を生成する。始点ノード多重署名情報生成工程ST103において、始点ノード多重署名情報生成部113は、始点ノード一方向性ハッシュ関数演算工程ST101により得られたハッシュ値h2に対して、始点ノード110自身の署名鍵x1により演算を行い、始点ノード順序付き多重署名情報σ21を生成する。始点ノード多重検証鍵情報生成工程ST104において、始点ノード多重検証鍵情報生成部115は、始点ノード110自身の第1の検証鍵v11から始点ノード順序付き多重検証鍵情報vm11を生成する。始点ノード送信工程ST105において、始点ノード送信部116は、メッセージmと、始点ノード順序付き多重署名情報σ21と、始点ノード110自身の第1の検証鍵v11と、始点ノード署名情報uniσ21と、始点ノード順序付き多重検証鍵情報vm11を直後のノードへ送信する。署名順序がi番目の中間ノード120署名者uiは、図6に示すように、中間ノード受信工程ST111と、中間ノード一方向性ハッシュ関数演算工程ST112と、中間ノード署名情報生成工程ST113と、中間ノード多重署名情報生成工程ST114と、中間ノード多重検証鍵情報生成工程ST115と、中間ノード送信工程ST116とにより、中間ノード順序付き多重署名情報及び中間ノード順序付き多重検証鍵情報を生成して直後のノード中間ノード120又は終点ノード130へ送信する。中間ノード受信工程ST111において、中間ノード受信部122は、メッセージmと、直前ノード署名情報uniσ2i-1と、直前ノード順序付き多重署名情報σ2i-1と、直前ノード順序付き多重検証鍵情報vm1i-1と、直前ノードの第1の検証鍵v1i-1を受信する。中間ノード一方向性ハッシュ関数演算工程ST112において、中間ノード一方向性ハッシュ関数演算部125は、メッセージmに対して一方向性ハッシュ関数演算を行う。中間ノード署名情報生成工程ST113において、中間ノード署名情報生成部126は、中間ノード一方向性ハッシュ関数演算工程ST112により得られたハッシュ値h2に対して、中間ノード120自身の署名鍵xiにより演算を行い、中間ノード署名情報uniσ2iを生成する。中間ノード多重署名情報生成工程ST114において、中間ノード多重署名情報生成部123は、直前ノード署名情報uniσ2i-1に対して中間ノード120自身の署名鍵xiにより演算を行い、当該演算の結果に直前ノード順序付き多重署名情報を用いて中間ノード順序付き多重署名情報σ2iを生成する。中間ノード多重検証鍵情報生成工程ST115において、中間ノード多重検証鍵情報生成部124は、直前ノードの第1の検証鍵v1i-1に中間ノード120自身の署名鍵xiにより演算を行い、当該演算の結果に直前ノード順序付き多重検証鍵情報vm1i-1を用いて中間ノード順序付き多重検証鍵情報vm1iを生成する。中間ノード送信工程ST116において、中間ノード送信部127は、メッセージmと、中間ノード順序付き多重署名情報σ2iと、中間ノード120自身の第1の検証鍵v1iと、中間ノード署名情報uniσ2iと、中間ノード順序付き多重検証鍵情報vm1iを直後のノードへ送信する。署名順序がk番目の終点ノード130署名者ukは、図7に示すように、終点ノード受信工程ST121と、終点ノード多重署名情報生成工程ST122と、終点ノード多重検証鍵情報生成工程ST123と、公開工程ST124とにより、公開順序付き多重署名情報及び公開順序付き多重検証鍵情報を生成して公開する。終点ノード受信工程ST121において、終点ノード受信部132は、メッセージmと、直前ノード署名情報uniσ2k-1と、直前ノード順序付き多重署名情報σ2k-1と、直前ノード順序付き多重検証鍵情報vm1k-1と、直前ノードの第1の検証鍵v1k-1を受信する。終点ノード多重署名情報生成工程ST122において、終点ノード多重署名情報生成部133は、直前ノード署名情報uniσ2k-1に対して自身の署名鍵xiにより演算を行い、当該演算の結果に直前ノード順序付き多重署名情報σ2k-1を用いて終点ノード順序付き多重署名情報σ2kを生成する。終点ノード多重検証鍵情報生成工程ST123において、終点ノード多重検証鍵情報生成部134は、直前ノードの第1の検証鍵v1k-1に対して終点ノード130自身の署名鍵xiにより演算を行い、当該演算の結果に直前ノード順序付き多重検証鍵情報vm1k-1を用いて終点ノード順序付き多重検証鍵情報vm1kを生成する。公開工程ST124において、公開部135は、終点ノード多重署名情報生成工程ST122により生成された終点ノード順序付き多重署名情報σ2kと、終点ノード多重検証鍵情報生成工程ST123により生成された終点ノード順序付き多重検証鍵情報vm1kを公開する。このように、多重署名システムに係る多重署名方法によれば、中間ノード120又は終点ノード130は、直前のノードの署名情報に対して自身の署名鍵によって演算を行って隣接するノード間の多重署名情報を生成する。また、中間ノード120又は終点ノード130は、直前のノードの検証鍵に対して自身の署名鍵によって演算を行って隣接するノード間の多重検証鍵情報を生成する。さらに、中間ノード120又は終点ノード130は、多重署名情報の総和に始点ノード署名情報を加算した順序付き多重署名情報と、多重検証鍵情報の総和に始点ノードの第1の検証鍵を加算した順序付き多重検証鍵情報とを生成する。これらの順序付き多重署名情報や順序付き多重検証鍵情報は、自身のノードに至るまでの署名経路を保持し、かつ楕円曲線上の点のみで生成される。すなわち、署名者の数ノードの数が多くなっても、署名サイズは増大せず、一定値以下に抑制することができる。また、検証システムにおける検証ノード140は、図8に示すように、収集工程ST131と、検証ノード一方向性ハッシュ関数演算工程ST132と、第1の検証工程ST133と、第2の検証工程ST134とにより、公開順序付き多重署名情報σ2kの正当性を検証する。収集工程ST131において、収集部142は、メッセージmの署名を行った全てのノードの第1の検証鍵v1i及び第2の検証鍵v2iを収集する。検証ノード一方向性ハッシュ関数演算工程ST132において、検証ノード一方向性ハッシュ関数演算部141は、メッセージmに対して一方向性ハッシュ関数演算を行う。検証ノード一方向性ハッシュ関数演算部141は、例えば、終点ノード130からメッセージmを得る。第1の検証工程ST133において、第1の検証部143は、収集工程ST131により収集された全てのノードの検証鍵v1i及びv2i並びに第2の値g2に基づいて、公開順序付き多重検証鍵情報vm1kの正当性を検証する。第2の検証工程ST134において、第2の検証部144は、第1の検証工程ST133により正当性が検証された公開順序付き多重検証鍵情報vm1kと、検証ノード一方向性ハッシュ関数演算工程ST132により生成されたハッシュ値h2と、第1の値g1とを用いて、公開順序付き多重署名情報σ2kの正当性を検証する。このようにして、検証システムは、第1の検証工程ST133及び第2の検証工程ST134により、全てのノードの検証鍵とメッセージのハッシュ値と楕円曲線上の点g1及びg2に基づいて、公開順序付き多重署名情報の正当性を検証することができる。したがって、検証システムに係る検証方法では、各ノードにて生成される個々の署名情報等を検証することなく、終点ノード130により公開された署名情報を数値演算のみで検証することにより、ノード間をどのような順序で署名されてきたかを証明することができる。すなわち、順序管理のための別の装置を要することなく、検証工程の処理負荷を低減して検証作業を実行することができる。[署名方法]多重署名システムによる署名の手順について、図9を参照しながら説明する。1ユーザuiiは、1≦i≦kとなる自然数の符号に対し、自然数xiただしp≠qならxp≠xqを選び、g1からv1i=xig1を、g2からv2i=xig2を計算する。ここで、xiを署名鍵とし、楕円上の点v1i及びv2iを検証鍵として各ノードに割り当てる。2最初の署名者であるユーザu1始点ノード110は、メッセージmに対するハッシュ値h2=H2mを求め、順序付き多重署名情報σ21=x1h2を計算する。また、始点ノード110は、署名情報uniσ21=x1h2を求める。また、始点ノード110は、順序付き多重検証鍵情報vm11=v11=x1g1を求める。始点ノード110は、順序付き多重署名情報σ21と、署名情報uniσ21と、順序付き多重検証鍵情報vm11と、自身の第1の検証鍵v11を次のユーザu2中間ノード120へ送信する。3i番目のユーザui中間ノード120は、直前のユーザui-1始点ノード110又は中間ノード120から受信した署名情報uniσ2i-1に対して自身の署名鍵xiを使って演算を行いxiuniσ2i-1=xi-1xih2、当該演算結果と直前のユーザui-1から受信した順序付き多重署名情報σ2i-1を使って順序付き多重署名情報σ2iを計算する。さらに、中間ノード120は、署名情報uniσ2i=xih2を計算する。また、中間ノード120は、直前のユーザui-1の第1の検証鍵v1i-1に対して自身の署名鍵xiを使って演算を行いxiv1i-1=xi-1xig1、当該演算結果と直前のユーザui-1から受信した順序付き多重検証鍵情報vm1i-1を使って、順序付き多重検証鍵情報vm1iを計算する。中間ノード120は、順序付き多重署名情報σ2iと、署名情報uniσ2iと、順序付き多重検証鍵情報vm1iと、自身の第1の検証鍵v1iを次のユーザui1中間ノード120又は終点ノード130へ送信する。4最後のユーザuk終点ノード130は、直前のユーザuk-1始点ノード110又は中間ノード120から受信した署名情報uniσ2k-1に対して自身の署名鍵xkを使って演算を行いxkuniσ2k-1=xk-1xkh2、当該演算結果と直前のユーザuk-1から受信した順序付き多重署名情報σ2k-1を使って順序付き多重署名情報σ2kを計算する。さらに、終点ノード130は、直前のユーザuk-1の第1の検証鍵v1k-1に対して自身の署名鍵xkを使って演算を行いxkv1k-1=xk-1xkg1、当該演算結果と直前のユーザuk-1から受信した順序付き多重検証鍵情報vm1k-1を使って、順序付き多重検証鍵情報vm1kを計算する。終点ノード130は、順序付き多重署名情報σ2k及び順序付き多重検証鍵情報vm1kを、それぞれ全ユーザ全ノードの順序付き多重署名情報及び順序付き多重検証鍵情報として公開する。[検証方法]検証ノード140は、以下の手順により検証を行う。検証過程1メッセージmからh2=H2mを求める。検証過程2署名者の検証鍵v1i及びv2iを集める1≦i≦k。検証過程3順序付き多重検証鍵情報vm1kの正当性を検証する。具体的には、集めた検証鍵から10式に基づいて計算した結果とevm1k,g2の値が一致することを確認する。計算結果とevm1k,g2の値が一致した場合には、順序付き多重検証鍵情報vm1kの正当性が証明される。検証過程4正当性が確認された順序付き多重検証鍵情報vm1kを使って順序付き多重署名情報σ2kの正当性を検証する。eg1,σ2kとevm1k,h2を計算し、両者の値が一致することを確認する。ここで、検証過程3について詳細に検討する。11式に示すように、evm1k,g2から計算していくと、12式から16式への展開となり、署名過程が正しく行われていれば、16式と10式とは一致する。このように、16式と10式とが一致するか否かを検証することにより、公開されているユーザの検証鍵から順序付き多重検証鍵情報vm1kの正当性を検証する。なお、10式の第1項ev11,g2は、eg1,v21としてもよい。この場合も、15式の右辺第1項は、eg1,x1g2と変形可能であるから、16式の右辺第1項は、eg1,v21と変形され、16式と10式とは一致する。また、同様に、10式の全ての項において、集合G1に属する第1の検証鍵と集合G2に属する第2の検証鍵とを交換すると共に、ペアリングの順序を入れ替え可能である。また、順序付き多重検証鍵情報vm1kを一つの検証鍵と見なせば、検証過程4による検証は、GDH署名の検証と同じ検証を行っていることになり、多重署名の検証が可能となる。また、順序付き多重署名情報σ2k又は順序付き多重検証鍵情報vm1kの値に着目すると、x1x1x2xi-1xixk-1xk17が得られる。この17式の第一項は、x1のみである。署名鍵の値が一つのみの項は、この第一項のみであることから、ユーザu1が最初の署名者であることが分かる。また、x1が含まれる項は、第二項にもあり、これとの積を構成している値がx2であることから、次の署名者は、ユーザu2であることが分かる。また、x2が含まれる項は、第三項にもあり、これとの積を構成している値がx3であることから、第三の署名者は、ユーザu3であることが分かる。このように、各項の確認作業を順に繰り返すことによって、どのような順番で署名されてきたかが分かり、その結果としてユーザukが最後であることが分かる。また、17式については、CDH問題や楕円曲線上の離散対数問題から秘密情報である署名鍵を知らない第三者が、xi-1xiの式を任意に入れ替えることができないため、第三者による順序の入れ替えは不可能である。また、どんなに署名者が多くなっても、生成される署名情報は、順序付き多重署名情報σ2kと順序付き多重検証鍵情報vm1kの二つの楕円曲線上の点のみであり、それ以外の情報が付加されることはない。よって、署名のサイズは一定の値以下となる。このようにして、多重署名システムは、署名サイズの増大を防ぐことができ、かつ検証時の演算を数値演算のみで行える順序付き多重署名が構成でき、メモリコストや計算機の処理負荷の軽減を図ることができる。本実施形態では、17式において、署名鍵の値が一つのみの項がx1となっており、始点ノード110が明示された上で、各ノードの隣接関係が示されている。本発明はこれには限られず、x1の代わりにxkを用いてもよい。すなわち、公開順序付き多重署名情報を生成していく課程で、始点ノード110の署名情報uniσ21を加算することなく、隣接するノード間の多重署名情報のみを総和した後、終点ノード130の署名情報uniσ2kを加算する。また、公開順序付き多重検証鍵情報を生成していく課程で、始点ノード110の検証鍵v11を加算することなく、隣接するノード間の多重検証鍵情報のみを総和した後、終点ノード130の検証鍵v1kを加算する。このことにより、10式及び16式の右辺第1項ev11,g2は、ev1k,g2となる。<第2実施形態>以下、本発明の実施形態の一例である第2実施形態について説明する。本実施形態に係る多重署名システムは、複数のノードが木構造に構成され、署名対象である電子データメッセージに対して、順序の始点であり直前のノードが存在しないリーフノード始点ノードから、順序の終点であり直後のノードが存在しないルートノード終点ノードへ順に、順序付きの多重署名を行うシステムである。また、ルートノードにより公開された公開順序付き多重署名情報は、検証システムにおける検証ノードにより正当性が検証される。なお、第1実施形態と同様に、集合G1第1のGDHグループに属する第1の値g1と、集合G2第2のGDHグループに属する第2の値g2とが与えられている。また、集合G2の要素に写像変換する一方向性ハッシュ関数H2が定義されている。木構造におけるルートノードよりも下位前の署名順序である下位ノード220は、図10に示すように、記憶部221と、受信部222と、一方向性ハッシュ関数演算部223と、固有署名情報生成部224と、順序付き多重署名情報生成部225と、順序付き多重検証鍵情報生成部226と、送信部227とを備える。なお、受信部222、順序付き多重署名情報生成部225及び順序付き多重検証鍵情報生成部226は、木構造において、自身の直下に一又は複数の下位のノードが存在する場合に機能し、自身の直下に一又は複数の下位のノードが存在しない場合、すなわち自身がリーフノードである場合には機能しない。記憶部221は、自身に割り当てられている署名鍵xupと、第1の検証鍵v1up=xupg1及び第2の検証鍵v2up=xupg2とを記憶する。受信部222は、署名対象であるメッセージmと、直下のノードにより生成された固有署名情報uniσ2lowと、直前のノードにより生成された順序付き多重署名情報σ2lowと、直前のノードの第1の検証鍵v1lowと、直前のノードにより生成された順序付き多重検証鍵情報vm1lowとを受信する。一方向性ハッシュ関数演算部223は、受信したメッセージmに対して一方向性ハッシュ関数演算h2=H2mを行う。固有署名情報生成部224は、一方向性ハッシュ関数演算部223により演算されたハッシュ値h2に対して自身の署名鍵xupにより演算を行い、固有署名情報uniσ2up=xuph2を生成する。順序付き多重署名情報生成部225は、木構造において、自身の直下に一又は複数の下位のノードが存在する場合には、当該一又は複数の下位のノードによって生成された一又は複数の固有署名情報uniσ2lowの各々に対して、自身の署名鍵xupを乗じて、隣接するノード間の多重署名情報を生成する。さらに、木構造において、自身よりも2階層以下の層にも一又は複数のノードが存在する場合には、受信部222は、1階層下のノードから順序付き多重署名情報σ2lowを受信する。そして、順序付き多重署名情報生成部225は、生成した隣接するノード間の多重署名情報を総和し、さらに、下位ノードから順序付き多重署名情報σ2lowを受信した場合には、これらを加算して、自身のノードに至るまでの順序付き多重署名情報σ2up=xupΣuniσ2lowΣσ2lowを生成する。したがって、順序付き多重署名情報生成部225は、木構造において、リーフノードから自身のノードに至るまでの、全ての隣接するノード間で生成される多重署名情報を総和した順序付き多重署名情報σ2upを生成する。順序付き多重検証鍵情報生成部226は、木構造において、自身の直下に一又は複数の下位のノードが存在する場合には、当該一又は複数の下位のノードの第1の検証鍵v1lowの各々に対して、自身の署名鍵xupを乗じて、隣接するノード間の多重検証鍵情報を生成する。さらに、木構造において、自身よりも2階層以下の層にも一又は複数のノードが存在する場合には、受信部222は、1階層下のノードから順序付き多重検証鍵情報vm1lowを受信する。そして、順序付き多重検証鍵情報生成部226は、生成した隣接するノード間の多重検証鍵情報を総和し、さらに、下位ノードから順序付き多重検証鍵情報vm1lowを受信した場合には、これらを加算して、自身のノードに至るまでの順序付き多重検証鍵情報vm1up=xupΣv1lowΣvm1lowを生成する。したがって、順序付き多重検証鍵情報生成部226は、木構造において、リーフノードから自身のノードに至るまでの、全ての隣接するノード間で生成される多重検証鍵情報を総和した順序付き多重検証鍵情報vm1upを生成する。送信部227は、メッセージmと、固有署名情報uniσ2upと、順序付き多重署名情報σ2upと、下位ノード220自身の第1の検証鍵v1upと、順序付き多重検証鍵情報vm1upとを、直上のノード下位ノード220又はルートノード230へ送信する。また、木構造の最上位に位置するルートノード230は、図11に示すように、記憶部231と、受信部232と、一方向性ハッシュ関数演算部233と、順序付き多重署名情報生成部234と、順序付き多重検証鍵情報生成部235と、公開部236とを備える。記憶部231は、自身に割り当てられている署名鍵xrootと、第1の検証鍵v1root=xrootg1及び第2の検証鍵v2root=xrootg2とを記憶する。受信部232は、署名対象であるメッセージmと、直下のノードにより生成された固有署名情報uniσ2lowと、直前のノードにより生成された順序付き多重署名情報σ2lowと、直前のノードの第1の検証鍵v1lowと、直前のノードにより生成された順序付き多重検証鍵情報vm1lowとを受信する。一方向性ハッシュ関数演算部233は、受信したメッセージmに対して一方向性ハッシュ関数演算h2=H2mを行う。順序付き多重署名情報生成部234は、直下の一又は複数の下位のノードにより生成された一又は複数の固有署名情報uniσ2lowの各々に対して自身の署名鍵xrootを乗じて、隣接するノード間の多重検証鍵情報を生成する。また、順序付き多重署名情報生成部234は、一方向性ハッシュ関数演算部233により演算されたハッシュ値h2に対して自身の署名鍵xrootを乗じて固有署名情報uniσ2root=xrooth2を生成する。さらに、木構造において、自身よりも2階層以下の層にも一又は複数のノードが存在する場合には、受信部232は、1階層下のノードから順序付き多重署名情報σ2lowを受信する。そして、順序付き多重署名情報生成部234は、生成した固有署名情報と隣接するノード間の多重署名情報とを総和し、さらに、下位ノードから順序付き多重署名情報σ2lowを受信した場合には、これらを加算して、ルートノード230に至るまでの順序付き多重署名情報σ2root=uniσ2rootxrootΣuniσ2lowΣσ2lowを生成する。したがって、順序付き多重署名情報生成部234は、木構造において、リーフノードからルートノードに至るまでの、全ての隣接するノード間で生成される多重署名情報xlowxuph2の総和に対して、自身の固有署名情報uniσ2rootを加算した公開順序付き多重署名情報σ2root=xrooth2Σxlowxuph2を生成する。順序付き多重検証鍵情報生成部235は、直下の一又は複数の下位のノードの検証鍵v1lowの各々に対して自身の署名鍵xrootを乗じて、隣接するノード間の多重検証鍵情報を生成する。さらに、木構造において、自身よりも2階層以下の層にも一又は複数のノードが存在する場合には、受信部232は、1階層下のノードから順序付き多重検証鍵情報vm1lowを受信する。そして、順序付き多重検証鍵情報生成部235は、自身の第1の検証鍵v1rootと隣接するノード間の多重検証鍵情報とを総和し、さらに、下位ノードから順序付き多重検証鍵情報vm1lowを受信した場合には、これらを加算して、ルートノード230に至るまでの順序付き多重検証鍵情報vm1root=v1rootxrootΣv1lowΣvm1lowを生成する。したがって、順序付き多重検証鍵情報生成部235は、木構造において、リーフノードからルートノードに至るまでの、全ての隣接するノード間で生成される多重検証鍵情報xlowxupg1の総和に対して、自身の第1の検証鍵v1rootを加算した公開順序付き多重署名情報vm1root=xrootg1Σxlowxupg1を生成する。公開部236は、順序付き多重署名情報生成部234により生成されたルートノード230までの順序付き多重署名情報σ2rootと、順序付き多重検証鍵情報生成部235により生成されたルートノード230までの順序付き多重検証鍵情報vm1rootとを公開する。このような構成によれば、ルートノード230は、公開順序付き多重署名情報と公開順序付き多重検証鍵情報とを、他のノード例えば、後述の検証ノード240に対して公開することができる。よって、多重署名システムは、木構造上において連続隣接する2つのノード間の関係を署名鍵の積で表し、それを上位のノードで加算することにより、木構造を表現することができる。また、木構造においてノードの数が増えても、公開されるのは、ルートノード230で生成される公開順序付き多重署名情報σ2rootと公開順序付き多重検証鍵情報vm1rootであり、これらは楕円曲線上の点であるため、各情報のサイズ容量は増大せず、一定値以下に抑制することができ、効率的に順序付き電子署名を生成することができる。次に、公開順序付き多重署名情報を検証する検証システムについて説明する。なお、以下では、検証システムとしての検証ノード240の構成と動作について説明する。検証ノード240は、図12に示すように、一方向性ハッシュ関数演算部241と、収集部242と、第1の検証部243と、第2の検証部244とを備える。一方向性ハッシュ関数演算部241は、署名対象であるメッセージmに対して一方向性ハッシュ関数演算を行うh2=H2m。収集部242は、メッセージの署名を行った全てのノードから第1の検証鍵v1及び第2の検証鍵v2を収集する。このとき、収集部242は、署名順序における各署名者の配置に関する情報順序情報を、必ずしも入手しなくてもよいが、ルートノード230から入手するようにしておくことも好ましい。収集部242がこれらの情報を入手しない場合でも、第1の検証部243は、署名者の配置に関して、全ての組合せを演算することにより、公開順序付き多重検証鍵情報の正当性を検証することができる。その結果、第2の検証部244は、公開順序付き多重署名情報の正当性を検証することができる。しかし、収集部242がこれらの情報を入手し第1の検証部243へ受け渡すようにしておくと、これらの情報がない場合に比べて第1の検証部243の演算量が少なくてすむ。第1の検証部243は、収集部242により収集された全てのノードの第1の検証鍵v1及び第2の検証鍵v2と、集合G2に属する第2の値g2とに基づいて公開順序付き多重検証鍵情報vm1rootの正当性を検証する。第2の検証部244は、第1の検証部243により正当性が検証された公開順序付き多重検証鍵情報vm1root、ハッシュ値h2及び集合G1に属する第1の値g1に基づいて公開順序付き多重署名情報σ2rootの正当性を検証する。具体的には、第1の検証部243は、収集部242によって収集した全てのノードの検証鍵から、Πev1low,v2upev1root,g2を計算し、この計算結果とevm1root,g2の値が一致することを確認することによって、公開順序付き多重検証鍵情報vm1rootの正当性を検証する。また、第2の検証部244は、第1の検証部243によって正当性が確認された公開順序付き多重検証鍵情報vm1rootを利用して、eg1,σ2rootとevm1root,h2を計算し、両者が一致するか否かを確認することによって、公開順序付き多重署名情報σ2rootの正当性を検証する。なお、検証ノード240は、検証専用のノードであってもよいし、木構造上に配置されるいずれかのノードであってもよい。次に、多重署名システムにおいて、公開順序付きの多重署名情報と公開順序付き多重検証鍵情報とを生成する方法と、検証システムにおいて、公開順序付き多重署名情報の正当性を検証する方法について、図13から図15に示すフローチャートを参照しながら説明する。下位ノード220は、図13に示すように、受信工程ST201と、一方向性ハッシュ関数演算工程ST202と、固有署名情報生成工程ST203と、順序付き多重署名情報生成工程ST204と、順序付き多重検証鍵情報生成工程ST205と、送信工程ST206とにより、順序付き多重署名情報及び順序付き多重検証鍵情報を生成して直上のノード下位ノード220又はルートノード230へ送信する。受信工程ST201において、受信部222は、メッセージmと、直下のノードにより生成された固有署名情報uniσ2lowと、直前のノードにより生成された順序付き多重署名情報σ2lowと、直前のノードの第1の検証鍵v1lowと、直前のノードにより生成された順序付き多重検証鍵情報vm1lowとを受信する。一方向性ハッシュ関数演算工程ST202において、一方向性ハッシュ関数演算部223は、受信したメッセージmに対して一方向性ハッシュ関数演算を行う。固有署名情報生成工程ST203において、固有署名情報生成部224は、一方向性ハッシュ関数演算工程ST202により演算されたハッシュ値h2に対して自身の署名鍵xupにより演算を行い、固有署名情報uniσ2upを生成する。順序付き多重署名情報生成工程ST204において、順序付き多重署名情報生成部225は、木構造において、リーフノードから自身のノードに至るまでの、全ての隣接するノード間で生成される多重署名情報を総和した順序付き多重署名情報σ2upを生成する。順序付き多重検証鍵情報生成工程ST205において、順序付き多重検証鍵情報生成部226は、木構造において、リーフノードから自身のノードに至るまでの、全ての隣接するノード間で生成される多重検証鍵情報を総和した順序付き多重検証鍵情報vm1upを生成する。送信工程ST206において、送信部227は、メッセージmと、固有署名情報uniσ2upと、順序付き多重署名情報σ2upと、下位ノード220自身の第1の検証鍵v1upと、順序付き多重検証鍵情報vm1upとを、直上のノードへ送信する。また、ルートノード230は、図14に示すように、受信工程ST211と、一方向性ハッシュ関数演算工程ST212と、順序付き多重署名情報生成工程ST213と、順序付き多重検証鍵情報生成工程ST214と、公開工程ST215とにより、公開順序付き多重署名情報σ2rootと公開順序付き多重検証鍵情報vm1rootとを生成して公開する。受信工程ST211において、受信部232は、メッセージmと、直下のノードにより生成された固有署名情報uniσ2lowと、直前のノードにより生成された順序付き多重署名情報σ2lowと、直前のノードの第1の検証鍵v1lowと、直前のノードにより生成された順序付き多重検証鍵情報vm1lowとを受信する。一方向性ハッシュ関数演算工程ST212において、一方向性ハッシュ関数演算部233は、受信したメッセージmに対して一方向性ハッシュ関数演算を行う。順序付き多重署名情報生成工程ST213において、順序付き多重署名情報生成部234は、木構造において、リーフノードからルートノードに至るまでの、全ての隣接するノード間で生成される多重署名情報xlowxuph2の総和に対して、自身の固有署名情報uniσ2rootを加算した公開順序付き多重署名情報σ2root=xrooth2Σxlowxuph2を生成する。順序付き多重検証鍵情報生成工程ST214において、順序付き多重検証鍵情報生成部235は、木構造において、リーフノードからルートノードに至るまでの、全ての隣接するノード間で生成される多重検証鍵情報xlowxupg1の総和に対して、自身の第1の検証鍵v1rootを加算した公開順序付き多重署名情報vm1root=xrootg1Σxlowxupg1を生成する。公開工程ST215において、公開部236は、ルートノード230までの順序付き多重署名情報σ2rootと、ルートノード230までの順序付き多重検証鍵情報vm1rootとを公開する。よって、多重署名システムに係る多重署名方法によれば、ツリー構造上において連続隣接する2つのノード間の関係を署名鍵の積で表し、それを上位のノードで加算することにより、木構造を表現することができる。また、ノードの数が増えても、公開されるのは、最上位のルートノード230で生成される公開順序付き多重検証鍵情報vm1rootと公開順序付き多重署名情報σ2rootであり、これらは楕円曲線上の点であるため、各情報のサイズ容量は増大せず、一定値以下に抑制することができ、効率的に順序付き電子署名を生成することができる。また、検証ノード240は、図15に示すように、一方向性ハッシュ関数演算工程ST221と、収集工程ST222と、第1の検証工程ST223と、第2の検証工程ST224とにより、公開順序付き多重署名情報σ2rootの正当性を検証する。一方向性ハッシュ関数演算工程ST221において、一方向性ハッシュ関数演算部241は、メッセージmに対して一方向性ハッシュ関数演算を行う。収集工程ST222において、収集部242は、メッセージmの署名を行った全てのノードから第1の検証鍵v1及び第2の検証鍵v2を収集する。第1の検証工程ST223において、第1の検証部243は、収集工程ST222により収集された全てのノードの第1の検証鍵v1及び第2の検証鍵v2と、集合G2に属する第2の値g2とに基づいて公開順序付き多重検証鍵情報vm1rootの正当性を検証する。第2の検証工程ST224において、第2の検証部244は、第1の検証工程ST223により正当性が検証された公開順序付き多重検証鍵情報vm1root、ハッシュ値h2及び集合G1に属する第1の値g1に基づいて公開順序付き多重署名情報σ2rootの正当性を検証する。このようにして、検証システムは、第1の検証工程ST223及び第2の検証工程ST224により、全てのノードの検証鍵とメッセージのハッシュ値と楕円曲線上の点g1及びg2に基づいて、公開順序付き多重署名情報の正当性を検証することができる。したがって、検証システムに係る検証方法では、各ノードにて生成される個々の署名情報等を検証することなく、ルートノード230により公開された署名情報を数値演算のみで検証することにより、木構造におけるノード間をどのような順序で署名されてきたかを証明することができる。すなわち、順序管理のための別の装置を要することなく、検証工程の処理負荷を低減して検証作業を実行することができる。[実施例]ここで、木構造が3分木3階層で構成されている場合における多重署名システムの動作について図16を参照しながら具体的に説明する。なお、以下では、第1層を最上位のノードルートノードであるとし、第3層を最下位のノードリーフノードとする。また、第1層は、一つのノードルートノードが配置され、第2層は、三つのノードルートノードの直下にノード1からノード3が配置されているが配置され、第3層は、九つのノードノード1の直下にノード11からノード13が配置され、ノード2の直下にノード21からノード23が配置され、ノード3の直下にノード31からノード33が配置されているが配置されている。また、認証局CAは、予め各ノードに重複しない署名鍵と検証鍵を付与している。例えば、最上位のルートノードには、他のノードとは重複しない署名鍵と検証鍵が以下のように付与されている。ルートノード:署名鍵,第1の検証鍵,第2の検証鍵=xroot,v1root,v2root=xroot,xrootg1,xrootg2ノード1からノード3には、それぞれ他のノードとは重複しない署名鍵と検証鍵が以下のように付与されている。ノード1:署名鍵,第1の検証鍵,第2の検証鍵=x1,v11,v21=x1,x1g1,x1g2ノード2:署名鍵,第1の検証鍵,第2の検証鍵=x2,v12,v22=x2,x2g1,x2g2ノード3:署名鍵,第1の検証鍵,第2の検証鍵=x3,v13,v23=x3,x3g1,x3g2ノード11からノード33には、それぞれ他のノードとは重複しない署名鍵と検証鍵が以下のように付与されている。ノード11:署名鍵,第1の検証鍵,第2の検証鍵=x11,v111,v211=x11,x11g1,x11g2ノード12:署名鍵,第1の検証鍵,第2の検証鍵=x12,v112,v212=x12,x12g1,x12g2ノード13:署名鍵,第1の検証鍵,第2の検証鍵=x13,v113,v213=x13,x13g1,x13g2ノード21:署名鍵,第1の検証鍵,第2の検証鍵=x21,v121,v221=x21,x21g1,x21g2ノード22:署名鍵,第1の検証鍵,第2の検証鍵=x22,v122,v222=x22,x22g1,x22g2ノード23:署名鍵,第1の検証鍵,第2の検証鍵=x23,v123,v223=x23,x23g1,x23g2ノード31:署名鍵,第1の検証鍵,第2の検証鍵=x31,v131,v231=x31,x31g1,x31g2ノード32:署名鍵,第1の検証鍵,第2の検証鍵=x32,v132,v232=x32,x32g1,x32g2ノード33:署名鍵,第1の検証鍵,第2の検証鍵=x33,v133,v233=x33,x33g1,x33g2第3層のユーザu11ノード11は、メッセージmに対してハッシュ値h2=H2mを求め、ハッシュ値に自身の署名鍵x11により演算を行い固有署名情報uniσ211=x11h2を生成する。また、ユーザu11ノード11は、自身の検証鍵v111と、固有署名情報uniσ211とを直上のノード1へ送信する。なお、第3層における他のノードのユーザu12ノード12からユーザu33ノード33も同様に固有署名情報を生成し、生成した固有署名情報と自身の検証鍵とを直上のノードへ送信する。第2層のユーザu1ノード1は、直下のユーザユーザu11ノード11、ユーザu12ノード12、ユーザu13ノード13から受信したそれぞれの固有署名情報uniσ211、uniσ212、uniσ213に対して自身の署名鍵x1により演算を行い、自身のノードまでの順序付き多重署名情報σ21を生成する18式及び19式を参照。ユーザu1ノード1は、メッセージmに対してハッシュ値h2=H2mを求め、ハッシュ値に自身の署名鍵x1により演算を行い、固有署名情報uniσ21=x1h2を生成する。また、ユーザu1ノード1は、直下のユーザユーザu11ノード11、ユーザu12ノード12、ユーザu13ノード13から受信したそれぞれの検証鍵v111、v112、v113に対して、自身の署名鍵x1により演算を行い、自身のノードまでの順序付き多重検証鍵情報vm11を生成する20式及び21式を参照。また、ユーザu1ノード1は、自身の検証鍵v11と、固有署名情報uniσ21と、順序付き多重署名情報σ21と、順序付き多重検証鍵情報vm11とを、直上のノード本実施例では、ルートノードへ送信する。なお、第2層における他のノードのユーザu2ノード2及びユーザu3ノード3も同様に固有署名情報と、順序付き多重署名情報と、順序付き多重検証鍵情報とを生成し、自身の検証鍵と、固有署名情報と、順序付き多重署名情報と、順序付き多重検証鍵情報とを、直上のノード本実施例では、ルートノードへ送信する。ルートノードユーザurootは、メッセージmに対して一方向性ハッシュ関数演算を行い、そのハッシュ値h2に自身の署名鍵xrootにより演算を行って得られた演算値xrooth2と、直下のユーザユーザu1ノード1、ユーザu2ノード2、ユーザu3ノード3から受信したそれぞれの固有署名情報uniσ21、uniσ22、uniσ23に対して、自身の署名鍵xrootにより演算を行って得られた演算値と、直下のユーザから受信したそれぞれの順序付き多重署名情報σ21、σ22、σ23とからなる公開順序付き多重署名情報σ2rootを生成する22式及び23式を参照。また、ルートノードユーザurootは、自身の第1の検証鍵v1root=xrootg1と、直下のユーザユーザu1ノード1、ユーザu2ノード2、ユーザu3ノード3から受信したそれぞれの検証鍵v11、v12、v13に対して、自身の署名鍵xrootにより演算を行って得られた演算値と、直下のユーザから受信したそれぞれの順序付き多重検証鍵情報vm11、vm12、vm13とからなる公開順序付き多重検証鍵情報vm1rootを生成する24式及び25式を参照。ルートノードユーザurootは、生成した公開順序付き多重署名情報σ2rootと公開順序付き多重検証鍵情報vm1rootを公開する。また、検証ノード240は、以下の検証過程1から検証過程4により公開順序付き多重署名情報σ2rootの正当性を検証する。検証過程1検証ノード240は、メッセージmに対してハッシュ値h2=H2mを求める。検証過程2検証ノード240は、メッセージの署名を行った全てのノードの検証鍵を収集する。検証過程3検証ノード240は、ルートノード230によって公開された公開順序付き多重検証鍵情報vm1rootの正当性を検証する。具体的には、検証ノード240は、収集した全てのノードの検証鍵から26式及び27式に示す演算を行い、27式とevm1root,g2とが一致することを確認し、これらの値が一致した場合には、公開順序付き多重検証鍵情報vm1rootが正当であると判断する。検証過程4検証ノード240は、正当性が検証された公開順序付き多重検証鍵情報vm1rootに基づいて公開順序付き多重署名情報σ2rootの正当性を検証する。検証ノード240は、具体的には、eg1,σ2rootとevm1root,h2を計算し、これらの値が一致することを確認し、これらの一致した場合には、公開対象の順序付き多重署名情報σ2rootが正当であると判断する。ここで、検証過程3におけるevm1root,g2の演算過程について説明する。なお、便宜上xを、28式と置く。x=xrootxrootx1xrootx2xrootx3x11x1x12x1x13x1x21x2x22x2x23x2x31x3x32x3x33x328なお、署名の過程が正しく行われていれば、27式と33式は、一致する。また、公開順序付き多重検証鍵情報vm1rootを一つの検証鍵と見なせば、検証過程4による検証は、GDH署名の検証と同じ検証を行っていることになり、多重署名の検証が可能となる。なお、27式の第1項ev1root,g2は、eg1,v2rootとしてもよい。この場合も、32式の右辺第1項は、eg1,xrootg2と変形可能であるから、33式の右辺第1項は、eg1,v2rootと変形され、27式と33式とは一致する。また、同様に、27式の全ての項において、集合G1に属する第1の検証鍵と集合G2に属する第2の検証鍵とを交換すると共に、ペアリングの順序を入れ替え可能である。また、28式に着目すると、右辺第1項は、ルートノード230の署名鍵xrootのみで構成されている。よって、第1層の署名者は、ユーザurootであることが分かる。また、ルートノード230の署名鍵xrootは、右辺第2項、右辺第3項及び右辺第4項に含まれており、これを積として構成している値がx1、x2、x3であることから、第2層の署名者は、ユーザu1、ユーザu2、ユーザu3であることが分かる。また、第2層のユーザu1の署名鍵x1の値と積を構成している値がx11、x12、x13であることから、ノード1の直下のノード第3層の署名者は、ユーザu11、ユーザu12、ユーザu13であることが分かる。また、同様にして、ノード2の直下のノードの署名者は、ユーザu21、ユーザu22、ユーザu23であり、ノード3の直下のノードの署名者は、ユーザu31、ユーザu32、ユーザu33であることが分かる。このようにして、検証ノード240は、木構造上、どのような上下関係の下に署名されてきたのかを把握することができ、その結果として、木構造上のユーザの配置を把握することができる。また、28式については、CDH問題や楕円曲線上の離散対数問題から秘密情報である署名鍵を知らない第三者が、右辺の各項xpxqを任意に入れ替えることができないため、第三者による順序の入れ替えは不可能である。検証ノード240が採用する本検証方式は、木構造上において連続隣接する2つのノード間の関係を署名鍵の積で表し、それを上位のノードで加算することにより、木構造を表現することができる。また、ノードの数が増えても、公開されるのは、ルートノード230で生成される公開順序付き多重検証鍵情報vm1rootと公開順序付き多重署名情報σ2rootであり、これらは楕円曲線上の点であるため、各情報のサイズ容量は増大せず、一定値以下に抑制することができ、効率的に順序付き電子署名を生成することができる。また、本実施例においては、3分木3階層による木構造によって説明したが、これに限らず、3分木3階層以外の多分木多階層による木構造においても適用可能である。また、多重署名システムは、コンテンツの管理に利用することができる。映画の制作には、複数の工程があり、工程ごとに制作者が存在する。例えば、映画の統括者プロデューサを最上位のルートノード230とし、監督等の各制作者を下位ノード220として配置する。多重署名システムは、完成したコンテンツをメッセージmとして、各ノードに回覧する。各ノードでは、コンテンツの内容を確認し、木構造上において自身が配置されている位置に基づいた順序付きの電子署名を行い、直上のノードに必要な情報を送信する。そして、ルートノード230は、直下のノードから送信されてきた各種情報に基づいて公開順序付き多重検証鍵情報vm1rootと公開順序付き多重署名情報σ2rootを生成する。また、検証ノード240は、公開順序付き多重検証鍵情報vm1rootの正当性と、公開順序付き多重署名情報σ2rootの正当性を確認する。このようにして、検証ノード240は、公開順序付き多重署名情報σ2rootの正当性が確認されることによって、完成したコンテンツが各制作者に正しく回覧されて確認されたことを証明することができる。このようにして、多重署名システムは、コンテンツの管理を行うことができる。本実施形態では、28式において、署名鍵の値が一つのみの項がxrootとなっており、ルートノード230が明示された上で、各ノードの隣接関係が示されている。本発明はこれには限られず、xrootの代わりにリーフノードの署名鍵例えば、x11~x33を用いてもよい。すなわち、公開順序付き多重署名情報を生成していく課程で、隣接するノード間の多重署名情報の総和に対して、ルートノード230の固有署名情報uniσ2rootを加算せずに、リーフノードの固有署名情報uniσ2leafを加算する。また、公開順序付き多重検証鍵情報を生成していく課程で、隣接するノード間の多重検証鍵情報の総和に対して、ルートノード230の検証鍵v1rootを加算せずに、リーフノード210の検証鍵v1leafを加算する。このことにより、27式及び33式の右辺第1項ev1root,g2は、ev111,g2ev133,g2となる。<第3実施形態>以下、本発明の実施形態の一例である第3実施形態について説明する。本実施形態に係る多重署名システムは、複数の一般ノード320がメッシュ構造状に構成され、当該複数の一般ノード320間で多重署名を行って電子データメッセージを回覧し、代表ノード330公開ノードによりメッシュ構造を表現した電子署名を公開する。さらに、検証システムにおける検証ノード340は、代表ノード330により公開された電子署名の正当性を検証する。これにより、検証ノード340は、エンティティ間でどのように署名がなされてきたかを確認し、メッシュ構造により関係性が構築されているエンティティの配置を確認することができる。なお、本実施形態においては、第1実施形態又は第2実施形態における始点ノード及び終点ノードは存在しない。また、第1実施形態と同様に、集合G1第1のGDHグループに属する第1の値g1と、集合G2第2のGDHグループに属する第2の値g2とが与えられている。また、集合G2の要素に写像変換する一方向性ハッシュ関数H2が定義されている。メッシュ構造における一般ノード320は、図17に示すように、記憶部321と、受信部322と、一方向性ハッシュ関数演算部323と、固有署名情報生成部324と、多重署名情報生成部325と、多重検証鍵情報生成部326と、送信部327とを備える。記憶部321は、自身署名者uqのノードに割り当てられている署名鍵xqと、第1の検証鍵v1q及び第2の検証鍵v2qとを記憶する。受信部322は、署名対象であるメッセージmと、隣接する直前のノード署名者upのノードにより生成された固有署名情報uniσ2pと、直前のノードの第1の検証鍵v1pとを受信する。一方向性ハッシュ関数演算部323は、受信したメッセージmに対して一方向性ハッシュ関数演算h2=H2mを行う。固有署名情報生成部324は、一方向性ハッシュ関数演算部323により演算されたハッシュ値h2に対して自身の署名鍵xqにより演算を行い、固有署名情報uniσq=xqh2を生成する。多重署名情報生成部325は、隣接する直前の一般ノード320署名者upのノードによって生成された固有署名情報uniσ2pに対して、自身の署名鍵xqにより演算を行い、隣接する一般ノード320間up-uq間に固有の多重署名情報σ2p-qを生成する。多重検証鍵情報生成部326は、隣接する直前の一般ノード320署名者upのノードの第1の検証鍵v1pに対して、自身の署名鍵xqにより演算を行い、隣接する一般ノード320間up-uq間に固有の多重検証鍵情報vm1p-qを生成する。送信部327は、メッセージmと、自身の第1の検証鍵v1qと、固有署名情報uniσ2qとを、隣接する直後の一般ノード320へ送信する。また、送信部327は、多重署名情報σ2p-qと多重検証鍵情報vm1p-qとを、代表ノード330へ送信する。ここで、多重署名情報及び多重検証鍵情報は、メッシュ構造において、隣接する一般ノード320の全ての組合せのそれぞれに対して生成され、これらが代表ノード330へ送信される。なお、多重署名情報σ2p-q及び多重検証鍵情報vm1p-qは、隣接する一般ノード320のいずれか一方up又はuqにおいて生成されるものとし、代表ノード330へ送信される情報は重複しないものとする。メッシュ構造に構成された一般ノード320を統括する代表ノード330は、図18に示すように、記憶部331と、受信部332と、一方向性ハッシュ関数演算部333と、固有署名情報生成部334と、多重署名情報生成部335と、多重検証鍵情報生成部336とを備える。記憶部331は、自身に割り当てられている署名鍵xrと、第1の検証鍵v1r及び第2の検証鍵v2rとを記憶する。受信部332は、一般ノード320から、多重署名情報σ2p-qと多重検証鍵情報vm1p-qとを受信する。一方向性ハッシュ関数演算部333は、メッセージmに対して一方向性ハッシュ関数演算を行うh2=H2m。固有署名情報生成部334は、一方向性ハッシュ関数演算部333により演算されたハッシュ値h2に対して自身の署名鍵xrにより演算を行って、固有署名情報uniσ2r=xrh2を生成する。多重署名情報生成部335は、メッシュ構造における一又は複数の隣接する一般ノード320間に固有の多重署名情報σ2p-qを総和し、さらに固有署名情報生成部334により生成された固有署名情報uniσ2rを含んで加算して、公開多重署名情報σ2rを生成する。多重検証鍵情報生成部336は、メッシュ構造における一又は複数の隣接する一般ノード320間に固有の多重検証鍵情報vm1p-qを総和し、さらに代表ノードの第1の検証鍵v1rを含んで加算して、公開多重検証鍵情報vm1rを生成する。公開部337は、多重署名情報生成部335により生成された公開多重署名情報σ2rと、多重検証鍵情報生成部336により生成された公開多重検証鍵情報vm1rとを公開する。このような構成によれば、代表ノード330は、公開多重署名情報と公開多重検証鍵情報とを、他のノード例えば、後述の検証ノード340に対して公開することができる。このように、多重署名システムは、メッシュ構造状に構成されている複数の一般ノード320と、代表ノード330とによって構成され、メッシュ構造上において連続隣接する二つの一般ノード320間up-uq間において、いずれかのノードが多重署名情報σ2p-q及び多重検証鍵情報vm1p-qを演算により生成する。そして、多重署名システムは、全ての一般ノード320間に対して生成された多重署名情報と多重検証鍵情報とを代表ノード330で総和する。さらに、代表ノード330は、代表ノードの固有署名情報uniσ2r=xrh2を多重署名情報の総和に加算したものを、メッシュ構造全体の公開多重署名情報σ2r=uniσ2rΣσ2p-qとして公開する。また、代表ノード330は、代表ノード330の第1の検証鍵v1r=xrg1を多重検証鍵情報の総和に加算したものを、メッシュ構造全体の公開多重検証鍵情報vm1r=v1rΣvm1p-qとして公開する。よって、多重署名システムは、メッシュ構造上において連続隣接する二つの一般ノード320間の関係を署名鍵の積で表し、それらを代表ノード330で総和し、さらに代表ノード330の署名鍵を加算することにより、代表ノード330を含んだメッシュ構造を表現することができる。また、メッシュ構造において一般ノード320の数や結び付き隣接の数が増えても、公開されるのは、代表ノード330で生成される公開多重署名情報σ2rと公開検証鍵情報vm1rである。これらは楕円曲線上の点であるため、各情報のサイズ容量は増大せず、一定値以下に抑制することができ、効率的に多重電子署名を生成することができる。次に、公開多重署名情報を検証する検証システムについて説明する。検証システムが有する検証ノード340は、図19に示すように、一方向性ハッシュ関数演算部341と、収集部342と、第1の検証部343と、第2の検証部344とを備える。一方向性ハッシュ関数演算部341は、メッセージmに対して一方向性ハッシュ関数演算を行うh2=H2m。収集部342は、メッセージの署名を行った全ての一般ノード320の第1の検証鍵v1p、v1q、及び第2の検証鍵v2p、v2q、と、代表ノード330の第1の検証鍵v1rとを収集する。このとき、収集部342は、署名順序における各署名者の配置に関する情報順序情報を、必ずしも入手しなくてもよいが、代表ノード330から入手するようにしておくことも好ましい。収集部342がこれらの情報を入手しない場合でも、第1の検証部343は、署名者の配置に関して、全ての組合せを演算することにより、公開順序付き多重検証鍵情報の正当性を検証することができる。その結果、第2の検証部344は、公開順序付き多重署名情報の正当性を検証することができる。しかし、収集部342がこれらの情報を入手し第1の検証部343へ受け渡すようにしておくと、これらの情報がない場合に比べて第1の検証部343の演算量が少なくてすむ。第1の検証部343は、収集部342により収集された全ての一般ノード320の検証鍵及び代表ノード330の検証鍵と、集合G2に属する第2の値g2とに基づいて、公開多重検証鍵情報vm1rの正当性を検証する。第2の検証部344は、第1の検証部343により正当性が検証された公開多重検証鍵情報vm1r、ハッシュ値h2及び集合G1に属する第1の値g1に基づいて、公開多重署名情報σ2rの正当性を検証する。具体的には、第1の検証部343は、収集部342によって収集した一般ノード320の検証鍵と代表ノード330の検証鍵とから、全ての隣接した一般ノード320の組合せup,uqについてΠev1p,v1qev1r,g2を計算し、この計算結果とevm1r,g2の値が一致することを確認することによって、公開多重検証鍵情報vm1rの正当性を検証する。また、第2の検証部344は、第1の検証部343によって正当性が確認された公開多重検証鍵情報vm1rを利用して、eg1,σ2rとevm1r,h2を計算し、両者が一致するか否かを確認することによって、公開多重署名情報σ2rの正当性を検証する。このようにして検証ノード340は、第1の検証部343により全ての一般ノード320の検証鍵と代表ノード330の検証鍵とに基づいて公開多重検証鍵情報の正当性を検証し、正当性が検証された公開多重検証鍵情報に基づいて、第2の検証部344により公開多重署名情報の正当性を検証する。したがって、検証システムでは、一般ノード320にて生成される個々の多重検証鍵情報や多重署名情報等を検証することなく、これらの総和を含んで生成される公開多重検証鍵情報と公開多重署名情報とを検証することにより、代表ノード330を含んだメッシュ構造により関係性が構築されているノードの状況を証明することができる。すなわち、検証ノード340の処理負荷を低減して検証作業を実行することができる。なお、検証ノード340は、検証専用のノードであってもよいし、多重署名システムのメッシュ構造上に配置されるいずれかの一般ノード320や代表ノード330であってもよい。次に、多重署名システムにおいて、一般ノード320と代表ノード330により公開多重署名情報と公開多重検証鍵情報を生成する方法と、検証システムにおいて、検証ノード340により公開多重署名情報の正当性を検証する方法について説明する。一般ノード320署名者up及びuqは、図20に示すように、一方向性ハッシュ関数演算工程ST301と、固有署名情報生成工程ST302と、送信工程ST303と、受信工程ST304と、多重署名情報生成工程ST305と、多重検証鍵情報生成工程ST306とにより、隣接する一般ノード320間up-uq間に固有の多重署名情報σ2p-qと、隣接する一般ノード320間に固有の多重検証鍵情報vm1p-qを生成する。一方向性ハッシュ関数演算工程ST301において、署名者upのノードにおける一方向性ハッシュ関数演算部323は、メッセージmに対して一方向性ハッシュ関数演算を行う。固有署名情報生成工程ST302において、署名者upのノードにおける固有署名情報生成部324は、一方向性ハッシュ関数演算工程ST301により演算されたハッシュ値h2に対して自身の署名鍵xpにより演算を行い、署名情報uniσ2p=xph2を生成する。送信工程ST303において、署名者upのノードにおける送信部327は、メッセージmと、自身の第1の検証鍵v1pと、固有署名情報uniσ2pとを、隣接する署名者uqのノードへ送信する。受信工程ST304において、署名者uqのノードにおける受信部322は、隣接する署名者upのノードから、署名対象であるメッセージmと、固有署名情報uniσ2pと、第1の検証鍵v1pとを受信する。多重署名情報生成工程ST305において、署名者uqのノードにおける多重署名情報生成部325は、固有署名情報生成工程ST302により生成された固有署名情報uniσ2pに対して、自身の署名鍵xqにより演算を行い、隣接する一般ノード320間up-uq間に固有の多重署名情報σ2p-qを生成する。多重検証鍵情報生成工程ST306において、署名者uqのノードにおける多重検証鍵情報生成部326は、署名者upのノードの第1の検証鍵v1pに対して、自身の署名鍵xqにより演算を行い、隣接する一般ノード320間up-uq間に固有の多重検証鍵情報vm1p-qを生成する。また、代表ノード330は、図21に示すように、受信工程ST311と、一方向性ハッシュ関数演算工程ST312と、固有署名情報生成工程ST313と、多重署名情報生成工程ST314と、多重検証鍵情報生成工程ST315と、公開工程ST316とにより、公開多重署名情報σ2rと、公開多重検証鍵情報vm1rとを生成して公開する。受信工程ST311において、受信部332は、一般ノード320から、多重署名情報σ2p-qと多重検証鍵情報vm1p-qとを受信する。一方向性ハッシュ関数演算工程ST312において、一方向性ハッシュ関数演算部333は、メッセージmに対して一方向性ハッシュ関数演算を行うh2=H2m。固有署名情報生成工程ST313において、固有署名情報生成部334は、一方向性ハッシュ関数演算工程ST312で演算されたハッシュ値h2に対して自身の署名鍵xrにより演算を行って、固有署名情報uniσ2r=xrh2を生成する。多重署名情報生成工程ST314において、多重署名情報生成部335は、メッシュ構造における一又は複数の隣接する一般ノード320間に固有の多重署名情報を総和し、さらに代表ノード330の固有署名情報を加算して公開多重署名情報σ2rを生成する。多重検証鍵情報生成工程ST315において、多重検証鍵情報生成部336は、メッシュ構造における一又は複数の隣接する一般ノード320間に固有の多重検証鍵情報を総和し、さらに代表ノード330の第1の検証鍵v1rを加算して公開多重検証鍵情報vm1rを生成する。公開工程ST316において、公開部337は、公開多重署名情報σ2rと、公開多重検証鍵情報vm1rとを公開する。このように、多重署名システムに係る多重署名方法によれば、メッシュ構造上において連続隣接する二つの一般ノード320間up-uq間において、いずれかのノードが多重署名情報σ2p-q及び多重検証鍵情報vm1p-qを演算により生成する。そして、多重署名システムに係る多重署名方法は、全ての一般ノード320間に対して生成された多重署名情報と多重検証鍵情報とを代表ノード330で総和する。さらに、多重署名システムに係る多重署名方法は、代表ノード330の固有署名情報uniσ2r=xrh2を多重署名情報の総和に加算したものを、メッシュ構造全体の公開多重署名情報σ2r=uniσ2rΣσ2p-qとして、また、代表ノード330の第1の検証鍵v1r=xrg1を多重検証鍵情報の総和に加算したものを、メッシュ構造全体の公開多重検証鍵情報vm1r=v1rΣvm1p-qとして公開する。よって、多重署名システムに係る多重署名方法によれば、メッシュ構造上において連続隣接する二つの一般ノード320間の関係を署名鍵の積で表し、それらを代表ノード330で総和し、さらに代表ノード330の署名鍵を加算することにより、代表ノード330を含んだメッシュ構造を表現することができる。また、メッシュ構造において一般ノード320の数や結び付き隣接の数が増えても、公開されるのは、代表ノード330で生成される公開多重署名情報σ2rと公開検証鍵情報vm1rである。これらは楕円曲線上の点であるため、各情報のサイズ容量は増大せず、一定値以下に抑制することができ、効率的に多重電子署名を生成することができる。また、検証ノード340は、図22に示すように、一方向性ハッシュ関数演算工程ST321と、収集工程ST322と、第1の検証工程ST323と、第2の検証工程ST324とにより、公開多重署名情報σ2rの正当性を検証する。一方向性ハッシュ関数演算工程ST321において、一方向性ハッシュ関数演算部341は、メッセージmに一方向性ハッシュ関数演算を行う。収集工程ST322において、収集部342は、メッセージmの署名を行った全ての一般ノード320の第1の検証鍵v1及び第2の検証鍵v2を収集する。第1の検証工程ST323において、第1の検証部343は、収集工程ST322により収集された全ての一般ノード320の検証鍵と、集合G2に属する第2の値g2とに基づいて、公開多重検証鍵情報vm1rの正当性を検証する。第2の検証工程ST324において、第2の検証部344は、第1の検証工程ST323により正当性が検証された公開多重検証鍵情報、ハッシュ値h2及び集合G1に属する第1の値g1に基づいて、公開多重署名情報σ2rの正当性を検証する。このように、検証システムに係る検証方法では、一般ノード320にて生成される個々の多重検証鍵情報や多重署名情報等を検証することなく、これらの総和として生成される公開多重検証鍵情報と公開多重署名情報とを検証することにより、メッシュ構造により関係性が構築されているノードの状況を証明することができる。すなわち、第1の検証工程ST323や第2の検証工程ST324の処理負荷を低減して検証作業を実行することができる。[実施例]ここで、多重署名システムの動作について、図23に示すメッシュ構造を一例として具体的に説明する。なお、この例では、ノード1からノード7の七つの一般ノード320がメッシュ構造状に配置され、ノード1とノード2、ノード2とノード3、ノード3とノード4、ノード4とノード5、ノード5とノード6、ノード6とノード7、ノード7とノード1、ノード2とノード6、ノード3とノード5、ノード3とノード7がそれぞれ隣接するノードとして相互に多重署名を行う。また、認証局CAは、予め各ノードに重複しない署名鍵と検証鍵を付与している。具体的には、ノード1からノード7と代表ノード330ノードrには、それぞれ他のノードとは重複しない署名鍵と検証鍵が以下のように付与されている。ノード1:署名鍵,第1の検証鍵,第2の検証鍵=x1,v11,v21=x1,x1g1,x1g2ノード2:署名鍵,第1の検証鍵,第2の検証鍵=x2,v12,v22=x2,x2g1,x2g2ノード3:署名鍵,第1の検証鍵,第2の検証鍵=x3,v13,v23=x3,x3g1,x3g2ノード4:署名鍵,第1の検証鍵,第2の検証鍵=x4,v14,v24=x4,x4g1,x4g2ノード5:署名鍵,第1の検証鍵,第2の検証鍵=x5,v15,v25=x5,x5g1,x5g2ノード6:署名鍵,第1の検証鍵,第2の検証鍵=x6,v16,v26=x6,x6g1,x5g2ノード7:署名鍵,第1の検証鍵,第2の検証鍵=x7,v17,v27=x7,x7g1,x7g2ノードr:署名鍵,第1の検証鍵,第2の検証鍵=xr,v1r,v2r=xr,xrg1,xrg2まず、各ノードノード1~ノード7、ノードrは、電子データ例えば、メッシュ構造の確認情報としてのメッセージmに対してハッシュ値h2=H2mを求める。次に、全ての隣接するノード間において、多重署名情報と多重検証鍵情報とを生成する。具体的には、例えば、ノード1署名者u1は、ハッシュ値h2に自身の署名鍵x1をかけて固有署名情報uniσ21=x1h2を生成し、検証鍵v11と共にノード2に送信する。そして、ノード2署名者u2は、ノード1から受信した固有署名情報uniσ21に対して自身の署名鍵x2をかけて、34式により多重署名情報を生成する。σ21-2=x2x1h2=x1x2h234また同様に、ノード2は、ノード1から受信した第1の検証鍵v11に対して自身の署名鍵x2をかけて、35式により多重検証鍵情報を生成する。vm11-2=x2x1g1=x1x2g135なお、34式及び35式の計算は、ノード1又はノード2のいずれが行ってもよい。すなわち、ノード2が固有署名情報uniσ22=x2h2を生成した後に第1の検証鍵v12と共にノード1へ送信し、ノード1が多重署名情報σ21-2及び多重検証鍵情報vm11-2を生成してもよい。他の隣接するノード間においても同様に、多重署名情報σ22-3、σ23-4、σ24-5、σ25-6、σ26-7、σ27-1、σ22-6、σ23-5、σ23-7及び多重検証鍵情報vm12-3、vm13-4、vm14-5、vm15-6、vm16-7、vm17-1、vm12-6、vm13-5、vm13-7を生成する。隣接する全てのノード間で多重署名情報及び多重検証鍵情報が生成されると、ノードr代表者urは、これらの多重署名情報σ2p-q及び多重検証鍵情報vm1p-qを回収する。そして、ノードrは、回収した全ての多重署名情報σ2p-qとノードrの固有署名情報uniσ2rとを足し合わせ、36~37式により公開多重署名情報σ2rを生成する。また、ノードrは、回収した全ての多重検証鍵情報vm1p-qとノードrの第1の検証鍵v1rとを足し合わせ、38~39式により公開多重検証鍵情報vm1rを生成する。そして、ノードrは、生成した公開多重署名情報σ2rと公開多重検証鍵情報vm1rを公開情報として公開する。また、検証ノード340は、以下の検証過程1から検証過程4により公開多重署名情報σ2rの正当性を検証する。検証過程1検証ノード340は、メッセージmに対してハッシュ値h2=H2mを求める。検証過程2検証ノード340は、メッセージmの署名を行った全ての一般ノード320と代表ノード330の検証鍵を収集する。検証過程3検証ノード340は、代表ノード330によって公開された公開多重検証鍵情報vm1rの正当性を検証する。具体的には、検証ノード340は、収集した全ての一般ノード320と代表ノード330の検証鍵から40式及び41式に示す演算を行い、41式とevm1r,g2とが一致することを確認し、これらの値が一致した場合には、公開多重検証鍵情報vm1rが正当であると判断する。検証過程4検証ノード340は、正当性が検証された公開多重検証鍵情報vm1rに基づいて公開多重署名情報σ2rの正当性を検証する。検証ノード340は、具体的には、eg1,σ2rとevm1r,h2を計算し、これらの値が一致することを確認し、これらの一致した場合には、公開多重署名情報σ2rが正当であると判断する。ここで、検証過程3におけるevm1r,g2の演算過程について説明する。なお、便宜上xは、42式と置く。x=xrx1x2x2x3x3x4x5x6x6x7x7x1x2x6x3x5x3x742なお、署名の過程が正しく行われていれば、41式と47式は、一致する。また、公開多重検証鍵情報vm1rを一つの検証鍵と見なせば、検証過程4による検証は、GDH署名の検証と同じ検証を行っていることになり、公開多重署名情報σ2rの検証が可能となる。なお、41式の第1項ev1r,g2は、eg1,v2rとしてもよい。この場合も、46式の右辺第1項は、eg1,xrg2と変形可能であるから、16式の右辺第1項は、eg1,v2rと変形され、41式と47式とは一致する。また、同様に、41式の全ての項において、集合G1に属する第1の検証鍵と集合G2に属する第2の検証鍵とを交換すると共に、ペアリングの順序を入れ替え可能である。また、42式の右辺に着目すると、任意の隣接する一般ノード320upとuqに対応してxpxqという積になっており、ノード間がどのような関係により署名されてきたかが表されている。さらに、右辺第1項は、代表ノード330の署名鍵xrのみで構成されている。よって、代表ノード330の署名者はurであることが分かる。このように、検証システム検証ノード340は、メッシュ構造上、どのような関係の下に署名されてきたのかを把握することができ、その結果として、代表ノード330を含んだメッシュ構造上の署名者の配置を把握することができる。また、42式については、CDH問題や楕円曲線上の離散対数問題から秘密情報である署名鍵を知らない第三者が、右辺の各項xr及びxpxqを任意に入れ替えることができないため、第三者による順序の入れ替えは不可能である。すなわち、検証システム検証ノード340が採用する本検証方式は、メッシュ構造上において連続隣接する二つのノード間の関係を署名鍵の積で表し、それを代表ノード330で全て集めることにより、メッシュ構造を表現することができる。また、ノードの数が増えても、公開されるのは、代表ノード330で生成される公開多重検証鍵情報vm1rと公開多重署名情報σ2rであり、これらは楕円曲線上の点であるため、各情報のサイズ容量は増大せず、一定値以下に抑制することができ、効率的に多重電子署名を生成することができる。本実施形態における多重署名システム及び検証システムは、例えば駅改札のネットワーク等、PtoPPeertoPeerの限定された範囲のネットワークの管理に利用することができる。すなわち、各ノード間にて署名された多重署名情報及び多重検証鍵情報を収集して正当性を検証することにより、限定された範囲のネットワークから外れた所に情報が漏洩していないかどうかを検証することができる。本実施形態では、42式において、署名鍵の値が一つのみの項がxrとなっており、代表ノード330が明示された上で、各ノードの隣接関係が示されている。本発明はこれには限られず、xrを用いずに、メッシュ構造内の各ノードの隣接関係のみを示してもよい。すなわち、代表ノード330は、隣接するノード間の多重署名情報の総和に対して、代表ノード330の固有署名情報uniσ2rを加算せずに公開する。また、代表ノード330は、隣接するノード間の多重検証鍵情報の総和に対して、代表ノード330の検証鍵v1rを加算せずに公開する。このことにより、41式及び47式の右辺第1項ev1r,g2はなくなる。また、上述の各実施形態において、ペアリング関数への入力である2つの引数は、ペアリングの演算が可能な楕円曲線上の点g1又はg2のスカラー倍として表されるが、この楕円曲線は、第1引数と第2引数とで異なっている。すなわち、ペアリング関数の第1引数用と第2引数用とに、それぞれ異なる楕円曲線G1又はG2上の2点g1又はg2が与えられている。具体的には、第1引数に関する検証鍵は、g1のスカラー倍G1上の点となり、第2引数に関するハッシュ値及び署名情報は、g2のスカラー倍G2上の点となる。このことにより、演算回数が増加する場合があるが、ペアリング関数の演算において並列して処理できるため、計算時間の短縮が期待できる。また、集合G1又はG2のいずれかに不具合が発見された場合、一方を共用する、又は他のGDHグループに交換することにより、多重署名システム及び検証システムが維持される。以上、本発明の実施形態について説明したが、本発明は上述した実施形態に限るものではない。また、本発明の実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、本発明の実施形態に記載されたものに限定されるものではない。また、多重署名システム及び検証システムによる一連の処理は、ソフトウェアにより行うこともできる。一連の処理をソフトウェアによって行う場合には、そのソフトウェアを構成するプログラムが、汎用のコンピュータ等にインストールされる。また、当該プログラムは、CD-ROMのようなリムーバブルメディアに記録されてユーザに配布されてもよいし、ネットワークを介してユーザのコンピュータにダウンロードされることにより配布されてもよい。"