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