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