"あるノードから別のノードへの順序付きのアグリゲート署名を行うアグリゲート署名システムであって、各ノードには、所定の自然数からなる署名鍵と、第1のGDHGAP-Diffie-Hellmanグループに属する第1の値に対して、当該署名鍵により演算を行って生成される当該第1のGDHグループに属する検証鍵とがそれぞれ割り当てられており、当該各ノードは、直前のノードが存在する場合、当該直前のノードの署名対象であるメッセージ又は当該メッセージのハッシュ値、及び当該直前のノードの署名情報を受信する受信部と、自身のメッセージと、前記直前のノードが存在する場合、当該直前のノードのメッセージとに対して、それぞれ一方向性ハッシュ関数演算を行って、各メッセージの第2のGDHグループに属するハッシュ値を生成する署名ノード一方向性ハッシュ関数演算部と、自身のメッセージのハッシュ値に対して自身の署名鍵により演算を行った結果と、前記直前のノードが存在する場合、当該直前のノードのメッセージのハッシュ値に対して自身のノードの署名鍵により演算を行った結果、及び前記直前のノードの署名情報とを総和して、自身の署名情報を生成する署名情報生成部と、直後のノードが存在する場合、自身のメッセージ又は当該メッセージのハッシュ値、及び自身の署名情報を、当該直後のノードへ送信する送信部と、を備えるアグリゲート署名システム。前記署名情報生成部は、前記直前のノードが複数存在する場合、自身のメッセージのハッシュ値に対して自身の署名鍵により演算を行った結果と、前記直前のノードそれぞれのメッセージのハッシュ値に対して自身のノードの署名鍵により演算を行った複数の結果と、前記直前のノードそれぞれの署名情報とを総和して、自身の署名情報を生成する請求項1に記載のアグリゲート署名システム。前記各ノードは、自身の署名情報を公開する公開部を備える請求項1又は請求項2に記載のアグリゲート署名システム。前記公開部は、前記各ノードの順序情報をさらに公開する請求項3に記載のアグリゲート署名システム。請求項3又は請求項4に記載のアグリゲート署名システムに備えられている前記公開部により公開された署名情報を検証する検証システムであって、前記公開された署名情報が生成される過程の全てのノードのメッセージ又は当該メッセージのハッシュ値、及び当該全てのノードの検証鍵を収集する収集部と、前記収集部により収集されたメッセージに対して、それぞれ一方向性ハッシュ関数演算を行って、各メッセージの前記第2のGDHグループに属するハッシュ値を生成する検証ノード一方向性ハッシュ関数演算部と、前記全てのノードの検証鍵、及び前記全てのノードのメッセージのハッシュ値に基づいて、前記公開された署名情報の正当性を検証する検証部と、を備える検証システム。前記検証部は、同一ノードの検証鍵及びハッシュ値によるペアリング演算の結果と、あるノードの検証鍵及び当該ノードの直前のノードのハッシュ値によるペアリング演算の結果とを全て乗じた値を、前記第1の値及び前記公開された署名情報によるペアリング演算の結果と比較し、双方が一致する場合、前記公開された署名情報が正当であると判定し、双方が一致しない場合、前記公開された署名情報が正当でないと判定する請求項5に記載の検証システム。あるノードから別のノードへの順序付きのアグリゲート署名を行うアグリゲート署名方法であって、各ノードには、所定の自然数からなる署名鍵と、第1のGDHGAP-Diffie-Hellmanグループに属する第1の値に対して、当該署名鍵により演算を行って生成される当該第1のGDHグループに属する検証鍵とがそれぞれ割り当てられており、当該各ノードが、第1のGDHGAP-Diffie-Hellmanグループに属する第1の値に対して、自身の署名鍵により演算を行って、当該第1のGDHグループに属する自身の検証鍵を生成する検証鍵生成工程と、直前のノードが存在する場合、当該直前のノードの署名対象であるメッセージ又は当該メッセージのハッシュ値、及び当該直前のノードの署名情報を受信する受信工程と、自身のメッセージと、前記直前のノードが存在する場合、当該直前のノードのメッセージとに対して、それぞれ一方向性ハッシュ関数演算を行って、各メッセージの第2のGDHグループに属するハッシュ値を生成する署名ノード一方向性ハッシュ関数演算工程と、自身のメッセージのハッシュ値に対して自身の署名鍵により演算を行った結果と、前記直前のノードが存在する場合、当該直前のノードのメッセージのハッシュ値に対して自身のノードの署名鍵により演算を行った結果、及び前記直前のノードの署名情報とを総和して、自身の署名情報を生成する署名情報生成工程と、直後のノードが存在する場合、自身のメッセージ又は当該メッセージのハッシュ値、及び自身の署名情報を、当該直後のノードへ送信する送信工程と、を実行するアグリゲート署名方法。あるノードから別のノードへの順序付きのアグリゲート署名を行うアグリゲート署名方法をコンピュータに実行させるためのアグリゲート署名プログラムであって、各ノードには、所定の自然数からなる署名鍵と、第1のGDHGAP-Diffie-Hellmanグループに属する第1の値に対して、当該署名鍵により演算を行って生成される当該第1のGDHグループに属する検証鍵とがそれぞれ割り当てられており、当該各ノードに、第1のGDHGAP-Diffie-Hellmanグループに属する第1の値に対して、自身の署名鍵により演算を行って、当該第1のGDHグループに属する自身の検証鍵を生成する検証鍵生成工程と、直前のノードが存在する場合、当該直前のノードの署名対象であるメッセージ又は当該メッセージのハッシュ値、及び当該直前のノードの署名情報を受信する受信工程と、自身のメッセージと、前記直前のノードが存在する場合、当該直前のノードのメッセージとに対して、それぞれ一方向性ハッシュ関数演算を行って、各メッセージの第2のGDHグループに属するハッシュ値を生成する署名ノード一方向性ハッシュ関数演算工程と、自身のメッセージのハッシュ値に対して自身の署名鍵により演算を行った結果と、前記直前のノードが存在する場合、当該直前のノードのメッセージのハッシュ値に対して自身のノードの署名鍵により演算を行った結果、及び前記直前のノードの署名情報とを総和して、自身の署名情報を生成する署名情報生成工程と、直後のノードが存在する場合、自身のメッセージ又は当該メッセージのハッシュ値、及び自身の署名情報を、当該直後のノードへ送信する送信工程と、を実行させるためのアグリゲート署名プログラム。しかしながら、これらの多重署名やグループ署名では署名者が全て等価な関係で表現される。したがって、一例として示した多重署名システムにおいて電子データがどのように流通してきたのかを、この署名方式だけで表現することができない。これに対し、順序や上下関係を証明する方式としては順序付き多重署名方式例えば、特許文献2、3を参照があげられる。これにより署名者の順番が保証され、個人の上下関係が表現できる。しかしながら、これら既存の順序付き多重署名方式は、RSARivestShamirAdleman問題ベースのものか、離散対数問題ベースのものが提案されている。RSA問題ベースでは、署名する人数が増えるほど署名サイズが大きくなってしまい、また、離散対数問題ベースでは、ゼロ知識証明を利用するために演算処理に負荷がかかり、効率的な処理にならない。また、両者共、同一のメッセージに対して複数人が署名を行う方式であるため、各署名者がそれぞれ異なるメッセージを対象とするアグリゲート署名を行うことができなかった。本発明は、上記課題を解決するため、署名する人数が増えても署名サイズを一定値に抑制し、かつ効率的な演算処理によって順序付き電子署名を行うことができるアグリゲート署名システム、検証システム、アグリゲート署名方法及びアグリゲート署名プログラムを提供することを目的とする。本発明では、以下のような解決手段を提供する。1本発明に係るアグリゲート署名システムは、上記課題を解決するために、あるノードから別のノードへの順序付きのアグリゲート署名を行うアグリゲート署名システムであって、各ノードには、所定の自然数からなる署名鍵と、第1のGDHGAP-Diffie-Hellmanグループに属する第1の値に対して、当該署名鍵により演算を行って生成される当該第1のGDHグループに属する検証鍵とがそれぞれ割り当てられており、当該各ノードは、以下の各部を備える。a直前のノードが存在する場合、当該直前のノードの署名対象であるメッセージ又は当該メッセージのハッシュ値、及び当該直前のノードの署名情報を受信する受信部。b自身のメッセージと、前記直前のノードが存在する場合、当該直前のノードのメッセージとに対して、それぞれ一方向性ハッシュ関数演算を行って、各メッセージの第2のGDHグループに属するハッシュ値を生成する署名ノード一方向性ハッシュ関数演算部。c自身のメッセージのハッシュ値に対して自身の署名鍵により演算を行った結果と、前記直前のノードが存在する場合、当該直前のノードのメッセージのハッシュ値に対して自身のノードの署名鍵により演算を行った結果、及び前記直前のノードの署名情報とを総和して、自身の署名情報を生成する署名情報生成部。d直後のノードが存在する場合、自身のメッセージ又は当該メッセージのハッシュ値、及び自身の署名情報を、当該直後のノードへ送信する送信部。このような構成によれば、アグリゲート署名システムは、各ノードにおいて、直前のノードのメッセージから得られたハッシュ値と、自身のメッセージから得られたハッシュ値とに対して、自身のノードに割り当てられている署名鍵によって演算を行い、さらに、直前のノードにより生成された署名情報を用いて、自身の署名情報を生成する。アグリゲート署名システムは、この署名情報により、各ノードに至るまでの署名順序を表現することができる。また、このように構成されることにより、アグリゲート署名システムは、署名鍵を知らない第三者がGDHグループの要素である楕円曲線上の点から署名鍵を求めることを、計算量的に困難にすることができる。また、署名者の数ノードの数が増えても、生成される署名情報は楕円曲線上の点であるため、署名情報のサイズ容量は増大せず一定値以下に抑制することができ、効率的にアグリゲート署名を生成することができる。2また、上記アグリゲート署名システムでは、前記署名情報生成部は、前記直前のノードが複数存在する場合、自身のメッセージのハッシュ値に対して自身の署名鍵により演算を行った結果と、前記直前のノードそれぞれのメッセージのハッシュ値に対して自身のノードの署名鍵により演算を行った複数の結果と、前記直前のノードそれぞれの署名情報とを総和して、自身の署名情報を生成することを特徴とする。このような構成によれば、アグリゲート署名システムは、各ノードにおいて、直前の一又は複数のノードのメッセージから得られたハッシュ値それぞれと、自身のメッセージから得られたハッシュ値とに対して、自身のノードに割り当てられている署名鍵によって演算を行い、さらに直前のノードにより生成された署名情報を用いて、自身の署名情報を生成する。アグリゲート署名システムは、この署名情報により、各ノードに至るまでの木構造における署名順序を表現することができる。なお、木構造とは、対称か非対称かを問わず、任意の構造を持つ木構造全てを指す。本発明は、この任意の構造を持つ木構造に対して適応可能である。3また、上記アグリゲート署名システムでは、前記各ノードは、自身の署名情報を公開する公開部を備えることを特徴とする。このような構成によれば、各ノードは、順序付きのアグリゲート署名である署名情報を他のノードに対して公開することができる。4また、上記アグリゲート署名システムでは、前記公開部は、前記各ノードの順序情報をさらに公開することを特徴とする。このような構成によれば、各ノードは、署名情報と共に、この署名情報が生成されるまでの過程で署名が行われたノードの順序を公開することができる。5本発明に係る検証システムは、上記課題を解決するために、上記アグリゲート署名システムに備えられている前記公開部により公開された署名情報を検証する検証システムであって、前記公開された署名情報が生成される過程の全てのノードのメッセージ又は当該メッセージのハッシュ値、及び当該全てのノードの検証鍵を収集する収集部と、前記収集部により収集されたメッセージに対して、それぞれ一方向性ハッシュ関数演算を行って、各メッセージの前記第2のGDHグループに属するハッシュ値を生成する検証ノード一方向性ハッシュ関数演算部と、前記全てのノードの検証鍵、及び前記全てのノードのメッセージのハッシュ値に基づいて、前記公開された署名情報の正当性を検証する検証部と、を備える。このような構成によれば、検証システムは、検証部により全てのノードの検証鍵とメッセージのハッシュ値とに基づいて、公開された署名情報の正当性を検証する。よって、検証システムでは、各ノードにて生成される個々の署名情報等を検証することなく、公開された署名情報を検証することにより、署名順序を証明することができる。すなわち、検証システムでは、検証ノードの処理負荷を低減して検証作業を実行することができる。6また、上記検証システムでは、前記検証部は、同一ノードの検証鍵及びハッシュ値によるペアリング演算の結果と、あるノードの検証鍵及び当該ノードの直前のノードのハッシュ値によるペアリング演算の結果とを全て乗じた値を、前記第1の値及び前記公開された署名情報によるペアリング演算の結果と比較し、双方が一致する場合、前記公開された署名情報が正当であると判定し、双方が一致しない場合、前記公開された署名情報が正当でないと判定することを特徴とする。このような構成によれば、検証システムは、ペアリング演算を用いたGDH署名により、順序付きアグリゲート署名の正当性を、効率的な演算処理で検証できる。7本発明に係るアグリゲート署名方法は、上記課題を解決するために、あるノードから別のノードへの順序付きのアグリゲート署名を行うアグリゲート署名方法であって、各ノードには、所定の自然数からなる署名鍵と、第1のGDHGAP-Diffie-Hellmanグループに属する第1の値に対して、当該署名鍵により演算を行って生成される当該第1のGDHグループに属する検証鍵とがそれぞれ割り当てられており、当該各ノードが以下の各工程を実行する。a直前のノードが存在する場合、当該直前のノードの署名対象であるメッセージ又は当該メッセージのハッシュ値、及び当該直前のノードの署名情報を受信する受信工程。b自身のメッセージと、前記直前のノードが存在する場合、当該直前のノードのメッセージとに対して、それぞれ一方向性ハッシュ関数演算を行って、各メッセージの第2のGDHグループに属するハッシュ値を生成する署名ノード一方向性ハッシュ関数演算工程。c自身のメッセージのハッシュ値に対して自身の署名鍵により演算を行った結果と、前記直前のノードが存在する場合、当該直前のノードのメッセージのハッシュ値に対して自身のノードの署名鍵により演算を行った結果、及び前記直前のノードの署名情報とを総和して、自身の署名情報を生成する署名情報生成工程。d直後のノードが存在する場合、自身のメッセージ又は当該メッセージのハッシュ値、及び自身の署名情報を、当該直後のノードへ送信する送信工程。8本発明に係るアグリゲート署名プログラムは、上記課題を解決するために、あるノードから別のノードへの順序付きのアグリゲート署名を行うアグリゲート署名方法をコンピュータに実行させるためのアグリゲート署名プログラムであって、各ノードには、所定の自然数からなる署名鍵と、第1のGDHGAP-Diffie-Hellmanグループに属する第1の値に対して、当該署名鍵により演算を行って生成される当該第1のGDHグループに属する検証鍵とがそれぞれ割り当てられており、当該各ノードに、以下の各工程を実行させる。a直前のノードが存在する場合、当該直前のノードの署名対象であるメッセージ又は当該メッセージのハッシュ値、及び当該直前のノードの署名情報を受信する受信工程。b自身のメッセージと、前記直前のノードが存在する場合、当該直前のノードのメッセージとに対して、それぞれ一方向性ハッシュ関数演算を行って、各メッセージの第2のGDHグループに属するハッシュ値を生成する署名ノード一方向性ハッシュ関数演算工程。c自身のメッセージのハッシュ値に対して自身の署名鍵により演算を行った結果と、前記直前のノードが存在する場合、当該直前のノードのメッセージのハッシュ値に対して自身のノードの署名鍵により演算を行った結果、及び前記直前のノードの署名情報とを総和して、自身の署名情報を生成する署名情報生成工程。d直後のノードが存在する場合、自身のメッセージ又は当該メッセージのハッシュ値、及び自身の署名情報を、当該直後のノードへ送信する送信工程。本発明によれば、署名する人数が増えても署名サイズを一定値に抑制し、かつ効率的な演算処理によって順序付きアグリゲート署名を行うことができる。<第1実施形態>以下、本発明の実施形態の一例である第1実施形態について説明する。本実施形態に係るアグリゲート署名システムは、複数のノードが木構造状に構成され、これら複数のノードで独立したメッセージに対して、下位のノードから順に順序付きの多重署名を行うシステムである。また、最上位のルートノードにより公開された署名情報は、検証システムにおける検証ノードにより正当性が検証される。ところで、各ノードには、予め重複しない署名鍵と検証鍵とが認証局CAによってそれぞれ割り当てられている。署名鍵は、所定の自然数xからなり、検証鍵は、GDHGAP-Diffie-HellmanグループG1の要素である楕円曲線上の点g1と固有署名鍵xとに基づいて生成される楕円曲線上の点v=xg1からなることが好ましい。このように構成されることにより、署名鍵xを知らない第三者がvやg1の値から署名鍵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の値から署名σを導出することは不可能である。木構造における最下位ノードであるリーフノード10は、図1に示すように、記憶部11と、リーフノード一方向性ハッシュ関数演算部12と、リーフノード署名情報生成部13と、リーフノード送信部14とを備える。記憶部11は、自身署名者uleafのノードに割り当てられている署名鍵xleafと、集合G1に属する値g1第1の値に対して、この署名鍵により演算を行って生成される集合G1に属する検証鍵vleaf=xleafg1とを記憶する。リーフノード一方向性ハッシュ関数演算部12は、自身の署名対象であるメッセージmleafに対して、一方向性ハッシュ関数演算を行って、集合G2第2のGDHグループに属するハッシュ値を生成する。リーフノード署名情報生成部13は、リーフノード一方向性ハッシュ関数演算部12により演算された、自身の署名対象であるメッセージmleafのハッシュ値hleaf=H2mleafに対して自身の署名鍵xleafにより演算を行い、署名情報σleaf=xleafhleafを生成する。リーフノード送信部14は、生成した署名情報σleafとメッセージmleafとを次直上のノード、すなわち中間ノード20へ送信する。また、木構造における最下位リーフノード10より上のノードである中間ノード20は、図2に示すように、記憶部21と、中間ノード受信部22と、中間ノード一方向性ハッシュ関数演算部23と、中間ノード署名情報生成部24と、中間ノード送信部25と、を備える。記憶部21は、自身署名者uupのノードに割り当てられている署名鍵xupと、集合G1に属する値g1に対して、この署名鍵により演算を行って生成される集合G1に属する検証鍵vup=xupg1とを記憶する。中間ノード受信部22は、直下の一又は複数のノード署名者ulowのノードの署名対象であるメッセージmlowと、これら直下のノードにより生成された署名情報σlowと、を受信する。中間ノード一方向性ハッシュ関数演算部23は、直下のノードから受信したメッセージmlowのそれぞれと、自身の署名対象であるメッセージmupとに、それぞれ一方向性ハッシュ関数演算を行って、集合G2に属するハッシュ値を生成する。中間ノード署名情報生成部24は、自身のメッセージmupから得られたハッシュ値hup=H2mupに対して自身の固有署名鍵xupにより演算を行った結果と、直下のノードのメッセージmlowそれぞれから得られたハッシュ値hlow=H2mlowに対して自身の固有署名鍵xupにより演算を行った結果と、直下のノードの署名情報σlowとを総和して、自身の中間ノード署名情報σup=Σlowσlowxuphlowxuphupを生成するΣlowは、直下の一又は複数のノード全てについての総和を示す。中間ノード送信部25は、次直上のノードが存在する場合に、自身の署名対象であるメッセージmupと、中間ノード署名情報σupとを、次のノードへ送信する。このような構成によれば、アグリゲート署名システムは、各中間ノード20において、直下のノードのメッセージから得られたハッシュ値と、自身のメッセージから得られたハッシュ値とに対して、自身のノードに割り当てられている署名鍵によって演算を行い、さらに直下のノードにより生成された署名情報を総和して、中間ノード署名情報を生成する。この署名情報は、自身のノードに至るまでの木構造における署名経路を保持し、かつ楕円曲線上の点のみで生成される。すなわち、署名者ノードの数が多くなっても、署名サイズは増大せず、一定値以下に抑制することができる。また、木構造における最上位の中間ノードであるルートノード30は、図3に示すように、記憶部31と、ルートノード受信部32と、ルートノード一方向性ハッシュ関数演算部33と、ルートノード署名情報生成部34と、公開部35とを備える。記憶部31は、自身署名者urootのノードに割り当てられている署名鍵xrootと、集合G1に属する値g1に対して、この署名鍵により演算を行って生成される集合G1に属する検証鍵vroot=xrootg1を記憶する。なお、ルートノード受信部32は、中間ノード受信部22と同一の構成であり、ルートノード一方向性ハッシュ関数演算部33は、中間ノード一方向性ハッシュ関数演算部23と同一の構成であり、ルートノード署名情報生成部34は、中間ノード署名情報生成部24と同一の構成である。公開部35は、ルートノード署名情報生成部34により生成されたルートノード署名情報を公開する。このような構成によれば、ルートノード30は、自身が生成した署名情報σrootを他のノード、特に後述の検証システムにおける検証ノード40に対して公開署名情報σとして公開することができる。また、公開部35は、署名順序を示す木構造内における署名者の配置、及び各署名者と署名を行ったメッセージとの対応関係に関する情報も公開する。次に、ルートノード30により公開された公開署名情報σを検証する検証システムについて説明する。検証システムが有する検証ノード40は、図4に示すように、収集部41と、検証ノード一方向性ハッシュ関数演算部42と、検証部43とを備える。収集部41は、署名を行った全てのノードリーフノード10、中間ノード20、ルートノード30それぞれのメッセージmiと、検証鍵viとを収集する。このとき、収集部41は、木構造内における署名者の配置、及び各署名者と署名を行ったメッセージとの対応関係に関する情報を、必ずしも入手しなくてもよいが、ルートノード30から入手するようにしておくことも好ましい。収集部41がこれらの情報を入手しない場合でも、検証部43は、署名者の配置、及び各署名者と署名を行ったメッセージとの対応関係に関して、全ての組み合わせを演算することにより、公開署名情報の正当性を検証することが可能である。しかし、収集部41がこれらの情報を入手し検証部43へ受け渡すようにしておくと、これらの情報がない場合に比べて検証部43の演算量が少なくてすむ。検証ノード一方向性ハッシュ関数演算部42は、収集部41により収集された各メッセージmiに対して、それぞれ一方向性ハッシュ関数演算を行って、各メッセージの集合G2に属するハッシュ値hi=H2miを生成する。検証部43は、収集部41により収集された全てのノードの検証鍵と、検証ノード一方向性ハッシュ関数演算部42により得られたハッシュ値と、署名者の配置、及び各署名者と署名を行ったメッセージとの対応関係に関する情報と、に基づいて、公開署名情報σの正当性を検証する。このとき、検証部43は、署名者の配置、及び各署名者と署名を行ったメッセージとの対応関係に関する情報がない場合、これらの対応関係に関する全ての組み合わせを演算する。具体的には、検証部43は、各ノードの検証鍵とハッシュ値とから、同一ノードの検証鍵及びハッシュ値によるペアリング演算の結果と、あるノードの検証鍵及び直前のノードのハッシュ値によるペアリング演算の結果とを全て乗じた値、すなわち、{Πall-nodeevi,hi}{Πevup,hlow}を計算する。そして、検証部43は、この計算結果を、g1及び公開署名情報σによるペアリング演算の結果、すなわち、eg1,σと比較し、双方が一致する場合、公開署名情報が正当であると判定し、双方が一致しない場合、公開署名情報が正当でないと判定する。このようにして検証ノード40は、検証部43により、全てのノードの検証鍵と、メッセージのハッシュ値と、署名者の配置、及び各署名者と署名を行ったメッセージとの対応関係に関する情報と、に基づいて、公開されているルートノード30の署名情報の正当性を検証することができる。ここで、署名者の配置、及び各署名者と署名を行ったメッセージとの対応関係に関する情報については、これらの情報がなくても、検証部43は、署名情報の正当性を検証することが可能である。したがって、検証システムでは、各ノードにて生成される個々の署名情報等を検証することなく、ルートノード30により公開された署名情報を数値演算のみで検証することにより、木構造におけるノード間をどのような順序で署名されてきたかを証明することができる。すなわち、順序管理のための別の装置を要することなく、検証ノード40の処理負荷を低減して効率的に検証作業を実行することができる。なお、検証ノード40は、検証専用のノードであってもよいし、アグリゲート署名システムのいずれかの中間ノード20やルートノード30であってもよい。次に、アグリゲート署名システムにおいて、各ノードの署名情報を生成する方法と、検証システムにおいて、署名情報の正当性を検証する方法について説明する。リーフノード10署名者uleafは、図5に示すように、リーフノード一方向性ハッシュ関数演算工程ST1と、リーフノード署名情報生成工程ST2と、リーフノード送信工程ST3とにより、リーフノード署名情報を生成して直上のノード中間ノード20へ送信する。リーフノード一方向性ハッシュ関数演算工程ST1において、リーフノード10におけるリーフノード一方向性ハッシュ関数演算部12は、自身のメッセージmleafに対して、一方向性ハッシュ関数演算を行う。リーフノード署名情報生成工程ST2において、リーフノード10におけるリーフノード署名情報生成部13は、リーフノード一方向性ハッシュ関数演算工程ST1により演算されたハッシュ値hleafに対して、自身の署名鍵xleafにより演算を行い、署名情報σleafを生成する。リーフノード送信工程ST3において、リーフノード10におけるリーフノード送信部14は、リーフノード署名情報生成工程ST2により生成された署名情報σleafを、直上の中間ノード20へ送信する。リーフノード10以外の中間ノード20署名者uupは、図6に示すように、中間ノード受信工程ST11と、中間ノード一方向性ハッシュ関数演算工程ST12と、中間ノード署名情報生成工程ST13と、中間ノード送信工程ST14とにより、中間ノード署名情報を生成して直上の中間ノード20へ送信する。中間ノード受信工程ST11において、署名者uupのノードにおける中間ノード受信部22は、直下のノード署名者ulowのメッセージmlow、及び直下のノードにより生成された署名情報σlowを受信する。中間ノード一方向性ハッシュ関数演算工程ST12において、署名者uupのノードにおける中間ノード一方向性ハッシュ関数演算部23は、直下のノードのメッセージmlow及び自身のメッセージmlowに対して、それぞれ一方向性ハッシュ関数演算を行う。中間ノード署名情報生成工程ST13において、署名者uupのノードにおける中間ノード署名情報生成部24は、自身のメッセージから演算により得られたハッシュ値hupに対して自身の署名鍵xupにより演算を行った結果と、直下のノードのメッセージから演算により得られたハッシュ値hlowに対して自身の署名鍵xupにより演算を行った結果と、直下のノードから受信した署名情報σlowとを総和して、自身のノードの署名情報σupを生成する。中間ノード送信工程ST14において、署名者uupのノードにおける中間ノード送信部25は、木構造における直上のノードが存在する場合に、自身のメッセージmup及び自身のノードの署名情報σupを、直上のノードへ送信する。また、木構造における最上位のノードであるルートノード30署名者urootは、図7に示すように、ルートノード受信工程ST21と、ルートノード一方向性ハッシュ関数演算工程ST22と、ルートノード署名情報生成工程ST23と、署名情報公開工程ST24とにより、アグリゲート署名システムにおける公開署名情報σを公開する。ルートノード受信工程ST21において、ルートノード30におけるルートノード受信部32は、直下のノード署名者ulowのメッセージmlow、及び直下のノードにより生成された署名情報σlowを受信する。ルートノード一方向性ハッシュ関数演算工程ST22において、ルートノード30におけるルートノード一方向性ハッシュ関数演算部33は、直下のノードのメッセージmlow及び自身のメッセージmrootに対して、それぞれ一方向性ハッシュ関数演算を行う。ルートノード署名情報生成工程ST23において、ルートノード30におけるルートノード署名情報生成部34は、自身のメッセージから演算により得られたハッシュ値hrootに対して自身の署名鍵xrootにより演算を行った結果と、直下のノードのメッセージから演算により得られたハッシュ値hlowに対して自身の署名鍵xrootにより演算を行った結果と、直下のノードから受信した署名情報σlowとを総和して、自身のノードの署名情報σrootを生成する。署名情報公開工程ST24において、ルートノード30における公開部35は、ルートノード署名情報生成工程ST23により生成された署名情報を、公開署名情報σとして公開する。このように、アグリゲート署名システムに係るアグリゲート署名方法によれば、各中間ノード20において、直下のノードのメッセージから得られたハッシュ値と、自身のメッセージから得られたハッシュ値とに対して、自身のノードに割り当てられている署名鍵によって演算を行い、さらに直下のノードにより生成された署名情報を総和して、中間ノード署名情報を生成する。この署名情報は、自身のノードに至るまでの署名経路を保持し、かつ楕円曲線上の点のみで生成される。すなわち、署名者ノードの数が多くなっても、署名サイズは増大せず、一定値以下に抑制することができる。また、検証システムにおける検証ノード40は、図8に示すように、収集工程ST31と、検証ノード一方向性ハッシュ関数演算工程ST32と、検証工程ST33とにより、公開署名情報σの正当性を検証する。収集工程ST31において、収集部41は、署名が行われた全てのノードのメッセージmi、及びこれら全てのノードの検証鍵viを収集する。検証ノード一方向性ハッシュ関数演算工程ST32において、検証ノード一方向性ハッシュ関数演算部42は、収集工程ST31により収集されたメッセージのそれぞれに対して、一方向性ハッシュ関数演算を行う。検証工程ST33において、検証部43は、収集工程ST31により収集された全てのノードの検証鍵、及び全てのノードのメッセージから検証ノード一方向性ハッシュ関数演算工程ST32で得られたハッシュ値に基づいて、公開署名情報σの正当性を検証する。このようにして、検証システムは、検証工程ST33により、全てのノードの検証鍵とメッセージのハッシュ値とに基づいて、公開されている中間ノード署名情報公開署名情報σの正当性を検証することができる。したがって、検証システムに係る検証方法では、各ノードにて生成される個々の署名情報等を検証することなく、ルートノード30により公開された署名情報を数値演算のみで検証することにより、木構造におけるノード間をどのような順序で署名されてきたかを証明することができる。すなわち、順序管理のための別の装置を要することなく、検証工程ST33の処理負荷を低減して検証作業を実行することができる。[実施例]ここで、木構造が3分木3階層で構成されている場合におけるアグリゲート署名システムの動作について図9を参照しながら具体的に説明する。なお、以下では、第1層をルートノード30であるとし、第2層を中間ノード20とし、第3層をリーフノード10とする。すなわち、第1層には、一つのルートノード30が配置されている。また、第2層には、三つの中間ノード20が配置され、urootの直下にu1からu3が配置されている。また、第3層には、九つのリーフノード10が配置され、u1の直下にu11からu13が配置され、u2の直下にu21からu23が配置され、u3の直下にu31からu33が配置されている。また、認証局CAは、予め各ノードに重複しない署名鍵と検証鍵を、以下のように付与している。なお、sとtはそれぞれ、1≦s≦3、1≦t≦3となる整数の符号である。第1層:署名鍵,検証鍵=xroot,vroot=xroot,xrootg1第2層:署名鍵,検証鍵=xs,vs=xs,xsg1第3層:署名鍵,検証鍵=xst,vst=xst,xstg1第3層の九つのリーフノード10ユーザustは、自身の署名対象であるメッセージmstに対してハッシュ値hst=H2mstを求め、ハッシュ値に対して自身の署名鍵xstにより演算を行い、署名情報σst=xsthstを生成する。また、リーフノード10ユーザustは、生成した署名情報σstと、メッセージmstとを直上のノードユーザusに送信する。第2層の三つの中間ノード20ユーザusは、まず自身の署名対象であるメッセージmsから、ハッシュ値hs=H2msを求める。次に、中間ノード20ユーザusは、直下のノードユーザus1、us2、us3から受信したメッセージms1、ms2、ms3から、ハッシュ値hs1=H2ms1、hs2=H2ms2、hs3=H2ms3を求める。さらに、中間ノード20ユーザusは、直下のノードから受信した署名情報σs1、σs2、σs3を用いて、σs=σs1xshs1σs2xshs2σs3xshs3xshs6=xs1hs1xshs1xs2hs2xshs2xs3hs3xshs3xshs7を計算する。そして、中間ノード20ユーザusは、生成した署名情報σsと、メッセージmsとを直上のノードユーザurootに送信する。第1層のルートノード30ユーザurootは、まず自身の署名対象であるメッセージmrootから、ハッシュ値hroot=H2mrootを求める。次に、ルートノード30ユーザurootは、直下のノードユーザu1、u2、u3から受信したメッセージm1、m2、m3から、ハッシュ値h1=H2m1、h2=H2m2、h3=H2m3を求める。さらに、ルートノード30ユーザurootは、直下のノードから受信した署名情報σ1、σ2、σ3を用いて、σ=σ1xrooth1σ2xrooth2σ3xrooth3xroothroot8=x11h11x1h11x12h12x1h12x13h13x1h13x1h1xrooth1x21h21x2h21x22h22x2h22x23h23x2h23x2h2xrooth2x31h31x3h31x32h32x3h32x33h33x3h33x3h3xrooth3xroothroot9を計算する。そして、ルートノード30ユーザurootは、生成した署名情報σを、全ユーザのアグリゲート署名情報として公開する。また、ルートノード30は、署名者の木構造における署名位置情報も公開する。署名位置情報は、例えば、{u11,u1,u12,u1,u13,u1,u21,u2,u22,u2,u23,u2,u31,u3,u32,u3,u33,u3,u1,uroot,u2,uroot,u3,uroot}のように、隣接するノードの組み合わせの列として表現される。このようにして、アグリゲート署名システムは、木構造上において連続隣接する2つのノード間の関係を署名鍵とハッシュ値の積で表すことにより、木構造を表現することができる。また、ノードの数が増えても、公開されるのは、ルートノード30で生成される公開署名情報σである。この署名情報は楕円曲線上の点であるため、情報のサイズ容量は増大せず、一定値以下に抑制することができ、効率的に順序付きアグリゲート署名を生成することができる。また、検証ノード40は、以下の検証過程1から検証過程3により公開署名情報σの正当性を検証する。検証過程1検証ノード40は、署名を行った全てのノードが署名対象としたメッセージmroot、m1、m2、m3、m11、m12、m13、m21、m22、m23、m31、m32、m33を収集し、これらに対してハッシュ値hroot=H2mroot、h1=H2m1、h2=H2m2、h3=H2m3、h11=H2m11、h12=H2m12、h13=H2m13、h21=H2m21、h22=H2m22、h23=H2m23、h31=H2m31、h32=H2m32、h33=H2m33を求める。検証過程2検証ノード40は、署名を行った全てのノードの検証鍵vroot、v1、v2、v3、v11、v12、v13、v21、v22、v23、v31、v32、v33を収集する。検証過程3検証ノード40は、公開された公開署名情報σの正当性を検証する。具体的には、検証ノード40は、検証過程1で求めたハッシュ値と、収集した全てのノードの検証鍵とから、ev11,h11ev1,h11ev12,h12ev1,h12ev13,h13ev1,h13ev1,h1evroot,h1ev21,h21ev2,h21ev22,h22ev2,h22ev23,h23ev2,h23ev2,h2evroot,h2ev31,h31ev3,h31ev32,h32ev3,h32ev33,h33ev3,h33ev3,h3evroot,h3evroot,hroot10を計算し、この値とeg1,σの値が一致することを確認する。これらの値が一致した場合には、公開署名情報σが正当であると判断する。ここで、検証過程3におけるeg1,σを展開すると、eg1,σ=eg1,x11h11eg1,x1h11eg1,x12h12eg1,x1h12eg1,x13h13eg1,x1h13eg1,x1h1eg1,xrooth1eg1,x21h21eg1,x2h21eg1,x22h22eg1,x2h22eg1,x23h23eg1,x2h23eg1,x2h2eg1,xrooth2eg1,x31h31eg1,x3h31eg1,x32h32eg1,x3h32eg1,x33h33eg1,x3h33eg1,x3h3eg1,xrooth3eg1,xroothroot11=ex11g1,h11ex1g1,h11ex12g1,h12ex1g1,h12ex13g1,h13ex1g1,h13ex1g1,h1exrootg1,h1ex21g1,h21ex2g1,h21ex22g1,h22ex2g1,h22ex23g1,h23ex2g1,h23ex2g1,h2exrootg1,h2ex31g1,h31ex3g1,h31ex32g1,h32ex3g1,h32ex33g1,h33ex3g1,h33ex3g1,h3exrootg1,h3exrootg1,hroot12=ev11,h11ev1,h11ev12,h12ev1,h12ev13,h13ev1,h13ev1,h1evroot,h1ev21,h21ev2,h21ev22,h22ev2,h22ev23,h23ev2,h23ev2,h2evroot,h2ev31,h31ev3,h31ev32,h32ev3,h32ev33,h33ev3,h33ev3,h3evroot,h3evroot,hroot13となり、署名の過程が正しく行われていれば、10式と一致する。よって、公開されているユーザの検証鍵と、全てのメッセージから求めたハッシュ値とから、アグリゲート署名の検証が可能となる。ここで、σの値に着目すると、ユーザustはhstにのみ署名処理xsthstの演算を行っており、他のhs及びhrootにはこのような署名処理を行っていない。これにより、ユーザustが最初、すなわち木構造におけるリーフノード10の署名者であることが分かる。また、xshstの項により、この最初の署名者が署名処理したhstに対して署名処理を行っているのがユーザusであることが表されているので、このユーザusが2番目中間ノード20の署名者であることが分かる。ユーザusは同時にhsに対して署名処理xshsを行っている。同様にxroothsの項により、このhsに対して署名処理を行っているのがユーザurootであることが表されているので、このユーザurootが3番目の署名者であることが分かる。さらに、hrootに対して署名処理を行っているユーザはなく、ユーザurootで収束しているため、この3番目の署名者がルートノード30であることが分かる。また、11式において、CDH問題や楕円曲線上の離散対数問題から、秘密情報である署名鍵を知らない第三者が、右辺の各項xαhβ又はxβhβを任意に取り除くことはできないため、第三者による順序の入れ替えは不可能である。すなわち、アグリゲート署名システム及び検証システムが採用する本署名方式は、木構造における署名順序を署名鍵とハッシュ値の積により表現することができる。また、署名者の数ノードの数が増えても、公開される情報は公開署名情報σのみである。この公開署名情報σは一つの楕円曲線上の点であるため、情報のサイズ容量は増大せず、一定値以下に抑制することができる。さらに、検証システムでは、検証過程3で示した数値演算のみで検証することにより、ノード間をどのような順序で署名されてきたかを証明することができる。したがって、順序管理のための装置を別途用意することなく、検証システムの処理負荷を低減して効率的に検証作業を実行することができる。<第2実施形態>以下、本発明の実施形態の一例である第2実施形態について説明する。なお、第1実施形態と同様の構成については、同一の符号を付し、説明を省略又は簡略化する。本実施形態に係るアグリゲート署名システムにおいて、リーフノード10は、リーフノード一方向性ハッシュ関数演算部12及びリーフノード送信部14の構成が第1実施形態と異なる。すなわち、リーフノード送信部14は、リーフノード一方向性ハッシュ関数演算部12の演算結果であるハッシュ値hleafとリーフノード署名情報σleafとを、直上のノード中間ノード20へ送信する。中間ノード20は、中間ノード受信部22、中間ノード一方向性ハッシュ関数演算部23、及び中間ノード送信部25の構成が第1実施形態と異なる。すなわち、中間ノード受信部22は、直下のノードから、メッセージmlowの代わりにハッシュ値hlowを受信して中間ノード署名情報生成部24へ供給する。これにより、中間ノード20は、直前のノードのメッセージmlowに対して一方向性ハッシュ関数演算を行う必要がなくなる。また、中間ノード送信部25は、中間ノード一方向性ハッシュ関数演算部23の演算結果であるハッシュ値hupと中間ノード署名情報σupとを、直上のノードへ送信する。ルートノード30は、ルートノード受信部32及びルートノード一方向性ハッシュ関数演算部33の構成が第1実施形態と異なる。すなわち、ルートノード受信部32は、直下のノードから、メッセージmlowの代わりにハッシュ値hlowを受信してルートノード署名情報生成部34へ供給する。これにより、ルートノード30は、直下のノードのメッセージmlowに対して一方向性ハッシュ関数演算を行う必要がなくなる。本実施形態に係る検証システムにおいて、検証ノード40は、収集部41の構成が第1実施形態と異なる。さらに、検証ノード40は、第1実施形態における検証ノード一方向性ハッシュ関数演算部42を必要としない。すなわち、収集部41は、各ノードから、メッセージmiの代わりにハッシュ値hiを受信して検証部43へ供給する。これにより、検証ノード40は、各ノードのメッセージmiに対して一方向性ハッシュ関数演算を行う必要がなくなる。本実施形態によれば、各ノードにおける一方向性ハッシュ関数演算の処理負荷を低減することができる。具体的には、第1実施形態における中間ノード一方向性ハッシュ関数演算工程ST12と、ルートノード一方向性ハッシュ関数演算工程ST22の処理負荷が低減され、検証ノード一方向性ハッシュ関数演算工程ST32は不要となる。なお、各ノード間においては、メッセージmi又はハッシュ値hiのいずれかが送受信されればよく、アグリゲート署名システム及び検証システム内において統一されていなくてもよい。また、メッセージ及びハッシュ値の双方を送受信することとしてもよい。以上で説明した各実施形態におけるアグリゲート署名システム及び検証システムは、各ノードで独立したメッセージを署名対象とするので、例えば署名済みの素材を集めてコンテンツを生成する場合のように、下位部分から上位全体へのボトムアップの署名方式を提供することができる。また、上述の各実施形態において、ペアリング関数への入力である2つの引数は、ペアリングの演算が可能な楕円曲線上の点g1又はg2のスカラー倍として表されるが、この楕円曲線は、第1引数と第2引数とで異なっている。すなわち、ペアリング関数の第1引数用と第2引数用とに、それぞれ異なる楕円曲線G1又はG2上の2点g1又はg2が与えられている。具体的には、第1引数に関する検証鍵は、g1のスカラー倍G1上の点となり、第2引数に関するハッシュ値及び署名情報は、g2のスカラー倍G2上の点となる。このことにより、演算回数が増加する場合があるが、ペアリング関数の演算において並列して処理できるため、計算時間の短縮が期待できる。また、集合G1又はG2のいずれかに不具合が発見された場合、一方を共用する、又は他のGDHグループに交換することにより、アグリゲート署名システム及び検証システムが維持される以上、本発明の実施形態について説明したが、本発明は上述した実施形態に限るものではない。また、本発明の実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、本発明の実施形態に記載されたものに限定されるものではない。上述の実施形態では、ルートノード30が公開部35を備えているが、他のノード中間ノード20、リーフノード10も備えていてよい。この場合、検証ノード40は、公開された署名情報に基づいて、公開したノードに至るまでの署名経路の正当性を検証可能である。さらに、各ノードの公開部35は、自身のノードの検証鍵を公開し、検証ノード40へ提供してもよい。また、上述の実施形態では、署名鍵及び検証鍵は、認証局によって割り当てられることとしたが、本発明はこれには限られない。例えば、アグリゲート署名システムにおいて、署名鍵となる自然数x、及び集合G1に属する値g1を決定し、検証鍵を演算により算出v=xg1してもよい。また、上述の実施形態では、中間ノード20に対して直下のノードが複数存在する木構造における順序付き多重署名について説明したが、本発明はこれには限られない。すなわち、中間ノード20に対して直下のノードが単一であり、複数のノードが一列に連なっている場合にも、本発明は適用可能である。この場合、アグリゲート署名システム及び検証システムは、各ノードで独立したメッセージを署名対象とするので、例えば電子掲示板やブログのコメント等のように、前のメッセージを受けて次のメッセージを追加する連作に対して利用することができる。なお、この場合、ルートノード30最終ノードが公開する署名者の署名順序情報署名位置情報は、例えば、{1,u1,2,u2,,k,uk}のように、順序番号を付加したノードの列として表現される。また、アグリゲート署名システム及び検証システムによる一連の処理は、ソフトウェアにより行うこともできる。一連の処理をソフトウェアによって行う場合には、そのソフトウェアを構成するプログラムが、汎用のコンピュータ等にインストールされる。また、当該プログラムは、CD-ROMのようなリムーバブルメディアに記録されてユーザに配布されてもよいし、ネットワークを介してユーザのコンピュータにダウンロードされることにより配布されてもよい。"