アグリゲート署名システム、検証システム、アグリゲート署名方法及びアグリゲート署名プログラム
【課題】署名する人数が増えても署名サイズを一定値に抑制し、かつ効率的な演算処理によって順序付き電子署名を行うことができるアグリゲート署名システム、検証システム、アグリゲート署名方法及びアグリゲート署名プログラムを提供すること。
【解決手段】アグリゲート署名システムは、各ノードにおいて、直前のノードのメッセージから得られたハッシュ値と、自身のメッセージから得られたハッシュ値とに対して、自身のノードに割り当てられている署名鍵によって演算を行い、さらに、直前のノードにより生成された署名情報を用いて、自身の署名情報を生成する。
【解決手段】アグリゲート署名システムは、各ノードにおいて、直前のノードのメッセージから得られたハッシュ値と、自身のメッセージから得られたハッシュ値とに対して、自身のノードに割り当てられている署名鍵によって演算を行い、さらに、直前のノードにより生成された署名情報を用いて、自身の署名情報を生成する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子署名を利用した電子データのアグリゲート署名システム、検証システム、アグリゲート署名方法及びアグリゲート署名プログラムに関する。
【背景技術】
【０００２】
現在、さまざまな電子情報がネットワークやメディアを介して送信されている。会社やコミュニティーのような組織においても、報告書やレポート、稟議書、連絡簿等さまざまな情報が電子化され、社員又はメンバー間でネットワークを経由して回覧されている。
【０００３】
その情報の発信源あるいは閲覧済みであることを保証する仕組みとして電子署名がある。この電子署名を利用することにより、特定の人しか知りえない署名鍵と電子情報を入力値として署名の演算を行い、検証者が検証鍵と言われる公開された情報と署名されたデータを入力値として検証演算を行うことで、その特定の人がそのデータの発信源であることを確認することが可能となる。ここで、検証鍵から署名鍵を導出することは、計算量的に不可能であることから、他の人がその特定者に成りすまして署名を行うことができないため、その署名の正当性が保証される。
【０００４】
また、組織における電子情報の回覧においては、複数の人が介在して署名を行うケースが想定され、例えば、電子データの回覧や会社における承認システムがそれに該当する。複数人の署名を行う方式としては、それぞれの署名者を検証できる多重署名（例えば、非特許文献１を参照）や、特定のグループに所属している人の誰かが署名したことを保証できるグループ署名（例えば、特許文献１を参照）が提案されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００１−１６６６８７号公報
【特許文献２】特開平０９−２７０７８７号公報
【特許文献３】特開２００２−０４０９３５号公報
【非特許文献】
【０００６】
【非特許文献１】新保 淳、「多重署名に適したＥｌＧａｍａｌ署名の一変形方式」、暗号と情報セキュリティシンポジウム（ＣＳＳ）、ＳＣＩＳ９４−２Ｃ、電子情報通信学会、１９９４
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、これらの多重署名やグループ署名では署名者が全て等価な関係で表現される。したがって、一例として示した多重署名システムにおいて電子データがどのように流通してきたのかを、この署名方式だけで表現することができない。
【０００８】
これに対し、順序や上下関係を証明する方式としては順序付き多重署名方式（例えば、特許文献２、３を参照）があげられる。これにより署名者の順番が保証され、個人の上下関係が表現できる。しかしながら、これら既存の順序付き多重署名方式は、ＲＳＡ（Ｒｉｖｅｓｔ Ｓｈａｍｉｒ Ａｄｌｅｍａｎ）問題ベースのものか、離散対数問題ベースのものが提案されている。ＲＳＡ問題ベースでは、署名する人数が増えるほど署名サイズが大きくなってしまい、また、離散対数問題ベースでは、ゼロ知識証明を利用するために演算処理に負荷がかかり、効率的な処理にならない。また、両者共、同一のメッセージに対して複数人が署名を行う方式であるため、各署名者がそれぞれ異なるメッセージを対象とするアグリゲート署名を行うことができなかった。
【０００９】
本発明は、上記課題を解決するため、署名する人数が増えても署名サイズを一定値に抑制し、かつ効率的な演算処理によって順序付き電子署名を行うことができるアグリゲート署名システム、検証システム、アグリゲート署名方法及びアグリゲート署名プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明では、以下のような解決手段を提供する。
【００１１】
（１）本発明に係るアグリゲート署名システムは、上記課題を解決するために、あるノードから別のノードへの順序付きのアグリゲート署名を行うアグリゲート署名システムであって、各ノードには、所定の自然数からなる署名鍵と、第１のＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する第１の値に対して、当該署名鍵により演算を行って生成される当該第１のＧＤＨグループに属する検証鍵とがそれぞれ割り当てられており、当該各ノードは、以下の各部を備える。
（ａ）直前のノードが存在する場合、当該直前のノードの署名対象であるメッセージ又は当該メッセージのハッシュ値、及び当該直前のノードの署名情報を受信する受信部。
（ｂ）自身のメッセージと、前記直前のノードが存在する場合、当該直前のノードのメッセージとに対して、それぞれ一方向性ハッシュ関数演算を行って、各メッセージの第２のＧＤＨグループに属するハッシュ値を生成する署名ノード一方向性ハッシュ関数演算部。
（ｃ）自身のメッセージのハッシュ値に対して自身の署名鍵により演算を行った結果と、前記直前のノードが存在する場合、当該直前のノードのメッセージのハッシュ値に対して自身のノードの署名鍵により演算を行った結果、及び前記直前のノードの署名情報とを総和して、自身の署名情報を生成する署名情報生成部。
（ｄ）直後のノードが存在する場合、自身のメッセージ又は当該メッセージのハッシュ値、及び自身の署名情報を、当該直後のノードへ送信する送信部。
【００１２】
このような構成によれば、アグリゲート署名システムは、各ノードにおいて、直前のノードのメッセージから得られたハッシュ値と、自身のメッセージから得られたハッシュ値とに対して、自身のノードに割り当てられている署名鍵によって演算を行い、さらに、直前のノードにより生成された署名情報を用いて、自身の署名情報を生成する。アグリゲート署名システムは、この署名情報により、各ノードに至るまでの署名順序を表現することができる。
【００１３】
また、このように構成されることにより、アグリゲート署名システムは、署名鍵を知らない第三者がＧＤＨグループの要素である楕円曲線上の点から署名鍵を求めることを、計算量的に困難にすることができる。また、署名者の数（ノードの数）が増えても、生成される署名情報は楕円曲線上の点であるため、署名情報のサイズ（容量）は増大せず一定値以下に抑制することができ、効率的にアグリゲート署名を生成することができる。
【００１４】
（２）また、上記アグリゲート署名システムでは、前記署名情報生成部は、前記直前のノードが複数存在する場合、自身のメッセージのハッシュ値に対して自身の署名鍵により演算を行った結果と、前記直前のノードそれぞれのメッセージのハッシュ値に対して自身のノードの署名鍵により演算を行った複数の結果と、前記直前のノードそれぞれの署名情報とを総和して、自身の署名情報を生成することを特徴とする。
【００１５】
このような構成によれば、アグリゲート署名システムは、各ノードにおいて、直前の一又は複数のノードのメッセージから得られたハッシュ値それぞれと、自身のメッセージから得られたハッシュ値とに対して、自身のノードに割り当てられている署名鍵によって演算を行い、さらに直前のノードにより生成された署名情報を用いて、自身の署名情報を生成する。アグリゲート署名システムは、この署名情報により、各ノードに至るまでの木構造における署名順序を表現することができる。
なお、木構造とは、対称か非対称かを問わず、任意の構造を持つ木構造全てを指す。本発明は、この任意の構造を持つ木構造に対して適応可能である。
【００１６】
（３）また、上記アグリゲート署名システムでは、前記各ノードは、自身の署名情報を公開する公開部を備えることを特徴とする。
【００１７】
このような構成によれば、各ノードは、順序付きのアグリゲート署名である署名情報を他のノードに対して公開することができる。
【００１８】
（４）また、上記アグリゲート署名システムでは、前記公開部は、前記各ノードの順序情報をさらに公開することを特徴とする。
【００１９】
このような構成によれば、各ノードは、署名情報と共に、この署名情報が生成されるまでの過程で署名が行われたノードの順序を公開することができる。
【００２０】
（５）本発明に係る検証システムは、上記課題を解決するために、上記アグリゲート署名システムに備えられている前記公開部により公開された署名情報を検証する検証システムであって、前記公開された署名情報が生成される過程の全てのノードのメッセージ又は当該メッセージのハッシュ値、及び当該全てのノードの検証鍵を収集する収集部と、前記収集部により収集されたメッセージに対して、それぞれ一方向性ハッシュ関数演算を行って、各メッセージの前記第２のＧＤＨグループに属するハッシュ値を生成する検証ノード一方向性ハッシュ関数演算部と、前記全てのノードの検証鍵、及び前記全てのノードのメッセージのハッシュ値に基づいて、前記公開された署名情報の正当性を検証する検証部と、を備える。
【００２１】
このような構成によれば、検証システムは、検証部により全てのノードの検証鍵とメッセージのハッシュ値とに基づいて、公開された署名情報の正当性を検証する。
【００２２】
よって、検証システムでは、各ノードにて生成される個々の署名情報等を検証することなく、公開された署名情報を検証することにより、署名順序を証明することができる。すなわち、検証システムでは、検証ノードの処理負荷を低減して検証作業を実行することができる。
【００２３】
（６）また、上記検証システムでは、前記検証部は、同一ノードの検証鍵及びハッシュ値によるペアリング演算の結果と、あるノードの検証鍵及び当該ノードの直前のノードのハッシュ値によるペアリング演算の結果とを全て乗じた値を、前記第１の値及び前記公開された署名情報によるペアリング演算の結果と比較し、双方が一致する場合、前記公開された署名情報が正当であると判定し、双方が一致しない場合、前記公開された署名情報が正当でないと判定することを特徴とする。
【００２４】
このような構成によれば、検証システムは、ペアリング演算を用いたＧＤＨ署名により、順序付きアグリゲート署名の正当性を、効率的な演算処理で検証できる。
【００２５】
（７）本発明に係るアグリゲート署名方法は、上記課題を解決するために、あるノードから別のノードへの順序付きのアグリゲート署名を行うアグリゲート署名方法であって、各ノードには、所定の自然数からなる署名鍵と、第１のＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する第１の値に対して、当該署名鍵により演算を行って生成される当該第１のＧＤＨグループに属する検証鍵とがそれぞれ割り当てられており、当該各ノードが以下の各工程を実行する。
（ａ）直前のノードが存在する場合、当該直前のノードの署名対象であるメッセージ又は当該メッセージのハッシュ値、及び当該直前のノードの署名情報を受信する受信工程。
（ｂ）自身のメッセージと、前記直前のノードが存在する場合、当該直前のノードのメッセージとに対して、それぞれ一方向性ハッシュ関数演算を行って、各メッセージの第２のＧＤＨグループに属するハッシュ値を生成する署名ノード一方向性ハッシュ関数演算工程。
（ｃ）自身のメッセージのハッシュ値に対して自身の署名鍵により演算を行った結果と、前記直前のノードが存在する場合、当該直前のノードのメッセージのハッシュ値に対して自身のノードの署名鍵により演算を行った結果、及び前記直前のノードの署名情報とを総和して、自身の署名情報を生成する署名情報生成工程。
（ｄ）直後のノードが存在する場合、自身のメッセージ又は当該メッセージのハッシュ値、及び自身の署名情報を、当該直後のノードへ送信する送信工程。
【００２６】
（８）本発明に係るアグリゲート署名プログラムは、上記課題を解決するために、あるノードから別のノードへの順序付きのアグリゲート署名を行うアグリゲート署名方法をコンピュータに実行させるためのアグリゲート署名プログラムであって、各ノードには、所定の自然数からなる署名鍵と、第１のＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する第１の値に対して、当該署名鍵により演算を行って生成される当該第１のＧＤＨグループに属する検証鍵とがそれぞれ割り当てられており、当該各ノードに、以下の各工程を実行させる。
（ａ）直前のノードが存在する場合、当該直前のノードの署名対象であるメッセージ又は当該メッセージのハッシュ値、及び当該直前のノードの署名情報を受信する受信工程。
（ｂ）自身のメッセージと、前記直前のノードが存在する場合、当該直前のノードのメッセージとに対して、それぞれ一方向性ハッシュ関数演算を行って、各メッセージの第２のＧＤＨグループに属するハッシュ値を生成する署名ノード一方向性ハッシュ関数演算工程。
（ｃ）自身のメッセージのハッシュ値に対して自身の署名鍵により演算を行った結果と、前記直前のノードが存在する場合、当該直前のノードのメッセージのハッシュ値に対して自身のノードの署名鍵により演算を行った結果、及び前記直前のノードの署名情報とを総和して、自身の署名情報を生成する署名情報生成工程。
（ｄ）直後のノードが存在する場合、自身のメッセージ又は当該メッセージのハッシュ値、及び自身の署名情報を、当該直後のノードへ送信する送信工程。
【発明の効果】
【００２７】
本発明によれば、署名する人数が増えても署名サイズを一定値に抑制し、かつ効率的な演算処理によって順序付きアグリゲート署名を行うことができる。
【図面の簡単な説明】
【００２８】
【図１】第１実施形態に係るアグリゲート署名システムにおけるリーフノードの構成を示すブロック図である。
【図２】第１実施形態に係るアグリゲート署名システムにおける中間ノードの構成を示すブロック図である。
【図３】第１実施形態に係るアグリゲート署名システムにおけるルートノードの構成を示すブロック図である。
【図４】第１実施形態に係るアグリゲート署名システムにおける検証ノードの構成を示すブロック図である。
【図５】第１実施形態において、リーフノードの署名情報を生成する方法についての説明に供するフローチャートである。
【図６】第１実施形態において、中間ノードの署名情報を生成する方法についての説明に供するフローチャートである。
【図７】第１実施形態において、ルートノードで署名情報を公開する方法についての説明に供するフローチャートである。
【図８】第１実施形態において、検証ノードで署名情報の正当性を検証する方法についての説明に供するフローチャートである。
【図９】第１実施形態において、アグリゲート署名システムの動作についての説明に供する図である。
【図１０】第２実施形態に係るアグリゲート署名システムにおけるリーフノードの構成を示すブロック図である。
【図１１】第２実施形態に係るアグリゲート署名システムにおける中間ノードの構成を示すブロック図である。
【図１２】第２実施形態に係るアグリゲート署名システムにおけるルートノードの構成を示すブロック図である。
【図１３】第２実施形態に係るアグリゲート署名システムにおける検証ノードの構成を示すブロック図である。
【発明を実施するための形態】
【００２９】
＜第１実施形態＞
以下、本発明の実施形態の一例である第１実施形態について説明する。本実施形態に係るアグリゲート署名システムは、複数のノードが木構造状に構成され、これら複数のノードで独立したメッセージに対して、下位のノードから順に順序付きの多重署名を行うシステムである。また、最上位のルートノードにより公開された署名情報は、検証システムにおける検証ノードにより正当性が検証される。
【００３０】
ところで、各ノードには、予め重複しない署名鍵と検証鍵とが認証局（ＣＡ）によってそれぞれ割り当てられている。署名鍵は、所定の自然数（ｘ）からなり、検証鍵は、ＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループ（Ｇ１）の要素である楕円曲線上の点（ｇ１）と固有署名鍵（ｘ）とに基づいて生成される楕円曲線上の点（ｖ＝ｘｇ１）からなることが好ましい。このように構成されることにより、署名鍵（ｘ）を知らない第三者が「ｖ」や「ｇ１」の値から署名鍵（ｘ）を求めることは計算量的に困難となる。
【００３１】
ここで、本実施形態で採用される具体的な署名方式について説明する。アグリゲート署名システムでは、ベースとなる署名方式としてＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＧＤＨ）署名を採用する。ＧＤＨ署名とは、Ｄｅｃｉｓｉｏｎ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＤＤＨ）問題をペアリングと呼ばれるある種のブラックボックス関数ｅ（Ｐ，Ｑ）を用いることで、解くことが可能であることを利用した署名である。
【００３２】
次に、ペアリング演算を用いたＧＤＨ署名について説明する。楕円曲線上のＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題に関連して、ＧＤＨグループが定義されている。ＧＤＨグループについて簡単に説明する。Ｇ１及びＧ２をそれぞれ異なる楕円曲線上の点の集合とする。ｇ１を集合Ｇ１の、ｇ２を集合Ｇ２の要素としたとき、楕円曲線上のＤｅｃｉｓｉｏｎａｌ Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＤＤＨ）問題とＣｏｍｐｕｔａｔｉｏｎａｌ Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＣＤＨ）問題が以下のように定義される。
【００３３】
ＤＤＨ問題：あるａ、ｂ、ｃという自然数があり、ｇｘ、ａｇｘ、ｂｇｘ、ｃｇｘ（ｘは１及び２）が与えられた時、ｃ＝ａｂかどうかを判定する問題。
ＣＤＨ問題：あるａ、ｂ、ｃという自然数があり、ｇｘ、ａｇｘ、ｂｇｘが与えられた時、ａｂｇｙを計算する問題（ｘは１及び２、ｙは１又は２）。
【００３４】
このとき、ＤＤＨ問題は、計算量的に簡単であるが、ＣＤＨ問題は、計算量的に難問である場合、この集合ＧｘをＧＤＨグループと定義する。
【００３５】
これに対し、ある楕円曲線上の点をＰ，Ｑとし、そのＰ，Ｑによっては次にあげる性質を持つことができるペアリングと呼ばれるブラックボックス関数ｅ（Ｐ，Ｑ）を定義できるものが存在する。
ｅ（Ｐ，Ｑ１＋Ｑ２）＝ｅ（Ｐ，Ｑ１）ｅ（Ｐ，Ｑ２） ・・・（１）
ｅ（Ｐ１＋Ｐ２，Ｑ）＝ｅ（Ｐ１，Ｑ）ｅ（Ｐ２，Ｑ） ・・・（２）
ｅ（ａＰ，ｂＱ）＝ｅ（ｂＰ，ａＱ）＝ｅ（ａｂＰ，Ｑ）＝ｅ（Ｐ，ａｂＱ）＝ｅ（Ｐ，Ｑ）ａｂ ・・・（３）
【００３６】
よって、ｇｘがペアリング演算の可能な楕円曲線上の点である場合には、上記の性質から、（３）式にｇｘ、ａｇｘ、ｂｇｘ、ｃｇｘを入力すると、例えば、
ｅ（ａｇ１，ｂｇ２）＝ｅ（ｇ１，ｇ２）ａｂ ・・・（４）
ｅ（ｇ１，ｃｇ２）＝ｅ（ｇ１，ｇ２）ｃ ・・・（５）
となる。したがって、両者の値が一致するかどうかにより、「ａｂ＝ｃ」であるかどうかを判定でき、ｇ１及びｇ２は、ＧＤＨグループＧ１又はＧ２の要素となりうる。
【００３７】
この性質を利用してＧＤＨ署名が構成される。集合Ｇ１及びＧ２は、ＧＤＨグループであり、ｇ１及びｇ２は、それぞれ集合Ｇ１及びＧ２の要素となる点とする。また、一方向性ハッシュ関数Ｈ２を、通常使用される任意のビット長のサイズの数値データが固定のビット長のサイズの数値データに写像変換される方式とは異なり、
Ｈ２：｛０，１｝＊→Ｇ２
のように、任意のビット長のサイズの数値データを楕円曲線上の点として表現されるＧＤＨグループＧ２の要素に写像変換する方式であると定義する。
【００３８】
このとき、ＧＤＨ署名は以下のように定義される。
鍵生成：自然数ｘを選び、ｇ１からｖ＝ｘｇ１を計算する。ｘを署名鍵、楕円曲線上の点ｖを検証鍵とする。
署名：署名者は、メッセージ「ｍ∈｛０，１｝＊」に対しｈ＝Ｈ２（ｍ）を計算し、さらに自分の署名鍵を用いてσ＝ｘｈを計算する。σをｍに対する署名として公開する。
検証：検証者は、メッセージｍからｈ＝Ｈ２（ｍ）を計算し、集合Ｇ１に属するｇ１及びｖと、集合Ｇ２に属するｈ及びσを準備する。ｅ（ｇ１，σ）とｅ（ｖ，ｈ）を計算し、両者の値が一致したら、署名σは、正しい署名と判定する。
【００３９】
このとき、ｈの値は集合Ｇ２の要素となるので、ある自然数ｙを用いてｈ＝ｙｇ２と表現できる。その結果、正しく署名が行われていれば（ｇ１，ｖ，ｈ，σ）＝（ｇ１，ｘｇ１，ｙｇ２，ｘｙｇ２）となる。したがって、正当な署名であれば上記の検証でのペアリング演算は、ｅ（ｇ１，σ）＝ｅ（ｇ１，ｘｙｇ２）＝ｅ（ｇ１，ｇ２）ｘｙ＝ｅ（ｘｇ１，ｙｇ２）＝ｅ（ｖ，ｈ）となり、値が一致することから、検証可能となる。なお、ＧＤＨグループの条件であるＣＤＨ問題の困難性から、署名鍵ｘを知らない第三者がｇ１、ｇ２、ｖ、ｈの値から署名σを導出することは不可能である。
【００４０】
木構造における最下位ノードであるリーフノード１０は、図１に示すように、記憶部１１と、リーフノード一方向性ハッシュ関数演算部１２と、リーフノード署名情報生成部１３と、リーフノード送信部１４とを備える。
【００４１】
記憶部１１は、自身（署名者ｕｌｅａｆのノード）に割り当てられている署名鍵（ｘｌｅａｆ）と、集合Ｇ１に属する値ｇ１（第１の値）に対して、この署名鍵により演算を行って生成される集合Ｇ１に属する検証鍵（ｖｌｅａｆ＝ｘｌｅａｆｇ１）とを記憶する。
【００４２】
リーフノード一方向性ハッシュ関数演算部１２は、自身の署名対象であるメッセージ（ｍｌｅａｆ）に対して、一方向性ハッシュ関数演算を行って、集合Ｇ２（第２のＧＤＨグループ）に属するハッシュ値を生成する。
【００４３】
リーフノード署名情報生成部１３は、リーフノード一方向性ハッシュ関数演算部１２により演算された、自身の署名対象であるメッセージ（ｍｌｅａｆ）のハッシュ値（ｈｌｅａｆ＝Ｈ２（ｍｌｅａｆ））に対して自身の署名鍵（ｘｌｅａｆ）により演算を行い、署名情報（σｌｅａｆ＝ｘｌｅａｆｈｌｅａｆ）を生成する。
【００４４】
リーフノード送信部１４は、生成した署名情報（σｌｅａｆ）とメッセージ（ｍｌｅａｆ）とを次（直上）のノード、すなわち中間ノード２０へ送信する。
【００４５】
また、木構造における最下位（リーフノード１０）より上のノードである中間ノード２０は、図２に示すように、記憶部２１と、中間ノード受信部２２と、中間ノード一方向性ハッシュ関数演算部２３と、中間ノード署名情報生成部２４と、中間ノード送信部２５と、を備える。
【００４６】
記憶部２１は、自身（署名者ｕｕｐのノード）に割り当てられている署名鍵（ｘｕｐ）と、集合Ｇ１に属する値ｇ１に対して、この署名鍵により演算を行って生成される集合Ｇ１に属する検証鍵（ｖｕｐ＝ｘｕｐｇ１）とを記憶する。
【００４７】
中間ノード受信部２２は、直下の一又は複数のノード（署名者ｕｌｏｗのノード）の署名対象であるメッセージ（ｍｌｏｗ）と、これら直下のノードにより生成された署名情報（σｌｏｗ）と、を受信する。
【００４８】
中間ノード一方向性ハッシュ関数演算部２３は、直下のノードから受信したメッセージ（ｍｌｏｗ）のそれぞれと、自身の署名対象であるメッセージ（ｍｕｐ）とに、それぞれ一方向性ハッシュ関数演算を行って、集合Ｇ２に属するハッシュ値を生成する。
【００４９】
中間ノード署名情報生成部２４は、自身のメッセージ（ｍｕｐ）から得られたハッシュ値（ｈｕｐ＝Ｈ２（ｍｕｐ））に対して自身の固有署名鍵（ｘｕｐ）により演算を行った結果と、直下のノードのメッセージ（ｍｌｏｗ）それぞれから得られたハッシュ値（ｈｌｏｗ＝Ｈ２（ｍｌｏｗ））に対して自身の固有署名鍵（ｘｕｐ）により演算を行った結果と、直下のノードの署名情報（σｌｏｗ）とを総和して、自身の中間ノード署名情報（σｕｐ＝Σｌｏｗ（σｌｏｗ＋ｘｕｐｈｌｏｗ）＋ｘｕｐｈｕｐ）を生成する（Σｌｏｗは、直下の一又は複数のノード全てについての総和を示す）。
【００５０】
中間ノード送信部２５は、次（直上）のノードが存在する場合に、自身の署名対象であるメッセージ（ｍｕｐ）と、中間ノード署名情報（σｕｐ）とを、次のノードへ送信する。
【００５１】
このような構成によれば、アグリゲート署名システムは、各中間ノード２０において、直下のノードのメッセージから得られたハッシュ値と、自身のメッセージから得られたハッシュ値とに対して、自身のノードに割り当てられている署名鍵によって演算を行い、さらに直下のノードにより生成された署名情報を総和して、中間ノード署名情報を生成する。この署名情報は、自身のノードに至るまでの木構造における署名経路を保持し、かつ楕円曲線上の点のみで生成される。すなわち、署名者（ノードの数）が多くなっても、署名サイズは増大せず、一定値以下に抑制することができる。
【００５２】
また、木構造における最上位の中間ノードであるルートノード３０は、図３に示すように、記憶部３１と、ルートノード受信部３２と、ルートノード一方向性ハッシュ関数演算部３３と、ルートノード署名情報生成部３４と、公開部３５とを備える。
【００５３】
記憶部３１は、自身（署名者ｕｒｏｏｔのノード）に割り当てられている署名鍵（ｘｒｏｏｔ）と、集合Ｇ１に属する値ｇ１に対して、この署名鍵により演算を行って生成される集合Ｇ１に属する検証鍵（ｖｒｏｏｔ＝ｘｒｏｏｔｇ１）を記憶する。
【００５４】
なお、ルートノード受信部３２は、中間ノード受信部２２と同一の構成であり、ルートノード一方向性ハッシュ関数演算部３３は、中間ノード一方向性ハッシュ関数演算部２３と同一の構成であり、ルートノード署名情報生成部３４は、中間ノード署名情報生成部２４と同一の構成である。
【００５５】
公開部３５は、ルートノード署名情報生成部３４により生成されたルートノード署名情報を公開する。このような構成によれば、ルートノード３０は、自身が生成した署名情報（σｒｏｏｔ）を他のノード、特に後述の検証システムにおける検証ノード４０に対して公開署名情報（σ）として公開することができる。
【００５６】
また、公開部３５は、署名順序を示す木構造内における署名者の配置、及び各署名者と署名を行ったメッセージとの対応関係に関する情報も公開する。
【００５７】
次に、ルートノード３０により公開された公開署名情報（σ）を検証する検証システムについて説明する。検証システムが有する検証ノード４０は、図４に示すように、収集部４１と、検証ノード一方向性ハッシュ関数演算部４２と、検証部４３とを備える。
【００５８】
収集部４１は、署名を行った全てのノード（リーフノード１０、中間ノード２０、ルートノード３０）それぞれのメッセージ（ｍｉ）と、検証鍵（ｖｉ）とを収集する。このとき、収集部４１は、木構造内における署名者の配置、及び各署名者と署名を行ったメッセージとの対応関係に関する情報を、必ずしも入手しなくてもよいが、ルートノード３０から入手するようにしておくことも好ましい。収集部４１がこれらの情報を入手しない場合でも、検証部４３は、署名者の配置、及び各署名者と署名を行ったメッセージとの対応関係に関して、全ての組み合わせを演算することにより、公開署名情報の正当性を検証することが可能である。しかし、収集部４１がこれらの情報を入手し検証部４３へ受け渡すようにしておくと、これらの情報がない場合に比べて検証部４３の演算量が少なくてすむ。
【００５９】
検証ノード一方向性ハッシュ関数演算部４２は、収集部４１により収集された各メッセージ（ｍｉ）に対して、それぞれ一方向性ハッシュ関数演算を行って、各メッセージの集合Ｇ２に属するハッシュ値（ｈｉ＝Ｈ２（ｍｉ））を生成する。
【００６０】
検証部４３は、収集部４１により収集された全てのノードの検証鍵と、検証ノード一方向性ハッシュ関数演算部４２により得られたハッシュ値と、署名者の配置、及び各署名者と署名を行ったメッセージとの対応関係に関する情報と、に基づいて、公開署名情報（σ）の正当性を検証する。このとき、検証部４３は、署名者の配置、及び各署名者と署名を行ったメッセージとの対応関係に関する情報がない場合、これらの対応関係に関する全ての組み合わせを演算する。
【００６１】
具体的には、検証部４３は、各ノードの検証鍵とハッシュ値とから、同一ノードの検証鍵及びハッシュ値によるペアリング演算の結果と、あるノードの検証鍵及び直前のノードのハッシュ値によるペアリング演算の結果とを全て乗じた値、すなわち、
｛Πａｌｌ−ｎｏｄｅ（ｅ（ｖｉ，ｈｉ））｝｛Π（ｅ（ｖｕｐ，ｈｌｏｗ））｝
を計算する。そして、検証部４３は、この計算結果を、ｇ１及び公開署名情報（σ）によるペアリング演算の結果、すなわち、
ｅ（ｇ１，σ）
と比較し、双方が一致する場合、公開署名情報が正当であると判定し、双方が一致しない場合、公開署名情報が正当でないと判定する。
【００６２】
このようにして検証ノード４０は、検証部４３により、全てのノードの検証鍵と、メッセージのハッシュ値と、署名者の配置、及び各署名者と署名を行ったメッセージとの対応関係に関する情報と、に基づいて、公開されているルートノード３０の署名情報の正当性を検証することができる。ここで、署名者の配置、及び各署名者と署名を行ったメッセージとの対応関係に関する情報については、これらの情報がなくても、検証部４３は、署名情報の正当性を検証することが可能である。
【００６３】
したがって、検証システムでは、各ノードにて生成される個々の署名情報等を検証することなく、ルートノード３０により公開された署名情報を数値演算のみで検証することにより、木構造におけるノード間をどのような順序で署名されてきたかを証明することができる。すなわち、順序管理のための別の装置を要することなく、検証ノード４０の処理負荷を低減して効率的に検証作業を実行することができる。なお、検証ノード４０は、検証専用のノードであってもよいし、アグリゲート署名システムのいずれかの中間ノード２０やルートノード３０であってもよい。
【００６４】
次に、アグリゲート署名システムにおいて、各ノードの署名情報を生成する方法と、検証システムにおいて、署名情報の正当性を検証する方法について説明する。
【００６５】
リーフノード１０（署名者ｕｌｅａｆ）は、図５に示すように、リーフノード一方向性ハッシュ関数演算工程ＳＴ１と、リーフノード署名情報生成工程ＳＴ２と、リーフノード送信工程ＳＴ３とにより、リーフノード署名情報を生成して直上のノード（中間ノード２０）へ送信する。
【００６６】
リーフノード一方向性ハッシュ関数演算工程ＳＴ１において、リーフノード１０におけるリーフノード一方向性ハッシュ関数演算部１２は、自身のメッセージ（ｍｌｅａｆ）に対して、一方向性ハッシュ関数演算を行う。
【００６７】
リーフノード署名情報生成工程ＳＴ２において、リーフノード１０におけるリーフノード署名情報生成部１３は、リーフノード一方向性ハッシュ関数演算工程ＳＴ１により演算されたハッシュ値（ｈｌｅａｆ）に対して、自身の署名鍵（ｘｌｅａｆ）により演算を行い、署名情報（σｌｅａｆ）を生成する。
【００６８】
リーフノード送信工程ＳＴ３において、リーフノード１０におけるリーフノード送信部１４は、リーフノード署名情報生成工程ＳＴ２により生成された署名情報（σｌｅａｆ）を、直上の中間ノード２０へ送信する。
【００６９】
リーフノード１０以外の中間ノード２０（署名者ｕｕｐ）は、図６に示すように、中間ノード受信工程ＳＴ１１と、中間ノード一方向性ハッシュ関数演算工程ＳＴ１２と、中間ノード署名情報生成工程ＳＴ１３と、中間ノード送信工程ＳＴ１４とにより、中間ノード署名情報を生成して直上の中間ノード２０へ送信する。
【００７０】
中間ノード受信工程ＳＴ１１において、署名者ｕｕｐのノードにおける中間ノード受信部２２は、直下のノード（署名者ｕｌｏｗ）のメッセージ（ｍｌｏｗ）、及び直下のノードにより生成された署名情報（σｌｏｗ）を受信する。
【００７１】
中間ノード一方向性ハッシュ関数演算工程ＳＴ１２において、署名者ｕｕｐのノードにおける中間ノード一方向性ハッシュ関数演算部２３は、直下のノードのメッセージ（ｍｌｏｗ）及び自身のメッセージ（ｍｌｏｗ）に対して、それぞれ一方向性ハッシュ関数演算を行う。
【００７２】
中間ノード署名情報生成工程ＳＴ１３において、署名者ｕｕｐのノードにおける中間ノード署名情報生成部２４は、自身のメッセージから演算により得られたハッシュ値（ｈｕｐ）に対して自身の署名鍵（ｘｕｐ）により演算を行った結果と、直下のノードのメッセージから演算により得られたハッシュ値（ｈｌｏｗ）に対して自身の署名鍵（ｘｕｐ）により演算を行った結果と、直下のノードから受信した署名情報（σｌｏｗ）とを総和して、自身のノードの署名情報（σｕｐ）を生成する。
【００７３】
中間ノード送信工程ＳＴ１４において、署名者ｕｕｐのノードにおける中間ノード送信部２５は、木構造における直上のノードが存在する場合に、自身のメッセージ（ｍｕｐ）及び自身のノードの署名情報（σｕｐ）を、直上のノードへ送信する。
【００７４】
また、木構造における最上位のノードであるルートノード３０（署名者ｕｒｏｏｔ）は、図７に示すように、ルートノード受信工程ＳＴ２１と、ルートノード一方向性ハッシュ関数演算工程ＳＴ２２と、ルートノード署名情報生成工程ＳＴ２３と、署名情報公開工程ＳＴ２４とにより、アグリゲート署名システムにおける公開署名情報（σ）を公開する。
【００７５】
ルートノード受信工程ＳＴ２１において、ルートノード３０におけるルートノード受信部３２は、直下のノード（署名者ｕｌｏｗ）のメッセージ（ｍｌｏｗ）、及び直下のノードにより生成された署名情報（σｌｏｗ）を受信する。
【００７６】
ルートノード一方向性ハッシュ関数演算工程ＳＴ２２において、ルートノード３０におけるルートノード一方向性ハッシュ関数演算部３３は、直下のノードのメッセージ（ｍｌｏｗ）及び自身のメッセージ（ｍｒｏｏｔ）に対して、それぞれ一方向性ハッシュ関数演算を行う。
【００７７】
ルートノード署名情報生成工程ＳＴ２３において、ルートノード３０におけるルートノード署名情報生成部３４は、自身のメッセージから演算により得られたハッシュ値（ｈｒｏｏｔ）に対して自身の署名鍵（ｘｒｏｏｔ）により演算を行った結果と、直下のノードのメッセージから演算により得られたハッシュ値（ｈｌｏｗ）に対して自身の署名鍵（ｘｒｏｏｔ）により演算を行った結果と、直下のノードから受信した署名情報（σｌｏｗ）とを総和して、自身のノードの署名情報（σｒｏｏｔ）を生成する。
【００７８】
署名情報公開工程ＳＴ２４において、ルートノード３０における公開部３５は、ルートノード署名情報生成工程ＳＴ２３により生成された署名情報を、公開署名情報（σ）として公開する。
【００７９】
このように、アグリゲート署名システムに係るアグリゲート署名方法によれば、各中間ノード２０において、直下のノードのメッセージから得られたハッシュ値と、自身のメッセージから得られたハッシュ値とに対して、自身のノードに割り当てられている署名鍵によって演算を行い、さらに直下のノードにより生成された署名情報を総和して、中間ノード署名情報を生成する。この署名情報は、自身のノードに至るまでの署名経路を保持し、かつ楕円曲線上の点のみで生成される。すなわち、署名者（ノードの数）が多くなっても、署名サイズは増大せず、一定値以下に抑制することができる。
【００８０】
また、検証システムにおける検証ノード４０は、図８に示すように、収集工程ＳＴ３１と、検証ノード一方向性ハッシュ関数演算工程ＳＴ３２と、検証工程ＳＴ３３とにより、公開署名情報（σ）の正当性を検証する。
【００８１】
収集工程ＳＴ３１において、収集部４１は、署名が行われた全てのノードのメッセージ（ｍｉ）、及びこれら全てのノードの検証鍵（ｖｉ）を収集する。
【００８２】
検証ノード一方向性ハッシュ関数演算工程ＳＴ３２において、検証ノード一方向性ハッシュ関数演算部４２は、収集工程ＳＴ３１により収集されたメッセージのそれぞれに対して、一方向性ハッシュ関数演算を行う。
【００８３】
検証工程ＳＴ３３において、検証部４３は、収集工程ＳＴ３１により収集された全てのノードの検証鍵、及び全てのノードのメッセージから検証ノード一方向性ハッシュ関数演算工程ＳＴ３２で得られたハッシュ値に基づいて、公開署名情報（σ）の正当性を検証する。
【００８４】
このようにして、検証システムは、検証工程ＳＴ３３により、全てのノードの検証鍵とメッセージのハッシュ値とに基づいて、公開されている中間ノード署名情報（公開署名情報σ）の正当性を検証することができる。
【００８５】
したがって、検証システムに係る検証方法では、各ノードにて生成される個々の署名情報等を検証することなく、ルートノード３０により公開された署名情報を数値演算のみで検証することにより、木構造におけるノード間をどのような順序で署名されてきたかを証明することができる。すなわち、順序管理のための別の装置を要することなく、検証工程ＳＴ３３の処理負荷を低減して検証作業を実行することができる。
【００８６】
［実施例］
ここで、木構造が３分木３階層で構成されている場合におけるアグリゲート署名システムの動作について図９を参照しながら具体的に説明する。なお、以下では、第１層をルートノード３０であるとし、第２層を中間ノード２０とし、第３層をリーフノード１０とする。
【００８７】
すなわち、第１層には、一つのルートノード３０が配置されている。また、第２層には、三つの中間ノード２０が配置され、ｕｒｏｏｔの直下にｕ１からｕ３が配置されている。また、第３層には、九つのリーフノード１０が配置され、ｕ１の直下にｕ１１からｕ１３が配置され、ｕ２の直下にｕ２１からｕ２３が配置され、ｕ３の直下にｕ３１からｕ３３が配置されている。
【００８８】
また、認証局（ＣＡ）は、予め各ノードに重複しない署名鍵と検証鍵を、以下のように付与している。なお、ｓとｔはそれぞれ、１≦ｓ≦３、１≦ｔ≦３となる整数の符号である。
第１層：（署名鍵，検証鍵）＝（ｘｒｏｏｔ，ｖｒｏｏｔ）＝（ｘｒｏｏｔ，ｘｒｏｏｔｇ１）
第２層：（署名鍵，検証鍵）＝（ｘｓ，ｖｓ）＝（ｘｓ，ｘｓｇ１）
第３層：（署名鍵，検証鍵）＝（ｘｓｔ，ｖｓｔ）＝（ｘｓｔ，ｘｓｔｇ１）
【００８９】
第３層の九つのリーフノード１０（ユーザｕｓｔ）は、自身の署名対象であるメッセージ（ｍｓｔ）に対してハッシュ値（ｈｓｔ＝Ｈ２（ｍｓｔ））を求め、ハッシュ値に対して自身の署名鍵ｘｓｔにより演算を行い、署名情報（σｓｔ＝ｘｓｔｈｓｔ）を生成する。また、リーフノード１０（ユーザｕｓｔ）は、生成した署名情報（σｓｔ）と、メッセージ（ｍｓｔ）とを直上のノード（ユーザｕｓ）に送信する。
【００９０】
第２層の三つの中間ノード２０（ユーザｕｓ）は、まず自身の署名対象であるメッセージ（ｍｓ）から、ハッシュ値（ｈｓ＝Ｈ２（ｍｓ））を求める。
次に、中間ノード２０（ユーザｕｓ）は、直下のノード（ユーザｕｓ１、ｕｓ２、ｕｓ３）から受信したメッセージ（ｍｓ１、ｍｓ２、ｍｓ３）から、ハッシュ値（ｈｓ１＝Ｈ２（ｍｓ１）、ｈｓ２＝Ｈ２（ｍｓ２）、ｈｓ３＝Ｈ２（ｍｓ３））を求める。
【００９１】
さらに、中間ノード２０（ユーザｕｓ）は、直下のノードから受信した署名情報（σｓ１、σｓ２、σｓ３）を用いて、
σｓ＝σｓ１＋ｘｓｈｓ１＋σｓ２＋ｘｓｈｓ２＋σｓ３＋ｘｓｈｓ３
＋ｘｓｈｓ ・・・（６）
＝ｘｓ１ｈｓ１＋ｘｓｈｓ１＋ｘｓ２ｈｓ２＋ｘｓｈｓ２
＋ｘｓ３ｈｓ３＋ｘｓｈｓ３＋ｘｓｈｓ ・・・（７）
を計算する。そして、中間ノード２０（ユーザｕｓ）は、生成した署名情報（σｓ）と、メッセージ（ｍｓ）とを直上のノード（ユーザｕｒｏｏｔ）に送信する。
【００９２】
第１層のルートノード３０（ユーザｕｒｏｏｔ）は、まず自身の署名対象であるメッセージ（ｍｒｏｏｔ）から、ハッシュ値（ｈｒｏｏｔ＝Ｈ２（ｍｒｏｏｔ））を求める。
次に、ルートノード３０（ユーザｕｒｏｏｔ）は、直下のノード（ユーザｕ１、ｕ２、ｕ３）から受信したメッセージ（ｍ１、ｍ２、ｍ３）から、ハッシュ値（ｈ１＝Ｈ２（ｍ１）、ｈ２＝Ｈ２（ｍ２）、ｈ３＝Ｈ２（ｍ３））を求める。
【００９３】
さらに、ルートノード３０（ユーザｕｒｏｏｔ）は、直下のノードから受信した署名情報（σ１、σ２、σ３）を用いて、
σ＝σ１＋ｘｒｏｏｔｈ１＋σ２＋ｘｒｏｏｔｈ２＋σ３＋ｘｒｏｏｔｈ３
＋ｘｒｏｏｔｈｒｏｏｔ ・・・（８）
＝ｘ１１ｈ１１＋ｘ１ｈ１１＋ｘ１２ｈ１２＋ｘ１ｈ１２
＋ｘ１３ｈ１３＋ｘ１ｈ１３＋ｘ１ｈ１＋ｘｒｏｏｔｈ１
＋ｘ２１ｈ２１＋ｘ２ｈ２１＋ｘ２２ｈ２２＋ｘ２ｈ２２
＋ｘ２３ｈ２３＋ｘ２ｈ２３＋ｘ２ｈ２＋ｘｒｏｏｔｈ２
＋ｘ３１ｈ３１＋ｘ３ｈ３１＋ｘ３２ｈ３２＋ｘ３ｈ３２
＋ｘ３３ｈ３３＋ｘ３ｈ３３＋ｘ３ｈ３＋ｘｒｏｏｔｈ３
＋ｘｒｏｏｔｈｒｏｏｔ ・・・（９）
を計算する。そして、ルートノード３０（ユーザｕｒｏｏｔ）は、生成した署名情報（σ）を、全ユーザのアグリゲート署名情報として公開する。
【００９４】
また、ルートノード３０は、署名者の木構造における署名位置情報も公開する。署名位置情報は、例えば、｛（ｕ１１，ｕ１），（ｕ１２，ｕ１），（ｕ１３，ｕ１），（ｕ２１，ｕ２），（ｕ２２，ｕ２），（ｕ２３，ｕ２），（ｕ３１，ｕ３），（ｕ３２，ｕ３），（ｕ３３，ｕ３），（ｕ１，ｕｒｏｏｔ），（ｕ２，ｕｒｏｏｔ），（ｕ３，ｕｒｏｏｔ）｝のように、隣接するノードの組み合わせの列として表現される。
【００９５】
このようにして、アグリゲート署名システムは、木構造上において連続（隣接）する２つのノード間の関係を署名鍵とハッシュ値の積で表すことにより、木構造を表現することができる。また、ノードの数が増えても、公開されるのは、ルートノード３０で生成される公開署名情報（σ）である。この署名情報は楕円曲線上の点であるため、情報のサイズ（容量）は増大せず、一定値以下に抑制することができ、効率的に順序付きアグリゲート署名を生成することができる。
【００９６】
また、検証ノード４０は、以下の検証過程１から検証過程３により公開署名情報（σ）の正当性を検証する。
【００９７】
（検証過程１）検証ノード４０は、署名を行った全てのノードが署名対象としたメッセージ（ｍｒｏｏｔ、ｍ１、ｍ２、ｍ３、ｍ１１、ｍ１２、ｍ１３、ｍ２１、ｍ２２、ｍ２３、ｍ３１、ｍ３２、ｍ３３）を収集し、これらに対してハッシュ値（ｈｒｏｏｔ＝Ｈ２（ｍｒｏｏｔ）、ｈ１＝Ｈ２（ｍ１）、ｈ２＝Ｈ２（ｍ２）、ｈ３＝Ｈ２（ｍ３）、ｈ１１＝Ｈ２（ｍ１１）、ｈ１２＝Ｈ２（ｍ１２）、ｈ１３＝Ｈ２（ｍ１３）、ｈ２１＝Ｈ２（ｍ２１）、ｈ２２＝Ｈ２（ｍ２２）、ｈ２３＝Ｈ２（ｍ２３）、ｈ３１＝Ｈ２（ｍ３１）、ｈ３２＝Ｈ２（ｍ３２）、ｈ３３＝Ｈ２（ｍ３３））を求める。
【００９８】
（検証過程２）検証ノード４０は、署名を行った全てのノードの検証鍵（ｖｒｏｏｔ、ｖ１、ｖ２、ｖ３、ｖ１１、ｖ１２、ｖ１３、ｖ２１、ｖ２２、ｖ２３、ｖ３１、ｖ３２、ｖ３３）を収集する。
【００９９】
（検証過程３）検証ノード４０は、公開された公開署名情報（σ）の正当性を検証する。具体的には、検証ノード４０は、検証過程１で求めたハッシュ値と、収集した全てのノードの検証鍵とから、
ｅ（ｖ１１，ｈ１１）・ｅ（ｖ１，ｈ１１）
・ｅ（ｖ１２，ｈ１２）・ｅ（ｖ１，ｈ１２）
・ｅ（ｖ１３，ｈ１３）・ｅ（ｖ１，ｈ１３）
・ｅ（ｖ１，ｈ１）・ｅ（ｖｒｏｏｔ，ｈ１）
・ｅ（ｖ２１，ｈ２１）・ｅ（ｖ２，ｈ２１）
・ｅ（ｖ２２，ｈ２２）・ｅ（ｖ２，ｈ２２）
・ｅ（ｖ２３，ｈ２３）・ｅ（ｖ２，ｈ２３）
・ｅ（ｖ２，ｈ２）・ｅ（ｖｒｏｏｔ，ｈ２）
・ｅ（ｖ３１，ｈ３１）・ｅ（ｖ３，ｈ３１）
・ｅ（ｖ３２，ｈ３２）・ｅ（ｖ３，ｈ３２）
・ｅ（ｖ３３，ｈ３３）・ｅ（ｖ３，ｈ３３）
・ｅ（ｖ３，ｈ３）・ｅ（ｖｒｏｏｔ，ｈ３）
・ｅ（ｖｒｏｏｔ，ｈｒｏｏｔ） ・・・（１０）
を計算し、この値とｅ（ｇ１，σ）の値が一致することを確認する。これらの値が一致した場合には、公開署名情報（σ）が正当であると判断する。
【０１００】
ここで、（検証過程３）における「ｅ（ｇ１，σ）」を展開すると、
ｅ（ｇ１，σ）
＝ｅ（ｇ１，ｘ１１ｈ１１）・ｅ（ｇ１，ｘ１ｈ１１）
・ｅ（ｇ１，ｘ１２ｈ１２）・ｅ（ｇ１，ｘ１ｈ１２）
・ｅ（ｇ１，ｘ１３ｈ１３）・ｅ（ｇ１，ｘ１ｈ１３）
・ｅ（ｇ１，ｘ１ｈ１）・ｅ（ｇ１，ｘｒｏｏｔｈ１）
・ｅ（ｇ１，ｘ２１ｈ２１）・ｅ（ｇ１，ｘ２ｈ２１）
・ｅ（ｇ１，ｘ２２ｈ２２）・ｅ（ｇ１，ｘ２ｈ２２）
・ｅ（ｇ１，ｘ２３ｈ２３）・ｅ（ｇ１，ｘ２ｈ２３）
・ｅ（ｇ１，ｘ２ｈ２）・ｅ（ｇ１，ｘｒｏｏｔｈ２）
・ｅ（ｇ１，ｘ３１ｈ３１）・ｅ（ｇ１，ｘ３ｈ３１）
・ｅ（ｇ１，ｘ３２ｈ３２）・ｅ（ｇ１，ｘ３ｈ３２）
・ｅ（ｇ１，ｘ３３ｈ３３）・ｅ（ｇ１，ｘ３ｈ３３）
・ｅ（ｇ１，ｘ３ｈ３）・ｅ（ｇ１，ｘｒｏｏｔｈ３）
・ｅ（ｇ１，ｘｒｏｏｔｈｒｏｏｔ） ・・・（１１）
＝ｅ（ｘ１１ｇ１，ｈ１１）・ｅ（ｘ１ｇ１，ｈ１１）
・ｅ（ｘ１２ｇ１，ｈ１２）・ｅ（ｘ１ｇ１，ｈ１２）
・ｅ（ｘ１３ｇ１，ｈ１３）・ｅ（ｘ１ｇ１，ｈ１３）
・ｅ（ｘ１ｇ１，ｈ１）・ｅ（ｘｒｏｏｔｇ１，ｈ１）
・ｅ（ｘ２１ｇ１，ｈ２１）・ｅ（ｘ２ｇ１，ｈ２１）
・ｅ（ｘ２２ｇ１，ｈ２２）・ｅ（ｘ２ｇ１，ｈ２２）
・ｅ（ｘ２３ｇ１，ｈ２３）・ｅ（ｘ２ｇ１，ｈ２３）
・ｅ（ｘ２ｇ１，ｈ２）・ｅ（ｘｒｏｏｔｇ１，ｈ２）
・ｅ（ｘ３１ｇ１，ｈ３１）・ｅ（ｘ３ｇ１，ｈ３１）
・ｅ（ｘ３２ｇ１，ｈ３２）・ｅ（ｘ３ｇ１，ｈ３２）
・ｅ（ｘ３３ｇ１，ｈ３３）・ｅ（ｘ３ｇ１，ｈ３３）
・ｅ（ｘ３ｇ１，ｈ３）・ｅ（ｘｒｏｏｔｇ１，ｈ３）
・ｅ（ｘｒｏｏｔｇ１，ｈｒｏｏｔ） ・・・（１２）
＝ｅ（ｖ１１，ｈ１１）・ｅ（ｖ１，ｈ１１）
・ｅ（ｖ１２，ｈ１２）・ｅ（ｖ１，ｈ１２）
・ｅ（ｖ１３，ｈ１３）・ｅ（ｖ１，ｈ１３）
・ｅ（ｖ１，ｈ１）・ｅ（ｖｒｏｏｔ，ｈ１）
・ｅ（ｖ２１，ｈ２１）・ｅ（ｖ２，ｈ２１）
・ｅ（ｖ２２，ｈ２２）・ｅ（ｖ２，ｈ２２）
・ｅ（ｖ２３，ｈ２３）・ｅ（ｖ２，ｈ２３）
・ｅ（ｖ２，ｈ２）・ｅ（ｖｒｏｏｔ，ｈ２）
・ｅ（ｖ３１，ｈ３１）・ｅ（ｖ３，ｈ３１）
・ｅ（ｖ３２，ｈ３２）・ｅ（ｖ３，ｈ３２）
・ｅ（ｖ３３，ｈ３３）・ｅ（ｖ３，ｈ３３）
・ｅ（ｖ３，ｈ３）・ｅ（ｖｒｏｏｔ，ｈ３）
・ｅ（ｖｒｏｏｔ，ｈｒｏｏｔ） ・・・（１３）
となり、署名の過程が正しく行われていれば、（１０）式と一致する。よって、公開されているユーザの検証鍵と、全てのメッセージから求めたハッシュ値とから、アグリゲート署名の検証が可能となる。
【０１０１】
ここで、σの値に着目すると、ユーザｕｓｔはｈｓｔにのみ署名処理（ｘｓｔｈｓｔの演算）を行っており、他のｈｓ及びｈｒｏｏｔにはこのような署名処理を行っていない。これにより、ユーザｕｓｔが最初、すなわち木構造におけるリーフノード１０の署名者であることが分かる。
【０１０２】
また、「ｘｓｈｓｔ」の項により、この最初の署名者が署名処理したｈｓｔに対して署名処理を行っているのがユーザｕｓであることが表されているので、このユーザｕｓが２番目（中間ノード２０）の署名者であることが分かる。ユーザｕｓは同時にｈｓに対して署名処理（ｘｓｈｓ）を行っている。同様に「ｘｒｏｏｔｈｓ」の項により、このｈｓに対して署名処理を行っているのがユーザｕｒｏｏｔであることが表されているので、このユーザｕｒｏｏｔが３番目の署名者であることが分かる。
【０１０３】
さらに、ｈｒｏｏｔに対して署名処理を行っているユーザはなく、ユーザｕｒｏｏｔで収束しているため、この３番目の署名者がルートノード３０であることが分かる。
【０１０４】
また、（１１）式において、ＣＤＨ問題や楕円曲線上の離散対数問題から、秘密情報である署名鍵を知らない第三者が、右辺の各項（ｘαｈβ又はｘβｈβ）を任意に取り除くことはできないため、第三者による順序の入れ替えは不可能である。すなわち、アグリゲート署名システム及び検証システムが採用する本署名方式は、木構造における署名順序を署名鍵とハッシュ値の積により表現することができる。
【０１０５】
また、署名者の数（ノードの数）が増えても、公開される情報は公開署名情報（σ）のみである。この公開署名情報（σ）は一つの楕円曲線上の点であるため、情報のサイズ（容量）は増大せず、一定値以下に抑制することができる。
【０１０６】
さらに、検証システムでは、検証過程３で示した数値演算のみで検証することにより、ノード間をどのような順序で署名されてきたかを証明することができる。したがって、順序管理のための装置を別途用意することなく、検証システムの処理負荷を低減して効率的に検証作業を実行することができる。
【０１０７】
＜第２実施形態＞
以下、本発明の実施形態の一例である第２実施形態について説明する。なお、第１実施形態と同様の構成については、同一の符号を付し、説明を省略又は簡略化する。
【０１０８】
本実施形態に係るアグリゲート署名システムにおいて、リーフノード１０は、リーフノード一方向性ハッシュ関数演算部１２及びリーフノード送信部１４の構成が第１実施形態と異なる。
すなわち、リーフノード送信部１４は、リーフノード一方向性ハッシュ関数演算部１２の演算結果であるハッシュ値（ｈｌｅａｆ）とリーフノード署名情報（σｌｅａｆ）とを、直上のノード（中間ノード２０）へ送信する。
【０１０９】
中間ノード２０は、中間ノード受信部２２、中間ノード一方向性ハッシュ関数演算部２３、及び中間ノード送信部２５の構成が第１実施形態と異なる。
すなわち、中間ノード受信部２２は、直下のノードから、メッセージ（ｍｌｏｗ）の代わりにハッシュ値（ｈｌｏｗ）を受信して中間ノード署名情報生成部２４へ供給する。これにより、中間ノード２０は、直前のノードのメッセージ（ｍｌｏｗ）に対して一方向性ハッシュ関数演算を行う必要がなくなる。
【０１１０】
また、中間ノード送信部２５は、中間ノード一方向性ハッシュ関数演算部２３の演算結果であるハッシュ値（ｈｕｐ）と中間ノード署名情報（σｕｐ）とを、直上のノードへ送信する。
【０１１１】
ルートノード３０は、ルートノード受信部３２及びルートノード一方向性ハッシュ関数演算部３３の構成が第１実施形態と異なる。
すなわち、ルートノード受信部３２は、直下のノードから、メッセージ（ｍｌｏｗ）の代わりにハッシュ値（ｈｌｏｗ）を受信してルートノード署名情報生成部３４へ供給する。これにより、ルートノード３０は、直下のノードのメッセージ（ｍｌｏｗ）に対して一方向性ハッシュ関数演算を行う必要がなくなる。
【０１１２】
本実施形態に係る検証システムにおいて、検証ノード４０は、収集部４１の構成が第１実施形態と異なる。さらに、検証ノード４０は、第１実施形態における検証ノード一方向性ハッシュ関数演算部４２を必要としない。
【０１１３】
すなわち、収集部４１は、各ノードから、メッセージ（ｍｉ）の代わりにハッシュ値（ｈｉ）を受信して検証部４３へ供給する。これにより、検証ノード４０は、各ノードのメッセージ（ｍｉ）に対して一方向性ハッシュ関数演算を行う必要がなくなる。
【０１１４】
本実施形態によれば、各ノードにおける一方向性ハッシュ関数演算の処理負荷を低減することができる。
具体的には、第１実施形態における中間ノード一方向性ハッシュ関数演算工程ＳＴ１２と、ルートノード一方向性ハッシュ関数演算工程ＳＴ２２の処理負荷が低減され、検証ノード一方向性ハッシュ関数演算工程ＳＴ３２は不要となる。
【０１１５】
なお、各ノード間においては、メッセージ（ｍｉ）又はハッシュ値（ｈｉ）のいずれかが送受信されればよく、アグリゲート署名システム及び検証システム内において統一されていなくてもよい。また、メッセージ及びハッシュ値の双方を送受信することとしてもよい。
【０１１６】
以上で説明した各実施形態におけるアグリゲート署名システム及び検証システムは、各ノードで独立したメッセージを署名対象とするので、例えば署名済みの素材を集めてコンテンツを生成する場合のように、下位（部分）から上位（全体）へのボトムアップの署名方式を提供することができる。
【０１１７】
また、上述の各実施形態において、ペアリング関数への入力である２つの引数は、ペアリングの演算が可能な楕円曲線上の点ｇ１又はｇ２のスカラー倍として表されるが、この楕円曲線は、第１引数と第２引数とで異なっている。すなわち、ペアリング関数の第１引数用と第２引数用とに、それぞれ異なる楕円曲線（Ｇ１又はＧ２）上の２点（ｇ１又はｇ２）が与えられている。具体的には、第１引数に関する検証鍵は、ｇ１のスカラー倍（Ｇ１上の点）となり、第２引数に関するハッシュ値及び署名情報は、ｇ２のスカラー倍（Ｇ２上の点）となる。
【０１１８】
このことにより、演算回数が増加する場合があるが、ペアリング関数の演算において並列して処理できるため、計算時間の短縮が期待できる。
また、集合Ｇ１又はＧ２のいずれかに不具合が発見された場合、一方を共用する、又は他のＧＤＨグループに交換することにより、アグリゲート署名システム及び検証システムが維持される
【０１１９】
以上、本発明の実施形態について説明したが、本発明は上述した実施形態に限るものではない。また、本発明の実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、本発明の実施形態に記載されたものに限定されるものではない。
【０１２０】
上述の実施形態では、ルートノード３０が公開部３５を備えているが、他のノード（中間ノード２０、リーフノード１０）も備えていてよい。この場合、検証ノード４０は、公開された署名情報に基づいて、公開したノードに至るまでの署名経路の正当性を検証可能である。さらに、各ノードの公開部３５は、自身のノードの検証鍵を公開し、検証ノード４０へ提供してもよい。
【０１２１】
また、上述の実施形態では、署名鍵及び検証鍵は、認証局によって割り当てられることとしたが、本発明はこれには限られない。例えば、アグリゲート署名システムにおいて、署名鍵となる自然数ｘ、及び集合Ｇ１に属する値ｇ１を決定し、検証鍵を演算により算出（ｖ＝ｘｇ１）してもよい。
【０１２２】
また、上述の実施形態では、中間ノード２０に対して直下のノードが複数存在する木構造における順序付き多重署名について説明したが、本発明はこれには限られない。すなわち、中間ノード２０に対して直下のノードが単一であり、複数のノードが一列に連なっている場合にも、本発明は適用可能である。
【０１２３】
この場合、アグリゲート署名システム及び検証システムは、各ノードで独立したメッセージを署名対象とするので、例えば電子掲示板やブログのコメント等のように、前のメッセージを受けて次のメッセージを追加する連作に対して利用することができる。
【０１２４】
なお、この場合、ルートノード３０（最終ノード）が公開する署名者の署名順序情報（署名位置情報）は、例えば、｛（１，ｕ１），（２，ｕ２），・・・，（ｋ，ｕｋ）｝のように、順序番号を付加したノードの列として表現される。
【０１２５】
また、アグリゲート署名システム及び検証システムによる一連の処理は、ソフトウェアにより行うこともできる。一連の処理をソフトウェアによって行う場合には、そのソフトウェアを構成するプログラムが、汎用のコンピュータ等にインストールされる。また、当該プログラムは、ＣＤ−ＲＯＭのようなリムーバブルメディアに記録されてユーザに配布されてもよいし、ネットワークを介してユーザのコンピュータにダウンロードされることにより配布されてもよい。
【符号の説明】
【０１２６】
１０ リーフノード
１１ 記憶部
１２ リーフノード一方向性ハッシュ関数演算部
１３ リーフノード署名情報生成部
１４ リーフノード送信部
２０ 中間ノード
２１ 記憶部
２２ 中間ノード受信部
２３ 中間ノード一方向性ハッシュ関数演算部
２４ 中間ノード署名情報生成部
２５ 中間ノード送信部
３０ ルートノード
３１ 記憶部
３２ ルートノード受信部
３３ ルートノード一方向性ハッシュ関数演算部
３４ ルートノード署名情報生成部
３５ 公開部
４０ 検証ノード
４１ 収集部
４２ 検証ノード一方向性ハッシュ関数演算部
４３ 検証部
【技術分野】
【０００１】
本発明は、電子署名を利用した電子データのアグリゲート署名システム、検証システム、アグリゲート署名方法及びアグリゲート署名プログラムに関する。
【背景技術】
【０００２】
現在、さまざまな電子情報がネットワークやメディアを介して送信されている。会社やコミュニティーのような組織においても、報告書やレポート、稟議書、連絡簿等さまざまな情報が電子化され、社員又はメンバー間でネットワークを経由して回覧されている。
【０００３】
その情報の発信源あるいは閲覧済みであることを保証する仕組みとして電子署名がある。この電子署名を利用することにより、特定の人しか知りえない署名鍵と電子情報を入力値として署名の演算を行い、検証者が検証鍵と言われる公開された情報と署名されたデータを入力値として検証演算を行うことで、その特定の人がそのデータの発信源であることを確認することが可能となる。ここで、検証鍵から署名鍵を導出することは、計算量的に不可能であることから、他の人がその特定者に成りすまして署名を行うことができないため、その署名の正当性が保証される。
【０００４】
また、組織における電子情報の回覧においては、複数の人が介在して署名を行うケースが想定され、例えば、電子データの回覧や会社における承認システムがそれに該当する。複数人の署名を行う方式としては、それぞれの署名者を検証できる多重署名（例えば、非特許文献１を参照）や、特定のグループに所属している人の誰かが署名したことを保証できるグループ署名（例えば、特許文献１を参照）が提案されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００１−１６６６８７号公報
【特許文献２】特開平０９−２７０７８７号公報
【特許文献３】特開２００２−０４０９３５号公報
【非特許文献】
【０００６】
【非特許文献１】新保 淳、「多重署名に適したＥｌＧａｍａｌ署名の一変形方式」、暗号と情報セキュリティシンポジウム（ＣＳＳ）、ＳＣＩＳ９４−２Ｃ、電子情報通信学会、１９９４
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、これらの多重署名やグループ署名では署名者が全て等価な関係で表現される。したがって、一例として示した多重署名システムにおいて電子データがどのように流通してきたのかを、この署名方式だけで表現することができない。
【０００８】
これに対し、順序や上下関係を証明する方式としては順序付き多重署名方式（例えば、特許文献２、３を参照）があげられる。これにより署名者の順番が保証され、個人の上下関係が表現できる。しかしながら、これら既存の順序付き多重署名方式は、ＲＳＡ（Ｒｉｖｅｓｔ Ｓｈａｍｉｒ Ａｄｌｅｍａｎ）問題ベースのものか、離散対数問題ベースのものが提案されている。ＲＳＡ問題ベースでは、署名する人数が増えるほど署名サイズが大きくなってしまい、また、離散対数問題ベースでは、ゼロ知識証明を利用するために演算処理に負荷がかかり、効率的な処理にならない。また、両者共、同一のメッセージに対して複数人が署名を行う方式であるため、各署名者がそれぞれ異なるメッセージを対象とするアグリゲート署名を行うことができなかった。
【０００９】
本発明は、上記課題を解決するため、署名する人数が増えても署名サイズを一定値に抑制し、かつ効率的な演算処理によって順序付き電子署名を行うことができるアグリゲート署名システム、検証システム、アグリゲート署名方法及びアグリゲート署名プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明では、以下のような解決手段を提供する。
【００１１】
（１）本発明に係るアグリゲート署名システムは、上記課題を解決するために、あるノードから別のノードへの順序付きのアグリゲート署名を行うアグリゲート署名システムであって、各ノードには、所定の自然数からなる署名鍵と、第１のＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する第１の値に対して、当該署名鍵により演算を行って生成される当該第１のＧＤＨグループに属する検証鍵とがそれぞれ割り当てられており、当該各ノードは、以下の各部を備える。
（ａ）直前のノードが存在する場合、当該直前のノードの署名対象であるメッセージ又は当該メッセージのハッシュ値、及び当該直前のノードの署名情報を受信する受信部。
（ｂ）自身のメッセージと、前記直前のノードが存在する場合、当該直前のノードのメッセージとに対して、それぞれ一方向性ハッシュ関数演算を行って、各メッセージの第２のＧＤＨグループに属するハッシュ値を生成する署名ノード一方向性ハッシュ関数演算部。
（ｃ）自身のメッセージのハッシュ値に対して自身の署名鍵により演算を行った結果と、前記直前のノードが存在する場合、当該直前のノードのメッセージのハッシュ値に対して自身のノードの署名鍵により演算を行った結果、及び前記直前のノードの署名情報とを総和して、自身の署名情報を生成する署名情報生成部。
（ｄ）直後のノードが存在する場合、自身のメッセージ又は当該メッセージのハッシュ値、及び自身の署名情報を、当該直後のノードへ送信する送信部。
【００１２】
このような構成によれば、アグリゲート署名システムは、各ノードにおいて、直前のノードのメッセージから得られたハッシュ値と、自身のメッセージから得られたハッシュ値とに対して、自身のノードに割り当てられている署名鍵によって演算を行い、さらに、直前のノードにより生成された署名情報を用いて、自身の署名情報を生成する。アグリゲート署名システムは、この署名情報により、各ノードに至るまでの署名順序を表現することができる。
【００１３】
また、このように構成されることにより、アグリゲート署名システムは、署名鍵を知らない第三者がＧＤＨグループの要素である楕円曲線上の点から署名鍵を求めることを、計算量的に困難にすることができる。また、署名者の数（ノードの数）が増えても、生成される署名情報は楕円曲線上の点であるため、署名情報のサイズ（容量）は増大せず一定値以下に抑制することができ、効率的にアグリゲート署名を生成することができる。
【００１４】
（２）また、上記アグリゲート署名システムでは、前記署名情報生成部は、前記直前のノードが複数存在する場合、自身のメッセージのハッシュ値に対して自身の署名鍵により演算を行った結果と、前記直前のノードそれぞれのメッセージのハッシュ値に対して自身のノードの署名鍵により演算を行った複数の結果と、前記直前のノードそれぞれの署名情報とを総和して、自身の署名情報を生成することを特徴とする。
【００１５】
このような構成によれば、アグリゲート署名システムは、各ノードにおいて、直前の一又は複数のノードのメッセージから得られたハッシュ値それぞれと、自身のメッセージから得られたハッシュ値とに対して、自身のノードに割り当てられている署名鍵によって演算を行い、さらに直前のノードにより生成された署名情報を用いて、自身の署名情報を生成する。アグリゲート署名システムは、この署名情報により、各ノードに至るまでの木構造における署名順序を表現することができる。
なお、木構造とは、対称か非対称かを問わず、任意の構造を持つ木構造全てを指す。本発明は、この任意の構造を持つ木構造に対して適応可能である。
【００１６】
（３）また、上記アグリゲート署名システムでは、前記各ノードは、自身の署名情報を公開する公開部を備えることを特徴とする。
【００１７】
このような構成によれば、各ノードは、順序付きのアグリゲート署名である署名情報を他のノードに対して公開することができる。
【００１８】
（４）また、上記アグリゲート署名システムでは、前記公開部は、前記各ノードの順序情報をさらに公開することを特徴とする。
【００１９】
このような構成によれば、各ノードは、署名情報と共に、この署名情報が生成されるまでの過程で署名が行われたノードの順序を公開することができる。
【００２０】
（５）本発明に係る検証システムは、上記課題を解決するために、上記アグリゲート署名システムに備えられている前記公開部により公開された署名情報を検証する検証システムであって、前記公開された署名情報が生成される過程の全てのノードのメッセージ又は当該メッセージのハッシュ値、及び当該全てのノードの検証鍵を収集する収集部と、前記収集部により収集されたメッセージに対して、それぞれ一方向性ハッシュ関数演算を行って、各メッセージの前記第２のＧＤＨグループに属するハッシュ値を生成する検証ノード一方向性ハッシュ関数演算部と、前記全てのノードの検証鍵、及び前記全てのノードのメッセージのハッシュ値に基づいて、前記公開された署名情報の正当性を検証する検証部と、を備える。
【００２１】
このような構成によれば、検証システムは、検証部により全てのノードの検証鍵とメッセージのハッシュ値とに基づいて、公開された署名情報の正当性を検証する。
【００２２】
よって、検証システムでは、各ノードにて生成される個々の署名情報等を検証することなく、公開された署名情報を検証することにより、署名順序を証明することができる。すなわち、検証システムでは、検証ノードの処理負荷を低減して検証作業を実行することができる。
【００２３】
（６）また、上記検証システムでは、前記検証部は、同一ノードの検証鍵及びハッシュ値によるペアリング演算の結果と、あるノードの検証鍵及び当該ノードの直前のノードのハッシュ値によるペアリング演算の結果とを全て乗じた値を、前記第１の値及び前記公開された署名情報によるペアリング演算の結果と比較し、双方が一致する場合、前記公開された署名情報が正当であると判定し、双方が一致しない場合、前記公開された署名情報が正当でないと判定することを特徴とする。
【００２４】
このような構成によれば、検証システムは、ペアリング演算を用いたＧＤＨ署名により、順序付きアグリゲート署名の正当性を、効率的な演算処理で検証できる。
【００２５】
（７）本発明に係るアグリゲート署名方法は、上記課題を解決するために、あるノードから別のノードへの順序付きのアグリゲート署名を行うアグリゲート署名方法であって、各ノードには、所定の自然数からなる署名鍵と、第１のＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する第１の値に対して、当該署名鍵により演算を行って生成される当該第１のＧＤＨグループに属する検証鍵とがそれぞれ割り当てられており、当該各ノードが以下の各工程を実行する。
（ａ）直前のノードが存在する場合、当該直前のノードの署名対象であるメッセージ又は当該メッセージのハッシュ値、及び当該直前のノードの署名情報を受信する受信工程。
（ｂ）自身のメッセージと、前記直前のノードが存在する場合、当該直前のノードのメッセージとに対して、それぞれ一方向性ハッシュ関数演算を行って、各メッセージの第２のＧＤＨグループに属するハッシュ値を生成する署名ノード一方向性ハッシュ関数演算工程。
（ｃ）自身のメッセージのハッシュ値に対して自身の署名鍵により演算を行った結果と、前記直前のノードが存在する場合、当該直前のノードのメッセージのハッシュ値に対して自身のノードの署名鍵により演算を行った結果、及び前記直前のノードの署名情報とを総和して、自身の署名情報を生成する署名情報生成工程。
（ｄ）直後のノードが存在する場合、自身のメッセージ又は当該メッセージのハッシュ値、及び自身の署名情報を、当該直後のノードへ送信する送信工程。
【００２６】
（８）本発明に係るアグリゲート署名プログラムは、上記課題を解決するために、あるノードから別のノードへの順序付きのアグリゲート署名を行うアグリゲート署名方法をコンピュータに実行させるためのアグリゲート署名プログラムであって、各ノードには、所定の自然数からなる署名鍵と、第１のＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する第１の値に対して、当該署名鍵により演算を行って生成される当該第１のＧＤＨグループに属する検証鍵とがそれぞれ割り当てられており、当該各ノードに、以下の各工程を実行させる。
（ａ）直前のノードが存在する場合、当該直前のノードの署名対象であるメッセージ又は当該メッセージのハッシュ値、及び当該直前のノードの署名情報を受信する受信工程。
（ｂ）自身のメッセージと、前記直前のノードが存在する場合、当該直前のノードのメッセージとに対して、それぞれ一方向性ハッシュ関数演算を行って、各メッセージの第２のＧＤＨグループに属するハッシュ値を生成する署名ノード一方向性ハッシュ関数演算工程。
（ｃ）自身のメッセージのハッシュ値に対して自身の署名鍵により演算を行った結果と、前記直前のノードが存在する場合、当該直前のノードのメッセージのハッシュ値に対して自身のノードの署名鍵により演算を行った結果、及び前記直前のノードの署名情報とを総和して、自身の署名情報を生成する署名情報生成工程。
（ｄ）直後のノードが存在する場合、自身のメッセージ又は当該メッセージのハッシュ値、及び自身の署名情報を、当該直後のノードへ送信する送信工程。
【発明の効果】
【００２７】
本発明によれば、署名する人数が増えても署名サイズを一定値に抑制し、かつ効率的な演算処理によって順序付きアグリゲート署名を行うことができる。
【図面の簡単な説明】
【００２８】
【図１】第１実施形態に係るアグリゲート署名システムにおけるリーフノードの構成を示すブロック図である。
【図２】第１実施形態に係るアグリゲート署名システムにおける中間ノードの構成を示すブロック図である。
【図３】第１実施形態に係るアグリゲート署名システムにおけるルートノードの構成を示すブロック図である。
【図４】第１実施形態に係るアグリゲート署名システムにおける検証ノードの構成を示すブロック図である。
【図５】第１実施形態において、リーフノードの署名情報を生成する方法についての説明に供するフローチャートである。
【図６】第１実施形態において、中間ノードの署名情報を生成する方法についての説明に供するフローチャートである。
【図７】第１実施形態において、ルートノードで署名情報を公開する方法についての説明に供するフローチャートである。
【図８】第１実施形態において、検証ノードで署名情報の正当性を検証する方法についての説明に供するフローチャートである。
【図９】第１実施形態において、アグリゲート署名システムの動作についての説明に供する図である。
【図１０】第２実施形態に係るアグリゲート署名システムにおけるリーフノードの構成を示すブロック図である。
【図１１】第２実施形態に係るアグリゲート署名システムにおける中間ノードの構成を示すブロック図である。
【図１２】第２実施形態に係るアグリゲート署名システムにおけるルートノードの構成を示すブロック図である。
【図１３】第２実施形態に係るアグリゲート署名システムにおける検証ノードの構成を示すブロック図である。
【発明を実施するための形態】
【００２９】
＜第１実施形態＞
以下、本発明の実施形態の一例である第１実施形態について説明する。本実施形態に係るアグリゲート署名システムは、複数のノードが木構造状に構成され、これら複数のノードで独立したメッセージに対して、下位のノードから順に順序付きの多重署名を行うシステムである。また、最上位のルートノードにより公開された署名情報は、検証システムにおける検証ノードにより正当性が検証される。
【００３０】
ところで、各ノードには、予め重複しない署名鍵と検証鍵とが認証局（ＣＡ）によってそれぞれ割り当てられている。署名鍵は、所定の自然数（ｘ）からなり、検証鍵は、ＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループ（Ｇ１）の要素である楕円曲線上の点（ｇ１）と固有署名鍵（ｘ）とに基づいて生成される楕円曲線上の点（ｖ＝ｘｇ１）からなることが好ましい。このように構成されることにより、署名鍵（ｘ）を知らない第三者が「ｖ」や「ｇ１」の値から署名鍵（ｘ）を求めることは計算量的に困難となる。
【００３１】
ここで、本実施形態で採用される具体的な署名方式について説明する。アグリゲート署名システムでは、ベースとなる署名方式としてＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＧＤＨ）署名を採用する。ＧＤＨ署名とは、Ｄｅｃｉｓｉｏｎ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＤＤＨ）問題をペアリングと呼ばれるある種のブラックボックス関数ｅ（Ｐ，Ｑ）を用いることで、解くことが可能であることを利用した署名である。
【００３２】
次に、ペアリング演算を用いたＧＤＨ署名について説明する。楕円曲線上のＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題に関連して、ＧＤＨグループが定義されている。ＧＤＨグループについて簡単に説明する。Ｇ１及びＧ２をそれぞれ異なる楕円曲線上の点の集合とする。ｇ１を集合Ｇ１の、ｇ２を集合Ｇ２の要素としたとき、楕円曲線上のＤｅｃｉｓｉｏｎａｌ Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＤＤＨ）問題とＣｏｍｐｕｔａｔｉｏｎａｌ Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＣＤＨ）問題が以下のように定義される。
【００３３】
ＤＤＨ問題：あるａ、ｂ、ｃという自然数があり、ｇｘ、ａｇｘ、ｂｇｘ、ｃｇｘ（ｘは１及び２）が与えられた時、ｃ＝ａｂかどうかを判定する問題。
ＣＤＨ問題：あるａ、ｂ、ｃという自然数があり、ｇｘ、ａｇｘ、ｂｇｘが与えられた時、ａｂｇｙを計算する問題（ｘは１及び２、ｙは１又は２）。
【００３４】
このとき、ＤＤＨ問題は、計算量的に簡単であるが、ＣＤＨ問題は、計算量的に難問である場合、この集合ＧｘをＧＤＨグループと定義する。
【００３５】
これに対し、ある楕円曲線上の点をＰ，Ｑとし、そのＰ，Ｑによっては次にあげる性質を持つことができるペアリングと呼ばれるブラックボックス関数ｅ（Ｐ，Ｑ）を定義できるものが存在する。
ｅ（Ｐ，Ｑ１＋Ｑ２）＝ｅ（Ｐ，Ｑ１）ｅ（Ｐ，Ｑ２） ・・・（１）
ｅ（Ｐ１＋Ｐ２，Ｑ）＝ｅ（Ｐ１，Ｑ）ｅ（Ｐ２，Ｑ） ・・・（２）
ｅ（ａＰ，ｂＱ）＝ｅ（ｂＰ，ａＱ）＝ｅ（ａｂＰ，Ｑ）＝ｅ（Ｐ，ａｂＱ）＝ｅ（Ｐ，Ｑ）ａｂ ・・・（３）
【００３６】
よって、ｇｘがペアリング演算の可能な楕円曲線上の点である場合には、上記の性質から、（３）式にｇｘ、ａｇｘ、ｂｇｘ、ｃｇｘを入力すると、例えば、
ｅ（ａｇ１，ｂｇ２）＝ｅ（ｇ１，ｇ２）ａｂ ・・・（４）
ｅ（ｇ１，ｃｇ２）＝ｅ（ｇ１，ｇ２）ｃ ・・・（５）
となる。したがって、両者の値が一致するかどうかにより、「ａｂ＝ｃ」であるかどうかを判定でき、ｇ１及びｇ２は、ＧＤＨグループＧ１又はＧ２の要素となりうる。
【００３７】
この性質を利用してＧＤＨ署名が構成される。集合Ｇ１及びＧ２は、ＧＤＨグループであり、ｇ１及びｇ２は、それぞれ集合Ｇ１及びＧ２の要素となる点とする。また、一方向性ハッシュ関数Ｈ２を、通常使用される任意のビット長のサイズの数値データが固定のビット長のサイズの数値データに写像変換される方式とは異なり、
Ｈ２：｛０，１｝＊→Ｇ２
のように、任意のビット長のサイズの数値データを楕円曲線上の点として表現されるＧＤＨグループＧ２の要素に写像変換する方式であると定義する。
【００３８】
このとき、ＧＤＨ署名は以下のように定義される。
鍵生成：自然数ｘを選び、ｇ１からｖ＝ｘｇ１を計算する。ｘを署名鍵、楕円曲線上の点ｖを検証鍵とする。
署名：署名者は、メッセージ「ｍ∈｛０，１｝＊」に対しｈ＝Ｈ２（ｍ）を計算し、さらに自分の署名鍵を用いてσ＝ｘｈを計算する。σをｍに対する署名として公開する。
検証：検証者は、メッセージｍからｈ＝Ｈ２（ｍ）を計算し、集合Ｇ１に属するｇ１及びｖと、集合Ｇ２に属するｈ及びσを準備する。ｅ（ｇ１，σ）とｅ（ｖ，ｈ）を計算し、両者の値が一致したら、署名σは、正しい署名と判定する。
【００３９】
このとき、ｈの値は集合Ｇ２の要素となるので、ある自然数ｙを用いてｈ＝ｙｇ２と表現できる。その結果、正しく署名が行われていれば（ｇ１，ｖ，ｈ，σ）＝（ｇ１，ｘｇ１，ｙｇ２，ｘｙｇ２）となる。したがって、正当な署名であれば上記の検証でのペアリング演算は、ｅ（ｇ１，σ）＝ｅ（ｇ１，ｘｙｇ２）＝ｅ（ｇ１，ｇ２）ｘｙ＝ｅ（ｘｇ１，ｙｇ２）＝ｅ（ｖ，ｈ）となり、値が一致することから、検証可能となる。なお、ＧＤＨグループの条件であるＣＤＨ問題の困難性から、署名鍵ｘを知らない第三者がｇ１、ｇ２、ｖ、ｈの値から署名σを導出することは不可能である。
【００４０】
木構造における最下位ノードであるリーフノード１０は、図１に示すように、記憶部１１と、リーフノード一方向性ハッシュ関数演算部１２と、リーフノード署名情報生成部１３と、リーフノード送信部１４とを備える。
【００４１】
記憶部１１は、自身（署名者ｕｌｅａｆのノード）に割り当てられている署名鍵（ｘｌｅａｆ）と、集合Ｇ１に属する値ｇ１（第１の値）に対して、この署名鍵により演算を行って生成される集合Ｇ１に属する検証鍵（ｖｌｅａｆ＝ｘｌｅａｆｇ１）とを記憶する。
【００４２】
リーフノード一方向性ハッシュ関数演算部１２は、自身の署名対象であるメッセージ（ｍｌｅａｆ）に対して、一方向性ハッシュ関数演算を行って、集合Ｇ２（第２のＧＤＨグループ）に属するハッシュ値を生成する。
【００４３】
リーフノード署名情報生成部１３は、リーフノード一方向性ハッシュ関数演算部１２により演算された、自身の署名対象であるメッセージ（ｍｌｅａｆ）のハッシュ値（ｈｌｅａｆ＝Ｈ２（ｍｌｅａｆ））に対して自身の署名鍵（ｘｌｅａｆ）により演算を行い、署名情報（σｌｅａｆ＝ｘｌｅａｆｈｌｅａｆ）を生成する。
【００４４】
リーフノード送信部１４は、生成した署名情報（σｌｅａｆ）とメッセージ（ｍｌｅａｆ）とを次（直上）のノード、すなわち中間ノード２０へ送信する。
【００４５】
また、木構造における最下位（リーフノード１０）より上のノードである中間ノード２０は、図２に示すように、記憶部２１と、中間ノード受信部２２と、中間ノード一方向性ハッシュ関数演算部２３と、中間ノード署名情報生成部２４と、中間ノード送信部２５と、を備える。
【００４６】
記憶部２１は、自身（署名者ｕｕｐのノード）に割り当てられている署名鍵（ｘｕｐ）と、集合Ｇ１に属する値ｇ１に対して、この署名鍵により演算を行って生成される集合Ｇ１に属する検証鍵（ｖｕｐ＝ｘｕｐｇ１）とを記憶する。
【００４７】
中間ノード受信部２２は、直下の一又は複数のノード（署名者ｕｌｏｗのノード）の署名対象であるメッセージ（ｍｌｏｗ）と、これら直下のノードにより生成された署名情報（σｌｏｗ）と、を受信する。
【００４８】
中間ノード一方向性ハッシュ関数演算部２３は、直下のノードから受信したメッセージ（ｍｌｏｗ）のそれぞれと、自身の署名対象であるメッセージ（ｍｕｐ）とに、それぞれ一方向性ハッシュ関数演算を行って、集合Ｇ２に属するハッシュ値を生成する。
【００４９】
中間ノード署名情報生成部２４は、自身のメッセージ（ｍｕｐ）から得られたハッシュ値（ｈｕｐ＝Ｈ２（ｍｕｐ））に対して自身の固有署名鍵（ｘｕｐ）により演算を行った結果と、直下のノードのメッセージ（ｍｌｏｗ）それぞれから得られたハッシュ値（ｈｌｏｗ＝Ｈ２（ｍｌｏｗ））に対して自身の固有署名鍵（ｘｕｐ）により演算を行った結果と、直下のノードの署名情報（σｌｏｗ）とを総和して、自身の中間ノード署名情報（σｕｐ＝Σｌｏｗ（σｌｏｗ＋ｘｕｐｈｌｏｗ）＋ｘｕｐｈｕｐ）を生成する（Σｌｏｗは、直下の一又は複数のノード全てについての総和を示す）。
【００５０】
中間ノード送信部２５は、次（直上）のノードが存在する場合に、自身の署名対象であるメッセージ（ｍｕｐ）と、中間ノード署名情報（σｕｐ）とを、次のノードへ送信する。
【００５１】
このような構成によれば、アグリゲート署名システムは、各中間ノード２０において、直下のノードのメッセージから得られたハッシュ値と、自身のメッセージから得られたハッシュ値とに対して、自身のノードに割り当てられている署名鍵によって演算を行い、さらに直下のノードにより生成された署名情報を総和して、中間ノード署名情報を生成する。この署名情報は、自身のノードに至るまでの木構造における署名経路を保持し、かつ楕円曲線上の点のみで生成される。すなわち、署名者（ノードの数）が多くなっても、署名サイズは増大せず、一定値以下に抑制することができる。
【００５２】
また、木構造における最上位の中間ノードであるルートノード３０は、図３に示すように、記憶部３１と、ルートノード受信部３２と、ルートノード一方向性ハッシュ関数演算部３３と、ルートノード署名情報生成部３４と、公開部３５とを備える。
【００５３】
記憶部３１は、自身（署名者ｕｒｏｏｔのノード）に割り当てられている署名鍵（ｘｒｏｏｔ）と、集合Ｇ１に属する値ｇ１に対して、この署名鍵により演算を行って生成される集合Ｇ１に属する検証鍵（ｖｒｏｏｔ＝ｘｒｏｏｔｇ１）を記憶する。
【００５４】
なお、ルートノード受信部３２は、中間ノード受信部２２と同一の構成であり、ルートノード一方向性ハッシュ関数演算部３３は、中間ノード一方向性ハッシュ関数演算部２３と同一の構成であり、ルートノード署名情報生成部３４は、中間ノード署名情報生成部２４と同一の構成である。
【００５５】
公開部３５は、ルートノード署名情報生成部３４により生成されたルートノード署名情報を公開する。このような構成によれば、ルートノード３０は、自身が生成した署名情報（σｒｏｏｔ）を他のノード、特に後述の検証システムにおける検証ノード４０に対して公開署名情報（σ）として公開することができる。
【００５６】
また、公開部３５は、署名順序を示す木構造内における署名者の配置、及び各署名者と署名を行ったメッセージとの対応関係に関する情報も公開する。
【００５７】
次に、ルートノード３０により公開された公開署名情報（σ）を検証する検証システムについて説明する。検証システムが有する検証ノード４０は、図４に示すように、収集部４１と、検証ノード一方向性ハッシュ関数演算部４２と、検証部４３とを備える。
【００５８】
収集部４１は、署名を行った全てのノード（リーフノード１０、中間ノード２０、ルートノード３０）それぞれのメッセージ（ｍｉ）と、検証鍵（ｖｉ）とを収集する。このとき、収集部４１は、木構造内における署名者の配置、及び各署名者と署名を行ったメッセージとの対応関係に関する情報を、必ずしも入手しなくてもよいが、ルートノード３０から入手するようにしておくことも好ましい。収集部４１がこれらの情報を入手しない場合でも、検証部４３は、署名者の配置、及び各署名者と署名を行ったメッセージとの対応関係に関して、全ての組み合わせを演算することにより、公開署名情報の正当性を検証することが可能である。しかし、収集部４１がこれらの情報を入手し検証部４３へ受け渡すようにしておくと、これらの情報がない場合に比べて検証部４３の演算量が少なくてすむ。
【００５９】
検証ノード一方向性ハッシュ関数演算部４２は、収集部４１により収集された各メッセージ（ｍｉ）に対して、それぞれ一方向性ハッシュ関数演算を行って、各メッセージの集合Ｇ２に属するハッシュ値（ｈｉ＝Ｈ２（ｍｉ））を生成する。
【００６０】
検証部４３は、収集部４１により収集された全てのノードの検証鍵と、検証ノード一方向性ハッシュ関数演算部４２により得られたハッシュ値と、署名者の配置、及び各署名者と署名を行ったメッセージとの対応関係に関する情報と、に基づいて、公開署名情報（σ）の正当性を検証する。このとき、検証部４３は、署名者の配置、及び各署名者と署名を行ったメッセージとの対応関係に関する情報がない場合、これらの対応関係に関する全ての組み合わせを演算する。
【００６１】
具体的には、検証部４３は、各ノードの検証鍵とハッシュ値とから、同一ノードの検証鍵及びハッシュ値によるペアリング演算の結果と、あるノードの検証鍵及び直前のノードのハッシュ値によるペアリング演算の結果とを全て乗じた値、すなわち、
｛Πａｌｌ−ｎｏｄｅ（ｅ（ｖｉ，ｈｉ））｝｛Π（ｅ（ｖｕｐ，ｈｌｏｗ））｝
を計算する。そして、検証部４３は、この計算結果を、ｇ１及び公開署名情報（σ）によるペアリング演算の結果、すなわち、
ｅ（ｇ１，σ）
と比較し、双方が一致する場合、公開署名情報が正当であると判定し、双方が一致しない場合、公開署名情報が正当でないと判定する。
【００６２】
このようにして検証ノード４０は、検証部４３により、全てのノードの検証鍵と、メッセージのハッシュ値と、署名者の配置、及び各署名者と署名を行ったメッセージとの対応関係に関する情報と、に基づいて、公開されているルートノード３０の署名情報の正当性を検証することができる。ここで、署名者の配置、及び各署名者と署名を行ったメッセージとの対応関係に関する情報については、これらの情報がなくても、検証部４３は、署名情報の正当性を検証することが可能である。
【００６３】
したがって、検証システムでは、各ノードにて生成される個々の署名情報等を検証することなく、ルートノード３０により公開された署名情報を数値演算のみで検証することにより、木構造におけるノード間をどのような順序で署名されてきたかを証明することができる。すなわち、順序管理のための別の装置を要することなく、検証ノード４０の処理負荷を低減して効率的に検証作業を実行することができる。なお、検証ノード４０は、検証専用のノードであってもよいし、アグリゲート署名システムのいずれかの中間ノード２０やルートノード３０であってもよい。
【００６４】
次に、アグリゲート署名システムにおいて、各ノードの署名情報を生成する方法と、検証システムにおいて、署名情報の正当性を検証する方法について説明する。
【００６５】
リーフノード１０（署名者ｕｌｅａｆ）は、図５に示すように、リーフノード一方向性ハッシュ関数演算工程ＳＴ１と、リーフノード署名情報生成工程ＳＴ２と、リーフノード送信工程ＳＴ３とにより、リーフノード署名情報を生成して直上のノード（中間ノード２０）へ送信する。
【００６６】
リーフノード一方向性ハッシュ関数演算工程ＳＴ１において、リーフノード１０におけるリーフノード一方向性ハッシュ関数演算部１２は、自身のメッセージ（ｍｌｅａｆ）に対して、一方向性ハッシュ関数演算を行う。
【００６７】
リーフノード署名情報生成工程ＳＴ２において、リーフノード１０におけるリーフノード署名情報生成部１３は、リーフノード一方向性ハッシュ関数演算工程ＳＴ１により演算されたハッシュ値（ｈｌｅａｆ）に対して、自身の署名鍵（ｘｌｅａｆ）により演算を行い、署名情報（σｌｅａｆ）を生成する。
【００６８】
リーフノード送信工程ＳＴ３において、リーフノード１０におけるリーフノード送信部１４は、リーフノード署名情報生成工程ＳＴ２により生成された署名情報（σｌｅａｆ）を、直上の中間ノード２０へ送信する。
【００６９】
リーフノード１０以外の中間ノード２０（署名者ｕｕｐ）は、図６に示すように、中間ノード受信工程ＳＴ１１と、中間ノード一方向性ハッシュ関数演算工程ＳＴ１２と、中間ノード署名情報生成工程ＳＴ１３と、中間ノード送信工程ＳＴ１４とにより、中間ノード署名情報を生成して直上の中間ノード２０へ送信する。
【００７０】
中間ノード受信工程ＳＴ１１において、署名者ｕｕｐのノードにおける中間ノード受信部２２は、直下のノード（署名者ｕｌｏｗ）のメッセージ（ｍｌｏｗ）、及び直下のノードにより生成された署名情報（σｌｏｗ）を受信する。
【００７１】
中間ノード一方向性ハッシュ関数演算工程ＳＴ１２において、署名者ｕｕｐのノードにおける中間ノード一方向性ハッシュ関数演算部２３は、直下のノードのメッセージ（ｍｌｏｗ）及び自身のメッセージ（ｍｌｏｗ）に対して、それぞれ一方向性ハッシュ関数演算を行う。
【００７２】
中間ノード署名情報生成工程ＳＴ１３において、署名者ｕｕｐのノードにおける中間ノード署名情報生成部２４は、自身のメッセージから演算により得られたハッシュ値（ｈｕｐ）に対して自身の署名鍵（ｘｕｐ）により演算を行った結果と、直下のノードのメッセージから演算により得られたハッシュ値（ｈｌｏｗ）に対して自身の署名鍵（ｘｕｐ）により演算を行った結果と、直下のノードから受信した署名情報（σｌｏｗ）とを総和して、自身のノードの署名情報（σｕｐ）を生成する。
【００７３】
中間ノード送信工程ＳＴ１４において、署名者ｕｕｐのノードにおける中間ノード送信部２５は、木構造における直上のノードが存在する場合に、自身のメッセージ（ｍｕｐ）及び自身のノードの署名情報（σｕｐ）を、直上のノードへ送信する。
【００７４】
また、木構造における最上位のノードであるルートノード３０（署名者ｕｒｏｏｔ）は、図７に示すように、ルートノード受信工程ＳＴ２１と、ルートノード一方向性ハッシュ関数演算工程ＳＴ２２と、ルートノード署名情報生成工程ＳＴ２３と、署名情報公開工程ＳＴ２４とにより、アグリゲート署名システムにおける公開署名情報（σ）を公開する。
【００７５】
ルートノード受信工程ＳＴ２１において、ルートノード３０におけるルートノード受信部３２は、直下のノード（署名者ｕｌｏｗ）のメッセージ（ｍｌｏｗ）、及び直下のノードにより生成された署名情報（σｌｏｗ）を受信する。
【００７６】
ルートノード一方向性ハッシュ関数演算工程ＳＴ２２において、ルートノード３０におけるルートノード一方向性ハッシュ関数演算部３３は、直下のノードのメッセージ（ｍｌｏｗ）及び自身のメッセージ（ｍｒｏｏｔ）に対して、それぞれ一方向性ハッシュ関数演算を行う。
【００７７】
ルートノード署名情報生成工程ＳＴ２３において、ルートノード３０におけるルートノード署名情報生成部３４は、自身のメッセージから演算により得られたハッシュ値（ｈｒｏｏｔ）に対して自身の署名鍵（ｘｒｏｏｔ）により演算を行った結果と、直下のノードのメッセージから演算により得られたハッシュ値（ｈｌｏｗ）に対して自身の署名鍵（ｘｒｏｏｔ）により演算を行った結果と、直下のノードから受信した署名情報（σｌｏｗ）とを総和して、自身のノードの署名情報（σｒｏｏｔ）を生成する。
【００７８】
署名情報公開工程ＳＴ２４において、ルートノード３０における公開部３５は、ルートノード署名情報生成工程ＳＴ２３により生成された署名情報を、公開署名情報（σ）として公開する。
【００７９】
このように、アグリゲート署名システムに係るアグリゲート署名方法によれば、各中間ノード２０において、直下のノードのメッセージから得られたハッシュ値と、自身のメッセージから得られたハッシュ値とに対して、自身のノードに割り当てられている署名鍵によって演算を行い、さらに直下のノードにより生成された署名情報を総和して、中間ノード署名情報を生成する。この署名情報は、自身のノードに至るまでの署名経路を保持し、かつ楕円曲線上の点のみで生成される。すなわち、署名者（ノードの数）が多くなっても、署名サイズは増大せず、一定値以下に抑制することができる。
【００８０】
また、検証システムにおける検証ノード４０は、図８に示すように、収集工程ＳＴ３１と、検証ノード一方向性ハッシュ関数演算工程ＳＴ３２と、検証工程ＳＴ３３とにより、公開署名情報（σ）の正当性を検証する。
【００８１】
収集工程ＳＴ３１において、収集部４１は、署名が行われた全てのノードのメッセージ（ｍｉ）、及びこれら全てのノードの検証鍵（ｖｉ）を収集する。
【００８２】
検証ノード一方向性ハッシュ関数演算工程ＳＴ３２において、検証ノード一方向性ハッシュ関数演算部４２は、収集工程ＳＴ３１により収集されたメッセージのそれぞれに対して、一方向性ハッシュ関数演算を行う。
【００８３】
検証工程ＳＴ３３において、検証部４３は、収集工程ＳＴ３１により収集された全てのノードの検証鍵、及び全てのノードのメッセージから検証ノード一方向性ハッシュ関数演算工程ＳＴ３２で得られたハッシュ値に基づいて、公開署名情報（σ）の正当性を検証する。
【００８４】
このようにして、検証システムは、検証工程ＳＴ３３により、全てのノードの検証鍵とメッセージのハッシュ値とに基づいて、公開されている中間ノード署名情報（公開署名情報σ）の正当性を検証することができる。
【００８５】
したがって、検証システムに係る検証方法では、各ノードにて生成される個々の署名情報等を検証することなく、ルートノード３０により公開された署名情報を数値演算のみで検証することにより、木構造におけるノード間をどのような順序で署名されてきたかを証明することができる。すなわち、順序管理のための別の装置を要することなく、検証工程ＳＴ３３の処理負荷を低減して検証作業を実行することができる。
【００８６】
［実施例］
ここで、木構造が３分木３階層で構成されている場合におけるアグリゲート署名システムの動作について図９を参照しながら具体的に説明する。なお、以下では、第１層をルートノード３０であるとし、第２層を中間ノード２０とし、第３層をリーフノード１０とする。
【００８７】
すなわち、第１層には、一つのルートノード３０が配置されている。また、第２層には、三つの中間ノード２０が配置され、ｕｒｏｏｔの直下にｕ１からｕ３が配置されている。また、第３層には、九つのリーフノード１０が配置され、ｕ１の直下にｕ１１からｕ１３が配置され、ｕ２の直下にｕ２１からｕ２３が配置され、ｕ３の直下にｕ３１からｕ３３が配置されている。
【００８８】
また、認証局（ＣＡ）は、予め各ノードに重複しない署名鍵と検証鍵を、以下のように付与している。なお、ｓとｔはそれぞれ、１≦ｓ≦３、１≦ｔ≦３となる整数の符号である。
第１層：（署名鍵，検証鍵）＝（ｘｒｏｏｔ，ｖｒｏｏｔ）＝（ｘｒｏｏｔ，ｘｒｏｏｔｇ１）
第２層：（署名鍵，検証鍵）＝（ｘｓ，ｖｓ）＝（ｘｓ，ｘｓｇ１）
第３層：（署名鍵，検証鍵）＝（ｘｓｔ，ｖｓｔ）＝（ｘｓｔ，ｘｓｔｇ１）
【００８９】
第３層の九つのリーフノード１０（ユーザｕｓｔ）は、自身の署名対象であるメッセージ（ｍｓｔ）に対してハッシュ値（ｈｓｔ＝Ｈ２（ｍｓｔ））を求め、ハッシュ値に対して自身の署名鍵ｘｓｔにより演算を行い、署名情報（σｓｔ＝ｘｓｔｈｓｔ）を生成する。また、リーフノード１０（ユーザｕｓｔ）は、生成した署名情報（σｓｔ）と、メッセージ（ｍｓｔ）とを直上のノード（ユーザｕｓ）に送信する。
【００９０】
第２層の三つの中間ノード２０（ユーザｕｓ）は、まず自身の署名対象であるメッセージ（ｍｓ）から、ハッシュ値（ｈｓ＝Ｈ２（ｍｓ））を求める。
次に、中間ノード２０（ユーザｕｓ）は、直下のノード（ユーザｕｓ１、ｕｓ２、ｕｓ３）から受信したメッセージ（ｍｓ１、ｍｓ２、ｍｓ３）から、ハッシュ値（ｈｓ１＝Ｈ２（ｍｓ１）、ｈｓ２＝Ｈ２（ｍｓ２）、ｈｓ３＝Ｈ２（ｍｓ３））を求める。
【００９１】
さらに、中間ノード２０（ユーザｕｓ）は、直下のノードから受信した署名情報（σｓ１、σｓ２、σｓ３）を用いて、
σｓ＝σｓ１＋ｘｓｈｓ１＋σｓ２＋ｘｓｈｓ２＋σｓ３＋ｘｓｈｓ３
＋ｘｓｈｓ ・・・（６）
＝ｘｓ１ｈｓ１＋ｘｓｈｓ１＋ｘｓ２ｈｓ２＋ｘｓｈｓ２
＋ｘｓ３ｈｓ３＋ｘｓｈｓ３＋ｘｓｈｓ ・・・（７）
を計算する。そして、中間ノード２０（ユーザｕｓ）は、生成した署名情報（σｓ）と、メッセージ（ｍｓ）とを直上のノード（ユーザｕｒｏｏｔ）に送信する。
【００９２】
第１層のルートノード３０（ユーザｕｒｏｏｔ）は、まず自身の署名対象であるメッセージ（ｍｒｏｏｔ）から、ハッシュ値（ｈｒｏｏｔ＝Ｈ２（ｍｒｏｏｔ））を求める。
次に、ルートノード３０（ユーザｕｒｏｏｔ）は、直下のノード（ユーザｕ１、ｕ２、ｕ３）から受信したメッセージ（ｍ１、ｍ２、ｍ３）から、ハッシュ値（ｈ１＝Ｈ２（ｍ１）、ｈ２＝Ｈ２（ｍ２）、ｈ３＝Ｈ２（ｍ３））を求める。
【００９３】
さらに、ルートノード３０（ユーザｕｒｏｏｔ）は、直下のノードから受信した署名情報（σ１、σ２、σ３）を用いて、
σ＝σ１＋ｘｒｏｏｔｈ１＋σ２＋ｘｒｏｏｔｈ２＋σ３＋ｘｒｏｏｔｈ３
＋ｘｒｏｏｔｈｒｏｏｔ ・・・（８）
＝ｘ１１ｈ１１＋ｘ１ｈ１１＋ｘ１２ｈ１２＋ｘ１ｈ１２
＋ｘ１３ｈ１３＋ｘ１ｈ１３＋ｘ１ｈ１＋ｘｒｏｏｔｈ１
＋ｘ２１ｈ２１＋ｘ２ｈ２１＋ｘ２２ｈ２２＋ｘ２ｈ２２
＋ｘ２３ｈ２３＋ｘ２ｈ２３＋ｘ２ｈ２＋ｘｒｏｏｔｈ２
＋ｘ３１ｈ３１＋ｘ３ｈ３１＋ｘ３２ｈ３２＋ｘ３ｈ３２
＋ｘ３３ｈ３３＋ｘ３ｈ３３＋ｘ３ｈ３＋ｘｒｏｏｔｈ３
＋ｘｒｏｏｔｈｒｏｏｔ ・・・（９）
を計算する。そして、ルートノード３０（ユーザｕｒｏｏｔ）は、生成した署名情報（σ）を、全ユーザのアグリゲート署名情報として公開する。
【００９４】
また、ルートノード３０は、署名者の木構造における署名位置情報も公開する。署名位置情報は、例えば、｛（ｕ１１，ｕ１），（ｕ１２，ｕ１），（ｕ１３，ｕ１），（ｕ２１，ｕ２），（ｕ２２，ｕ２），（ｕ２３，ｕ２），（ｕ３１，ｕ３），（ｕ３２，ｕ３），（ｕ３３，ｕ３），（ｕ１，ｕｒｏｏｔ），（ｕ２，ｕｒｏｏｔ），（ｕ３，ｕｒｏｏｔ）｝のように、隣接するノードの組み合わせの列として表現される。
【００９５】
このようにして、アグリゲート署名システムは、木構造上において連続（隣接）する２つのノード間の関係を署名鍵とハッシュ値の積で表すことにより、木構造を表現することができる。また、ノードの数が増えても、公開されるのは、ルートノード３０で生成される公開署名情報（σ）である。この署名情報は楕円曲線上の点であるため、情報のサイズ（容量）は増大せず、一定値以下に抑制することができ、効率的に順序付きアグリゲート署名を生成することができる。
【００９６】
また、検証ノード４０は、以下の検証過程１から検証過程３により公開署名情報（σ）の正当性を検証する。
【００９７】
（検証過程１）検証ノード４０は、署名を行った全てのノードが署名対象としたメッセージ（ｍｒｏｏｔ、ｍ１、ｍ２、ｍ３、ｍ１１、ｍ１２、ｍ１３、ｍ２１、ｍ２２、ｍ２３、ｍ３１、ｍ３２、ｍ３３）を収集し、これらに対してハッシュ値（ｈｒｏｏｔ＝Ｈ２（ｍｒｏｏｔ）、ｈ１＝Ｈ２（ｍ１）、ｈ２＝Ｈ２（ｍ２）、ｈ３＝Ｈ２（ｍ３）、ｈ１１＝Ｈ２（ｍ１１）、ｈ１２＝Ｈ２（ｍ１２）、ｈ１３＝Ｈ２（ｍ１３）、ｈ２１＝Ｈ２（ｍ２１）、ｈ２２＝Ｈ２（ｍ２２）、ｈ２３＝Ｈ２（ｍ２３）、ｈ３１＝Ｈ２（ｍ３１）、ｈ３２＝Ｈ２（ｍ３２）、ｈ３３＝Ｈ２（ｍ３３））を求める。
【００９８】
（検証過程２）検証ノード４０は、署名を行った全てのノードの検証鍵（ｖｒｏｏｔ、ｖ１、ｖ２、ｖ３、ｖ１１、ｖ１２、ｖ１３、ｖ２１、ｖ２２、ｖ２３、ｖ３１、ｖ３２、ｖ３３）を収集する。
【００９９】
（検証過程３）検証ノード４０は、公開された公開署名情報（σ）の正当性を検証する。具体的には、検証ノード４０は、検証過程１で求めたハッシュ値と、収集した全てのノードの検証鍵とから、
ｅ（ｖ１１，ｈ１１）・ｅ（ｖ１，ｈ１１）
・ｅ（ｖ１２，ｈ１２）・ｅ（ｖ１，ｈ１２）
・ｅ（ｖ１３，ｈ１３）・ｅ（ｖ１，ｈ１３）
・ｅ（ｖ１，ｈ１）・ｅ（ｖｒｏｏｔ，ｈ１）
・ｅ（ｖ２１，ｈ２１）・ｅ（ｖ２，ｈ２１）
・ｅ（ｖ２２，ｈ２２）・ｅ（ｖ２，ｈ２２）
・ｅ（ｖ２３，ｈ２３）・ｅ（ｖ２，ｈ２３）
・ｅ（ｖ２，ｈ２）・ｅ（ｖｒｏｏｔ，ｈ２）
・ｅ（ｖ３１，ｈ３１）・ｅ（ｖ３，ｈ３１）
・ｅ（ｖ３２，ｈ３２）・ｅ（ｖ３，ｈ３２）
・ｅ（ｖ３３，ｈ３３）・ｅ（ｖ３，ｈ３３）
・ｅ（ｖ３，ｈ３）・ｅ（ｖｒｏｏｔ，ｈ３）
・ｅ（ｖｒｏｏｔ，ｈｒｏｏｔ） ・・・（１０）
を計算し、この値とｅ（ｇ１，σ）の値が一致することを確認する。これらの値が一致した場合には、公開署名情報（σ）が正当であると判断する。
【０１００】
ここで、（検証過程３）における「ｅ（ｇ１，σ）」を展開すると、
ｅ（ｇ１，σ）
＝ｅ（ｇ１，ｘ１１ｈ１１）・ｅ（ｇ１，ｘ１ｈ１１）
・ｅ（ｇ１，ｘ１２ｈ１２）・ｅ（ｇ１，ｘ１ｈ１２）
・ｅ（ｇ１，ｘ１３ｈ１３）・ｅ（ｇ１，ｘ１ｈ１３）
・ｅ（ｇ１，ｘ１ｈ１）・ｅ（ｇ１，ｘｒｏｏｔｈ１）
・ｅ（ｇ１，ｘ２１ｈ２１）・ｅ（ｇ１，ｘ２ｈ２１）
・ｅ（ｇ１，ｘ２２ｈ２２）・ｅ（ｇ１，ｘ２ｈ２２）
・ｅ（ｇ１，ｘ２３ｈ２３）・ｅ（ｇ１，ｘ２ｈ２３）
・ｅ（ｇ１，ｘ２ｈ２）・ｅ（ｇ１，ｘｒｏｏｔｈ２）
・ｅ（ｇ１，ｘ３１ｈ３１）・ｅ（ｇ１，ｘ３ｈ３１）
・ｅ（ｇ１，ｘ３２ｈ３２）・ｅ（ｇ１，ｘ３ｈ３２）
・ｅ（ｇ１，ｘ３３ｈ３３）・ｅ（ｇ１，ｘ３ｈ３３）
・ｅ（ｇ１，ｘ３ｈ３）・ｅ（ｇ１，ｘｒｏｏｔｈ３）
・ｅ（ｇ１，ｘｒｏｏｔｈｒｏｏｔ） ・・・（１１）
＝ｅ（ｘ１１ｇ１，ｈ１１）・ｅ（ｘ１ｇ１，ｈ１１）
・ｅ（ｘ１２ｇ１，ｈ１２）・ｅ（ｘ１ｇ１，ｈ１２）
・ｅ（ｘ１３ｇ１，ｈ１３）・ｅ（ｘ１ｇ１，ｈ１３）
・ｅ（ｘ１ｇ１，ｈ１）・ｅ（ｘｒｏｏｔｇ１，ｈ１）
・ｅ（ｘ２１ｇ１，ｈ２１）・ｅ（ｘ２ｇ１，ｈ２１）
・ｅ（ｘ２２ｇ１，ｈ２２）・ｅ（ｘ２ｇ１，ｈ２２）
・ｅ（ｘ２３ｇ１，ｈ２３）・ｅ（ｘ２ｇ１，ｈ２３）
・ｅ（ｘ２ｇ１，ｈ２）・ｅ（ｘｒｏｏｔｇ１，ｈ２）
・ｅ（ｘ３１ｇ１，ｈ３１）・ｅ（ｘ３ｇ１，ｈ３１）
・ｅ（ｘ３２ｇ１，ｈ３２）・ｅ（ｘ３ｇ１，ｈ３２）
・ｅ（ｘ３３ｇ１，ｈ３３）・ｅ（ｘ３ｇ１，ｈ３３）
・ｅ（ｘ３ｇ１，ｈ３）・ｅ（ｘｒｏｏｔｇ１，ｈ３）
・ｅ（ｘｒｏｏｔｇ１，ｈｒｏｏｔ） ・・・（１２）
＝ｅ（ｖ１１，ｈ１１）・ｅ（ｖ１，ｈ１１）
・ｅ（ｖ１２，ｈ１２）・ｅ（ｖ１，ｈ１２）
・ｅ（ｖ１３，ｈ１３）・ｅ（ｖ１，ｈ１３）
・ｅ（ｖ１，ｈ１）・ｅ（ｖｒｏｏｔ，ｈ１）
・ｅ（ｖ２１，ｈ２１）・ｅ（ｖ２，ｈ２１）
・ｅ（ｖ２２，ｈ２２）・ｅ（ｖ２，ｈ２２）
・ｅ（ｖ２３，ｈ２３）・ｅ（ｖ２，ｈ２３）
・ｅ（ｖ２，ｈ２）・ｅ（ｖｒｏｏｔ，ｈ２）
・ｅ（ｖ３１，ｈ３１）・ｅ（ｖ３，ｈ３１）
・ｅ（ｖ３２，ｈ３２）・ｅ（ｖ３，ｈ３２）
・ｅ（ｖ３３，ｈ３３）・ｅ（ｖ３，ｈ３３）
・ｅ（ｖ３，ｈ３）・ｅ（ｖｒｏｏｔ，ｈ３）
・ｅ（ｖｒｏｏｔ，ｈｒｏｏｔ） ・・・（１３）
となり、署名の過程が正しく行われていれば、（１０）式と一致する。よって、公開されているユーザの検証鍵と、全てのメッセージから求めたハッシュ値とから、アグリゲート署名の検証が可能となる。
【０１０１】
ここで、σの値に着目すると、ユーザｕｓｔはｈｓｔにのみ署名処理（ｘｓｔｈｓｔの演算）を行っており、他のｈｓ及びｈｒｏｏｔにはこのような署名処理を行っていない。これにより、ユーザｕｓｔが最初、すなわち木構造におけるリーフノード１０の署名者であることが分かる。
【０１０２】
また、「ｘｓｈｓｔ」の項により、この最初の署名者が署名処理したｈｓｔに対して署名処理を行っているのがユーザｕｓであることが表されているので、このユーザｕｓが２番目（中間ノード２０）の署名者であることが分かる。ユーザｕｓは同時にｈｓに対して署名処理（ｘｓｈｓ）を行っている。同様に「ｘｒｏｏｔｈｓ」の項により、このｈｓに対して署名処理を行っているのがユーザｕｒｏｏｔであることが表されているので、このユーザｕｒｏｏｔが３番目の署名者であることが分かる。
【０１０３】
さらに、ｈｒｏｏｔに対して署名処理を行っているユーザはなく、ユーザｕｒｏｏｔで収束しているため、この３番目の署名者がルートノード３０であることが分かる。
【０１０４】
また、（１１）式において、ＣＤＨ問題や楕円曲線上の離散対数問題から、秘密情報である署名鍵を知らない第三者が、右辺の各項（ｘαｈβ又はｘβｈβ）を任意に取り除くことはできないため、第三者による順序の入れ替えは不可能である。すなわち、アグリゲート署名システム及び検証システムが採用する本署名方式は、木構造における署名順序を署名鍵とハッシュ値の積により表現することができる。
【０１０５】
また、署名者の数（ノードの数）が増えても、公開される情報は公開署名情報（σ）のみである。この公開署名情報（σ）は一つの楕円曲線上の点であるため、情報のサイズ（容量）は増大せず、一定値以下に抑制することができる。
【０１０６】
さらに、検証システムでは、検証過程３で示した数値演算のみで検証することにより、ノード間をどのような順序で署名されてきたかを証明することができる。したがって、順序管理のための装置を別途用意することなく、検証システムの処理負荷を低減して効率的に検証作業を実行することができる。
【０１０７】
＜第２実施形態＞
以下、本発明の実施形態の一例である第２実施形態について説明する。なお、第１実施形態と同様の構成については、同一の符号を付し、説明を省略又は簡略化する。
【０１０８】
本実施形態に係るアグリゲート署名システムにおいて、リーフノード１０は、リーフノード一方向性ハッシュ関数演算部１２及びリーフノード送信部１４の構成が第１実施形態と異なる。
すなわち、リーフノード送信部１４は、リーフノード一方向性ハッシュ関数演算部１２の演算結果であるハッシュ値（ｈｌｅａｆ）とリーフノード署名情報（σｌｅａｆ）とを、直上のノード（中間ノード２０）へ送信する。
【０１０９】
中間ノード２０は、中間ノード受信部２２、中間ノード一方向性ハッシュ関数演算部２３、及び中間ノード送信部２５の構成が第１実施形態と異なる。
すなわち、中間ノード受信部２２は、直下のノードから、メッセージ（ｍｌｏｗ）の代わりにハッシュ値（ｈｌｏｗ）を受信して中間ノード署名情報生成部２４へ供給する。これにより、中間ノード２０は、直前のノードのメッセージ（ｍｌｏｗ）に対して一方向性ハッシュ関数演算を行う必要がなくなる。
【０１１０】
また、中間ノード送信部２５は、中間ノード一方向性ハッシュ関数演算部２３の演算結果であるハッシュ値（ｈｕｐ）と中間ノード署名情報（σｕｐ）とを、直上のノードへ送信する。
【０１１１】
ルートノード３０は、ルートノード受信部３２及びルートノード一方向性ハッシュ関数演算部３３の構成が第１実施形態と異なる。
すなわち、ルートノード受信部３２は、直下のノードから、メッセージ（ｍｌｏｗ）の代わりにハッシュ値（ｈｌｏｗ）を受信してルートノード署名情報生成部３４へ供給する。これにより、ルートノード３０は、直下のノードのメッセージ（ｍｌｏｗ）に対して一方向性ハッシュ関数演算を行う必要がなくなる。
【０１１２】
本実施形態に係る検証システムにおいて、検証ノード４０は、収集部４１の構成が第１実施形態と異なる。さらに、検証ノード４０は、第１実施形態における検証ノード一方向性ハッシュ関数演算部４２を必要としない。
【０１１３】
すなわち、収集部４１は、各ノードから、メッセージ（ｍｉ）の代わりにハッシュ値（ｈｉ）を受信して検証部４３へ供給する。これにより、検証ノード４０は、各ノードのメッセージ（ｍｉ）に対して一方向性ハッシュ関数演算を行う必要がなくなる。
【０１１４】
本実施形態によれば、各ノードにおける一方向性ハッシュ関数演算の処理負荷を低減することができる。
具体的には、第１実施形態における中間ノード一方向性ハッシュ関数演算工程ＳＴ１２と、ルートノード一方向性ハッシュ関数演算工程ＳＴ２２の処理負荷が低減され、検証ノード一方向性ハッシュ関数演算工程ＳＴ３２は不要となる。
【０１１５】
なお、各ノード間においては、メッセージ（ｍｉ）又はハッシュ値（ｈｉ）のいずれかが送受信されればよく、アグリゲート署名システム及び検証システム内において統一されていなくてもよい。また、メッセージ及びハッシュ値の双方を送受信することとしてもよい。
【０１１６】
以上で説明した各実施形態におけるアグリゲート署名システム及び検証システムは、各ノードで独立したメッセージを署名対象とするので、例えば署名済みの素材を集めてコンテンツを生成する場合のように、下位（部分）から上位（全体）へのボトムアップの署名方式を提供することができる。
【０１１７】
また、上述の各実施形態において、ペアリング関数への入力である２つの引数は、ペアリングの演算が可能な楕円曲線上の点ｇ１又はｇ２のスカラー倍として表されるが、この楕円曲線は、第１引数と第２引数とで異なっている。すなわち、ペアリング関数の第１引数用と第２引数用とに、それぞれ異なる楕円曲線（Ｇ１又はＧ２）上の２点（ｇ１又はｇ２）が与えられている。具体的には、第１引数に関する検証鍵は、ｇ１のスカラー倍（Ｇ１上の点）となり、第２引数に関するハッシュ値及び署名情報は、ｇ２のスカラー倍（Ｇ２上の点）となる。
【０１１８】
このことにより、演算回数が増加する場合があるが、ペアリング関数の演算において並列して処理できるため、計算時間の短縮が期待できる。
また、集合Ｇ１又はＧ２のいずれかに不具合が発見された場合、一方を共用する、又は他のＧＤＨグループに交換することにより、アグリゲート署名システム及び検証システムが維持される
【０１１９】
以上、本発明の実施形態について説明したが、本発明は上述した実施形態に限るものではない。また、本発明の実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、本発明の実施形態に記載されたものに限定されるものではない。
【０１２０】
上述の実施形態では、ルートノード３０が公開部３５を備えているが、他のノード（中間ノード２０、リーフノード１０）も備えていてよい。この場合、検証ノード４０は、公開された署名情報に基づいて、公開したノードに至るまでの署名経路の正当性を検証可能である。さらに、各ノードの公開部３５は、自身のノードの検証鍵を公開し、検証ノード４０へ提供してもよい。
【０１２１】
また、上述の実施形態では、署名鍵及び検証鍵は、認証局によって割り当てられることとしたが、本発明はこれには限られない。例えば、アグリゲート署名システムにおいて、署名鍵となる自然数ｘ、及び集合Ｇ１に属する値ｇ１を決定し、検証鍵を演算により算出（ｖ＝ｘｇ１）してもよい。
【０１２２】
また、上述の実施形態では、中間ノード２０に対して直下のノードが複数存在する木構造における順序付き多重署名について説明したが、本発明はこれには限られない。すなわち、中間ノード２０に対して直下のノードが単一であり、複数のノードが一列に連なっている場合にも、本発明は適用可能である。
【０１２３】
この場合、アグリゲート署名システム及び検証システムは、各ノードで独立したメッセージを署名対象とするので、例えば電子掲示板やブログのコメント等のように、前のメッセージを受けて次のメッセージを追加する連作に対して利用することができる。
【０１２４】
なお、この場合、ルートノード３０（最終ノード）が公開する署名者の署名順序情報（署名位置情報）は、例えば、｛（１，ｕ１），（２，ｕ２），・・・，（ｋ，ｕｋ）｝のように、順序番号を付加したノードの列として表現される。
【０１２５】
また、アグリゲート署名システム及び検証システムによる一連の処理は、ソフトウェアにより行うこともできる。一連の処理をソフトウェアによって行う場合には、そのソフトウェアを構成するプログラムが、汎用のコンピュータ等にインストールされる。また、当該プログラムは、ＣＤ−ＲＯＭのようなリムーバブルメディアに記録されてユーザに配布されてもよいし、ネットワークを介してユーザのコンピュータにダウンロードされることにより配布されてもよい。
【符号の説明】
【０１２６】
１０ リーフノード
１１ 記憶部
１２ リーフノード一方向性ハッシュ関数演算部
１３ リーフノード署名情報生成部
１４ リーフノード送信部
２０ 中間ノード
２１ 記憶部
２２ 中間ノード受信部
２３ 中間ノード一方向性ハッシュ関数演算部
２４ 中間ノード署名情報生成部
２５ 中間ノード送信部
３０ ルートノード
３１ 記憶部
３２ ルートノード受信部
３３ ルートノード一方向性ハッシュ関数演算部
３４ ルートノード署名情報生成部
３５ 公開部
４０ 検証ノード
４１ 収集部
４２ 検証ノード一方向性ハッシュ関数演算部
４３ 検証部
【特許請求の範囲】
【請求項１】
あるノードから別のノードへの順序付きのアグリゲート署名を行うアグリゲート署名システムであって、
各ノードには、所定の自然数からなる署名鍵と、第１のＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する第１の値に対して、当該署名鍵により演算を行って生成される当該第１のＧＤＨグループに属する検証鍵とがそれぞれ割り当てられており、当該各ノードは、
直前のノードが存在する場合、当該直前のノードの署名対象であるメッセージ又は当該メッセージのハッシュ値、及び当該直前のノードの署名情報を受信する受信部と、
自身のメッセージと、前記直前のノードが存在する場合、当該直前のノードのメッセージとに対して、それぞれ一方向性ハッシュ関数演算を行って、各メッセージの第２のＧＤＨグループに属するハッシュ値を生成する署名ノード一方向性ハッシュ関数演算部と、
自身のメッセージのハッシュ値に対して自身の署名鍵により演算を行った結果と、前記直前のノードが存在する場合、当該直前のノードのメッセージのハッシュ値に対して自身のノードの署名鍵により演算を行った結果、及び前記直前のノードの署名情報とを総和して、自身の署名情報を生成する署名情報生成部と、
直後のノードが存在する場合、自身のメッセージ又は当該メッセージのハッシュ値、及び自身の署名情報を、当該直後のノードへ送信する送信部と、を備えるアグリゲート署名システム。
【請求項２】
前記署名情報生成部は、前記直前のノードが複数存在する場合、自身のメッセージのハッシュ値に対して自身の署名鍵により演算を行った結果と、前記直前のノードそれぞれのメッセージのハッシュ値に対して自身のノードの署名鍵により演算を行った複数の結果と、前記直前のノードそれぞれの署名情報とを総和して、自身の署名情報を生成する請求項１に記載のアグリゲート署名システム。
【請求項３】
前記各ノードは、自身の署名情報を公開する公開部を備える請求項１又は請求項２に記載のアグリゲート署名システム。
【請求項４】
前記公開部は、前記各ノードの順序情報をさらに公開する請求項３に記載のアグリゲート署名システム。
【請求項５】
請求項３又は請求項４に記載のアグリゲート署名システムに備えられている前記公開部により公開された署名情報を検証する検証システムであって、
前記公開された署名情報が生成される過程の全てのノードのメッセージ又は当該メッセージのハッシュ値、及び当該全てのノードの検証鍵を収集する収集部と、
前記収集部により収集されたメッセージに対して、それぞれ一方向性ハッシュ関数演算を行って、各メッセージの前記第２のＧＤＨグループに属するハッシュ値を生成する検証ノード一方向性ハッシュ関数演算部と、
前記全てのノードの検証鍵、及び前記全てのノードのメッセージのハッシュ値に基づいて、前記公開された署名情報の正当性を検証する検証部と、を備える検証システム。
【請求項６】
前記検証部は、同一ノードの検証鍵及びハッシュ値によるペアリング演算の結果と、あるノードの検証鍵及び当該ノードの直前のノードのハッシュ値によるペアリング演算の結果とを全て乗じた値を、前記第１の値及び前記公開された署名情報によるペアリング演算の結果と比較し、双方が一致する場合、前記公開された署名情報が正当であると判定し、双方が一致しない場合、前記公開された署名情報が正当でないと判定する請求項５に記載の検証システム。
【請求項７】
あるノードから別のノードへの順序付きのアグリゲート署名を行うアグリゲート署名方法であって、
各ノードには、所定の自然数からなる署名鍵と、第１のＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する第１の値に対して、当該署名鍵により演算を行って生成される当該第１のＧＤＨグループに属する検証鍵とがそれぞれ割り当てられており、当該各ノードが、
第１のＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する第１の値に対して、自身の署名鍵により演算を行って、当該第１のＧＤＨグループに属する自身の検証鍵を生成する検証鍵生成工程と、
直前のノードが存在する場合、当該直前のノードの署名対象であるメッセージ又は当該メッセージのハッシュ値、及び当該直前のノードの署名情報を受信する受信工程と、
自身のメッセージと、前記直前のノードが存在する場合、当該直前のノードのメッセージとに対して、それぞれ一方向性ハッシュ関数演算を行って、各メッセージの第２のＧＤＨグループに属するハッシュ値を生成する署名ノード一方向性ハッシュ関数演算工程と、
自身のメッセージのハッシュ値に対して自身の署名鍵により演算を行った結果と、前記直前のノードが存在する場合、当該直前のノードのメッセージのハッシュ値に対して自身のノードの署名鍵により演算を行った結果、及び前記直前のノードの署名情報とを総和して、自身の署名情報を生成する署名情報生成工程と、
直後のノードが存在する場合、自身のメッセージ又は当該メッセージのハッシュ値、及び自身の署名情報を、当該直後のノードへ送信する送信工程と、を実行するアグリゲート署名方法。
【請求項８】
あるノードから別のノードへの順序付きのアグリゲート署名を行うアグリゲート署名方法をコンピュータに実行させるためのアグリゲート署名プログラムであって、
各ノードには、所定の自然数からなる署名鍵と、第１のＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する第１の値に対して、当該署名鍵により演算を行って生成される当該第１のＧＤＨグループに属する検証鍵とがそれぞれ割り当てられており、当該各ノードに、
第１のＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する第１の値に対して、自身の署名鍵により演算を行って、当該第１のＧＤＨグループに属する自身の検証鍵を生成する検証鍵生成工程と、
直前のノードが存在する場合、当該直前のノードの署名対象であるメッセージ又は当該メッセージのハッシュ値、及び当該直前のノードの署名情報を受信する受信工程と、
自身のメッセージと、前記直前のノードが存在する場合、当該直前のノードのメッセージとに対して、それぞれ一方向性ハッシュ関数演算を行って、各メッセージの第２のＧＤＨグループに属するハッシュ値を生成する署名ノード一方向性ハッシュ関数演算工程と、
自身のメッセージのハッシュ値に対して自身の署名鍵により演算を行った結果と、前記直前のノードが存在する場合、当該直前のノードのメッセージのハッシュ値に対して自身のノードの署名鍵により演算を行った結果、及び前記直前のノードの署名情報とを総和して、自身の署名情報を生成する署名情報生成工程と、
直後のノードが存在する場合、自身のメッセージ又は当該メッセージのハッシュ値、及び自身の署名情報を、当該直後のノードへ送信する送信工程と、を実行させるためのアグリゲート署名プログラム。
【請求項１】
あるノードから別のノードへの順序付きのアグリゲート署名を行うアグリゲート署名システムであって、
各ノードには、所定の自然数からなる署名鍵と、第１のＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する第１の値に対して、当該署名鍵により演算を行って生成される当該第１のＧＤＨグループに属する検証鍵とがそれぞれ割り当てられており、当該各ノードは、
直前のノードが存在する場合、当該直前のノードの署名対象であるメッセージ又は当該メッセージのハッシュ値、及び当該直前のノードの署名情報を受信する受信部と、
自身のメッセージと、前記直前のノードが存在する場合、当該直前のノードのメッセージとに対して、それぞれ一方向性ハッシュ関数演算を行って、各メッセージの第２のＧＤＨグループに属するハッシュ値を生成する署名ノード一方向性ハッシュ関数演算部と、
自身のメッセージのハッシュ値に対して自身の署名鍵により演算を行った結果と、前記直前のノードが存在する場合、当該直前のノードのメッセージのハッシュ値に対して自身のノードの署名鍵により演算を行った結果、及び前記直前のノードの署名情報とを総和して、自身の署名情報を生成する署名情報生成部と、
直後のノードが存在する場合、自身のメッセージ又は当該メッセージのハッシュ値、及び自身の署名情報を、当該直後のノードへ送信する送信部と、を備えるアグリゲート署名システム。
【請求項２】
前記署名情報生成部は、前記直前のノードが複数存在する場合、自身のメッセージのハッシュ値に対して自身の署名鍵により演算を行った結果と、前記直前のノードそれぞれのメッセージのハッシュ値に対して自身のノードの署名鍵により演算を行った複数の結果と、前記直前のノードそれぞれの署名情報とを総和して、自身の署名情報を生成する請求項１に記載のアグリゲート署名システム。
【請求項３】
前記各ノードは、自身の署名情報を公開する公開部を備える請求項１又は請求項２に記載のアグリゲート署名システム。
【請求項４】
前記公開部は、前記各ノードの順序情報をさらに公開する請求項３に記載のアグリゲート署名システム。
【請求項５】
請求項３又は請求項４に記載のアグリゲート署名システムに備えられている前記公開部により公開された署名情報を検証する検証システムであって、
前記公開された署名情報が生成される過程の全てのノードのメッセージ又は当該メッセージのハッシュ値、及び当該全てのノードの検証鍵を収集する収集部と、
前記収集部により収集されたメッセージに対して、それぞれ一方向性ハッシュ関数演算を行って、各メッセージの前記第２のＧＤＨグループに属するハッシュ値を生成する検証ノード一方向性ハッシュ関数演算部と、
前記全てのノードの検証鍵、及び前記全てのノードのメッセージのハッシュ値に基づいて、前記公開された署名情報の正当性を検証する検証部と、を備える検証システム。
【請求項６】
前記検証部は、同一ノードの検証鍵及びハッシュ値によるペアリング演算の結果と、あるノードの検証鍵及び当該ノードの直前のノードのハッシュ値によるペアリング演算の結果とを全て乗じた値を、前記第１の値及び前記公開された署名情報によるペアリング演算の結果と比較し、双方が一致する場合、前記公開された署名情報が正当であると判定し、双方が一致しない場合、前記公開された署名情報が正当でないと判定する請求項５に記載の検証システム。
【請求項７】
あるノードから別のノードへの順序付きのアグリゲート署名を行うアグリゲート署名方法であって、
各ノードには、所定の自然数からなる署名鍵と、第１のＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する第１の値に対して、当該署名鍵により演算を行って生成される当該第１のＧＤＨグループに属する検証鍵とがそれぞれ割り当てられており、当該各ノードが、
第１のＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する第１の値に対して、自身の署名鍵により演算を行って、当該第１のＧＤＨグループに属する自身の検証鍵を生成する検証鍵生成工程と、
直前のノードが存在する場合、当該直前のノードの署名対象であるメッセージ又は当該メッセージのハッシュ値、及び当該直前のノードの署名情報を受信する受信工程と、
自身のメッセージと、前記直前のノードが存在する場合、当該直前のノードのメッセージとに対して、それぞれ一方向性ハッシュ関数演算を行って、各メッセージの第２のＧＤＨグループに属するハッシュ値を生成する署名ノード一方向性ハッシュ関数演算工程と、
自身のメッセージのハッシュ値に対して自身の署名鍵により演算を行った結果と、前記直前のノードが存在する場合、当該直前のノードのメッセージのハッシュ値に対して自身のノードの署名鍵により演算を行った結果、及び前記直前のノードの署名情報とを総和して、自身の署名情報を生成する署名情報生成工程と、
直後のノードが存在する場合、自身のメッセージ又は当該メッセージのハッシュ値、及び自身の署名情報を、当該直後のノードへ送信する送信工程と、を実行するアグリゲート署名方法。
【請求項８】
あるノードから別のノードへの順序付きのアグリゲート署名を行うアグリゲート署名方法をコンピュータに実行させるためのアグリゲート署名プログラムであって、
各ノードには、所定の自然数からなる署名鍵と、第１のＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する第１の値に対して、当該署名鍵により演算を行って生成される当該第１のＧＤＨグループに属する検証鍵とがそれぞれ割り当てられており、当該各ノードに、
第１のＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループに属する第１の値に対して、自身の署名鍵により演算を行って、当該第１のＧＤＨグループに属する自身の検証鍵を生成する検証鍵生成工程と、
直前のノードが存在する場合、当該直前のノードの署名対象であるメッセージ又は当該メッセージのハッシュ値、及び当該直前のノードの署名情報を受信する受信工程と、
自身のメッセージと、前記直前のノードが存在する場合、当該直前のノードのメッセージとに対して、それぞれ一方向性ハッシュ関数演算を行って、各メッセージの第２のＧＤＨグループに属するハッシュ値を生成する署名ノード一方向性ハッシュ関数演算工程と、
自身のメッセージのハッシュ値に対して自身の署名鍵により演算を行った結果と、前記直前のノードが存在する場合、当該直前のノードのメッセージのハッシュ値に対して自身のノードの署名鍵により演算を行った結果、及び前記直前のノードの署名情報とを総和して、自身の署名情報を生成する署名情報生成工程と、
直後のノードが存在する場合、自身のメッセージ又は当該メッセージのハッシュ値、及び自身の署名情報を、当該直後のノードへ送信する送信工程と、を実行させるためのアグリゲート署名プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２０１２−１７５６３４（Ｐ２０１２−１７５６３４Ａ）
【公開日】平成２４年９月１０日（２０１２．９．１０）
【国際特許分類】
【出願番号】特願２０１１−３８３８７（Ｐ２０１１−３８３８７）
【出願日】平成２３年２月２４日（２０１１．２．２４）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
【公開日】平成２４年９月１０日（２０１２．９．１０）
【国際特許分類】
【出願日】平成２３年２月２４日（２０１１．２．２４）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
[ Back to top ]