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