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