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