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