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