(57)【要約】【課題】回覧物がどの中間ノード及びリーフノードに流通し、誰が回覧したのかを知ることができる回覧システム及び回覧方法及び回覧プログラムを提供すること。【解決手段】リーフノード３１から送信されてくる固有検証鍵と、リーフノード署名情報とリーフノード確認検証鍵とを受信し、中間ノード２１から送信されてくる固有検証鍵と、中間ノード経由検証鍵とを受信するルートノード受信部１５と、中間ノード経由検証鍵に対して、中間ノード２１の固有検証鍵と、ルートノード１１の固有検証鍵とを用いて正当性を検証し、リーフノード確認検証鍵に対して、リーフノード３１の固有検証鍵と、中間ノード経由検証鍵とを用いて正当性を検証する第１の検証部１６と、正当性が検証されたリーフノード確認検証鍵と中間ノード経由検証鍵に基づいて、リーフノード署名情報の正当性を検証する第２の検証部１７を備える。【選択図】図１
2011029782.tif 000002
【特許請求の範囲】
【請求項１】
電子的な回覧物を発信するルートノードから前記ルートノードよりも下位の階層に属する下位ノードへ段階的に前記回覧物を回覧するツリー構造化された回覧システムであって、前記ルートノードと前記下位ノードには予め重複しない固有署名鍵と固有検証鍵がそれぞれ割り当てられており、
前記ルートノードは、
前記回覧物に一方向性ハッシュ関数演算を行う一方向性ハッシュ関数演算部と、
前記一方向性ハッシュ関数演算が行われた回覧物にルートノードの固有署名鍵で暗号化を行ってルートノード署名情報を生成するルートノード署名情報生成部と、
前記回覧物と、前記ルートノード署名情報と、ルートノードの固有検証鍵をツリー構造における一階層下の前記下位ノードに送信するルートノード送信部と、
ツリー構造における最下層の下位ノードであるリーフノードから送信されてくる当該リーフノードの固有検証鍵と、当該リーフノードで生成されるリーフノード署名情報と、リーフノード確認検証鍵とを受信し、前記ルートノードと前記リーフノードの間に他の下位ノードである中間ノードが存在する場合には、当該中間ノードから送信されてくる当該中間ノードの固有検証鍵と、当該中間ノードで生成される中間ノード経由検証鍵とを受信するルートノード受信部と、
前記中間ノード経由検証鍵に対して、当該中間ノード経由検証鍵を送信してきた中間ノードの固有検証鍵と、一階層上の中間ノードの前記中間ノード経由検証鍵又は前記ルートノードの固有検証鍵とを用いて正当性を検証し、前記リーフノード確認検証鍵に対して、前記リーフノードの固有検証鍵と、前記正当性が検証された一階層上の前記中間ノード経由検証鍵又はルートノードの固有検証鍵とを用いて正当性を検証する第１の検証部と、
正当性が検証された前記リーフノード確認検証鍵に基づいて、前記リーフノード署名情報の正当性を検証する第２の検証部を備えることを特徴とする回覧システム。
【請求項２】
前記中間ノードは、
ツリー構造における一階層上のノードから送信されてくる前記回覧物と第１の送信署名情報と第１の送信検証鍵を受信し、ツリー構造における一階層下のノードから送信されてくる第２の送信署名情報と第２の送信検証鍵を受信する中間ノード受信部と、
前記第１の送信署名情報に中間ノードの固有署名鍵で暗号化を行って中間ノード署名情報を生成する中間ノード署名情報生成部と、
前記第１の送信検証鍵に前記中間ノードの固有署名鍵で暗号化を行って前記中間ノード署名情報の検証鍵である前記中間ノード経由検証鍵を生成する中間ノード経由検証鍵生成部と、
前記ツリー構造における一階層上のノードに対して、前記第２の送信署名情報と、前記第２の送信検証鍵と、前記中間ノード経由検証鍵と、中間ノードの固有検証鍵を送信し、前記ツリー構造における一階層下のノードに対して、前記回覧物とともに前記中間ノード経由検証鍵と前記中間ノード署名情報を送信する中間ノード送信部とを備えることを特徴とする請求項１記載の回覧システム。
【請求項３】
前記リーフノードは、
ツリー構造における一階層上のノードから送信されてくる前記回覧物と第３の送信署名情報と第３の送信検証鍵を受信するリーフノード受信部と、
前記第３の送信署名情報にリーフノードの固有署名鍵で暗号化を行って前記リーフノード署名情報を生成するリーフノード署名情報生成部と、
前記第３の送信検証鍵に前記リーフノードの固有署名鍵で暗号化を行って前記リーフノード署名情報の検証鍵である前記リーフノード確認検証鍵を生成するリーフノード確認検証鍵生成部と、
前記ツリー構造における一階層上のノードに対して、前記リーフノード署名情報と、前記リーフノード確認検証鍵と、前記リーフノードの固有検証鍵を送信するリーフノード送信部とを備えることを特徴とする請求項１又は２記載の回覧システム。
【請求項４】
ツリー構造化された回覧システムにおいて、電子的な回覧物を発信するルートノードから前記ルートノードよりも下位の階層に属する下位ノードへ段階的に前記回覧物を回覧する回覧方法であって、前記ルートノードと前記下位ノードには予め重複しない固有署名鍵と固有検証鍵が割り当てられており、
前記ルートノードは、
前記回覧物に一方向性ハッシュ関数演算を行う一方向性ハッシュ関数演算工程と、
前記一方向性ハッシュ関数演算が行われた回覧物にルートノードの固有署名鍵で暗号化を行ってルートノード署名情報を生成するルートノード署名情報生成工程と、
前記回覧物と、前記ルートノード署名情報と、ルートノードの固有検証鍵をツリー構造における一階層下の前記下位ノードに送信するルートノード送信工程と、
ツリー構造における最下層の下位ノードであるリーフノードから送信されてくる当該リーフノードの固有検証鍵と、当該リーフノードで生成されるリーフノード署名情報とリーフノード確認検証鍵とを受信し、前記ルートノードと前記リーフノードの間に他の下位ノードである中間ノードが存在する場合には、当該中間ノードから送信されてくる当該中間ノードの固有検証鍵と、当該中間ノードで生成される中間ノード経由検証鍵とを受信するルートノード受信工程と、
前記中間ノード経由検証鍵に対して、当該中間ノード経由検証鍵を送信してきた中間ノードの固有検証鍵と、一階層上の中間ノードの前記中間ノード経由検証鍵又は前記ルートノードの固有検証鍵とを用いて正当性を検証し、前記リーフノード確認検証鍵に対して、前記リーフノードの固有検証鍵と、前記正当性が検証された一階層上の前記中間ノード経由検証鍵又はルートノードの固有検証鍵とを用いて正当性を検証する第１の検証工程と、
正当性が検証された前記リーフノード確認検証鍵に基づいて、前記リーフノード署名情報の正当性を検証する第２の検証工程とを備えることを特徴とする回覧方法。
【請求項５】
ツリー構造化された回覧システムにおいて、電子的な回覧物を発信するルートノードから前記ルートノードよりも下位の階層に属する下位ノードへ段階的に前記回覧物を回覧する方法をコンピュータによって実現するための回覧プログラムであって、前記ルートノードと前記下位ノードには予め重複しない固有署名鍵と固有検証鍵が割り当てられており、
前記回覧物に一方向性ハッシュ関数演算を行う一方向性ハッシュ関数演算工程と、
前記一方向性ハッシュ関数演算が行われた回覧物にルートノードの固有署名鍵で暗号化を行ってルートノード署名情報を生成するルートノード署名情報生成工程と、
前記回覧物と、前記ルートノード署名情報と、ルートノードの固有検証鍵をツリー構造における一階層下の前記下位ノードに送信するルートノード送信工程と、
ツリー構造における最下層の下位ノードであるリーフノードから送信されてくる当該リーフノードの固有検証鍵と、当該リーフノードで生成されるリーフノード署名情報とリーフノード確認検証鍵とを受信し、前記ルートノードと前記リーフノードの間に他の下位ノードである中間ノードが存在する場合には、当該中間ノードから送信されてくる当該中間ノードの固有検証鍵と、当該中間ノードで生成される中間ノード経由検証鍵とを受信するルートノード受信工程と、
前記中間ノード経由検証鍵に対して、当該中間ノード経由検証鍵を送信してきた中間ノードの固有検証鍵と、一階層上の中間ノードの前記中間ノード経由検証鍵又は前記ルートノードの固有検証鍵とを用いて正当性を検証し、前記リーフノード確認検証鍵に対して、前記リーフノードの固有検証鍵と、前記正当性が検証された一階層上の前記中間ノード経由検証鍵又はルートノードの固有検証鍵とを用いて正当性を検証する第１の検証工程と、
正当性が検証された前記リーフノード確認検証鍵に基づいて、前記リーフノード署名情報の正当性を検証する第２の検証工程とが前記ルートノードによって実行されるようにコンピュータによって実現するための回覧プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子署名を利用した回覧物の回覧システム及び回覧方法及び回覧プログラムに関する。
【背景技術】
【０００２】
現在、さまざまな電子情報がネットワークやメディアを介して送信されている。会社やコミュニティーのような組織においても、報告書やレポート、稟議書、連絡簿等さまざまな情報が電子化され、社員又はメンバー間でネットワークを経由して回覧されている。
【０００３】
その情報の発信源あるいは閲覧済みであることを保証する仕組みとして電子署名がある。この電子署名を利用することにより、特定の人しか知りえない署名鍵と電子情報を入力値として署名の演算を行い、検証者が検証鍵と言われる公開された情報と署名されたデータを入力値として検証演算を行うことで、その特定の人がそのデータの発信源であることを確認することが可能となる。ここで、検証鍵から署名鍵を導出することは、計算量的に不可能であることから、他の人がその特定者に成りすまして署名を行うことができないため、その署名の正当性が保証される。
【０００４】
また、組織における電子情報の回覧においては、複数の人が介在して署名を行うケースが想定され、例えば、電子データの回覧や会社における承認システムがそれに該当する。複数人の署名を行う方式としては、それぞれの署名者を検証できる多重署名（例えば、非特許文献１を参照。）や、特定のグループに所属している人の誰かが署名したことを保証できるグループ署名（例えば、特許文献１を参照。）が提案されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００１−１６６６８７号公報
【特許文献２】特開平０９−２７０７８７号公報
【特許文献３】特開２００２−０４０９３５号公報
【非特許文献】
【０００６】
【非特許文献１】新保  淳、「多重署名に適したＥｌＧａｍａｌ署名の一変形方式」、暗号と情報セキュリティシンポジウム（ＣＳＳ）、ＳＣＩＳ９４−２Ｃ、電子情報通信学会、１９９４
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、これらの多重署名やグループ署名では署名者がすべて等価な関係で表現され、一例として示した回覧システムにおいて回覧物がどのように流通してきたか、あるいは回覧状況をグループ毎で確認することをこの署名方式だけで表現することができない。
【０００８】
これに対し、順序や上下関係で証明される方式としては順序付き多重署名方式（例えば、特許文献２、３を参照。）があげられる。これにより署名者の順番が保証され、個人の上下関係が表現できる。しかしながら、これらは各署名者の前と後のユーザが一人ずつのみの場合のみで行える方式であり、例えば組織毎で区別しようとしても、既存の署名方式ではその組織構造を表現することができない。
【０００９】
本発明は、上記課題を解決するため、木構造を表現できる署名方式を応用し、組織構造に合わせて回覧状況を確認できる回覧システム及び回覧方法及び回覧プログラムを提供するものである。
【課題を解決するための手段】
【００１０】
本発明では、以下のような解決手段を提供する。
【００１１】
（１）本発明に係る回覧システムは、上記課題を解決するために、電子的な回覧物を発信するルートノードから前記ルートノードよりも下位の階層に属する下位ノードへ段階的に前記回覧物を回覧するツリー構造化された回覧システムであって、前記ルートノードと前記下位ノードには予め重複しない固有署名鍵と固有検証鍵がそれぞれ割り当てられており、前記ルートノードは、前記回覧物にハッシュ演算を行うハッシュ演算部と、前記ハッシュ演算が行われた回覧物にルートノードの固有署名鍵で暗号化を行ってルートノード署名情報を生成するルートノード署名情報生成部と、前記回覧物と、前記ルートノード署名情報と、ルートノードの固有検証鍵をツリー構造における一階層下の前記下位ノードに送信するルートノード送信部と、ツリー構造における最下層の下位ノードであるリーフノードから送信されてくる当該リーフノードの固有検証鍵と、当該リーフノードで生成されるリーフノード署名情報とリーフノード確認検証鍵とを受信し、前記ルートノードと前記リーフノードの間に他の下位ノードである中間ノードが存在する場合には、当該中間ノードから送信されてくる当該中間ノードの固有検証鍵と、当該中間ノードで生成される中間ノード経由検証鍵とを受信するルートノード受信部と、前記中間ノード経由検証鍵に対して、当該中間ノード経由検証鍵を送信してきた中間ノードの固有検証鍵と、一階層上の中間ノードの前記中間ノード経由検証鍵又は前記ルートノードの固有検証鍵とを用いて正当性を検証し、前記リーフノード確認検証鍵に対して、前記リーフノードの固有検証鍵と、前記正当性が検証された一階層上の前記中間ノード経由検証鍵又はルートノードの固有検証鍵とを用いて正当性を検証する第１の検証部と、正当性が検証された前記リーフノード確認検証鍵に基づいて、前記リーフノード署名情報の正当性を検証する第２の検証部を備えることを特徴とする。
【００１２】
このような構成によれば、回覧システムは、ツリー構造における最下層の下位ノードであるリーフノードから当該リーフノードの固有検証鍵と、当該リーフノードで生成されるリーフノード署名情報とリーフノード確認検証鍵がルートノードに送信される。また、回覧システムでは、ルートノードとリーフノードの間に他の下位ノードである中間ノードが存在する場合には、当該中間ノードから送信されてくる当該中間ノードの固有検証鍵と、当該中間ノードで生成される中間ノード経由検証鍵もルートノードに受信される。また、回覧システムでは、第１の検証部により、中間ノード経由検証鍵に対して、当該中間ノード経由検証鍵を送信してきた中間ノードの固有検証鍵と、ルートノードの固有検証鍵とを用いて正当性を検証し、つぎに、リーフノード確認検証鍵に対して、リーフノードの固有検証鍵と、正当性が検証された中間ノード経由検証鍵とを用いて正当性を検証する。また、回覧システムでは、第２の検証部により、正当性が検証されたリーフノード確認検証鍵に基づいて、リーフノード署名情報の正当性が検証される。
【００１３】
したがって、回覧システムでは、回覧物がどの中間ノード及びリーフノードに流通し、誰が回覧したのかを知ることができる。
【００１４】
（２）また、上記回覧システムでは、前記中間ノードは、ツリー構造における一階層上のノードから送信されてくる前記回覧物と第１の送信署名情報と第１の送信検証鍵を受信し、ツリー構造における一階層下のノードから送信されてくる第２の送信署名情報と第２の送信検証鍵を受信する中間ノード受信部と、前記第１の送信署名情報に中間ノードの固有署名鍵で暗号化を行って中間ノード署名情報を生成する中間ノード署名情報生成部と、前記第１の送信検証鍵に前記中間ノードの固有署名鍵で暗号化を行って前記中間ノード署名情報の検証鍵である前記中間ノード経由検証鍵を生成する中間ノード経由検証鍵生成部と、前記ツリー構造における一階層上のノードに対して、前記第２の送信署名情報と、前記第２の送信検証鍵と、前記中間ノード経由検証鍵と、中間ノードの固有検証鍵を送信し、前記ツリー構造における一階層下のノードに対して、前記回覧物とともに前記中間ノード経由検証鍵と前記中間ノード署名情報を送信する中間ノード送信部とを備えることが好ましい。
【００１５】
このような構成によれば、回覧システムでは、ルートノードとリーフノードの間に他の下位ノードである中間ノードが存在する場合には、中間ノードにおいて、受信した第１の送信署名情報（例えば、ルートノード署名情報）に中間ノードの固有署名鍵で暗号化を行って中間ノード署名情報を生成し、第１の送信検証鍵（例えば、ルートノードの固有検証鍵）に中間ノードの固有署名鍵で暗号化を行って中間ノード署名情報の検証鍵である中間ノード経由検証鍵を生成する。そして、中間ノードは、ツリー構造における一階層上のノードに対して、第２の送信署名情報（例えば、リーフノード署名情報）と、第２の送信検証鍵（例えば、リーフノードの固有検証鍵及びリーフノード確認検証鍵）と、中間ノード経由検証鍵と、中間ノードの固有検証鍵を送信し、ツリー構造における一階層下のノードに対して、回覧物とともに中間ノード経由検証鍵と中間ノード署名情報を送信する。
【００１６】
したがって、回覧システムでは、ルートノードは、中間ノードが生成した中間ノード経由検証鍵と中間ノードの固有検証鍵を受信するので、第１の検証部により、中間ノード経由検証鍵に対して、当該中間ノード経由検証鍵を送信してきた中間ノードの固有検証鍵と、ルートノードの固有検証鍵とを用いて正当性を検証し、つぎに、リーフノード確認検証鍵に対して、リーフノードの固有検証鍵と、正当性が検証された中間ノード経由検証鍵を用いて正当性を検証することができる。
【００１７】
（３）また、上記回覧システムでは、リーフノードは、ツリー構造における一階層上のノードから送信されてくる前記回覧物と第３の送信署名情報と第３の送信検証鍵を受信するリーフノード受信部と、前記第３の送信署名情報にリーフノードの固有署名鍵で暗号化を行って前記リーフノード署名情報を生成するリーフノード署名情報生成部と、前記第３の送信検証鍵に前記リーフノードの固有署名鍵で暗号化を行って前記リーフノード署名情報の検証鍵である前記リーフノード確認検証鍵を生成するリーフノード確認検証鍵生成部と、前記ツリー構造における一階層上のノードに対して、前記リーフノード署名情報と、前記リーフノード確認検証鍵と、前記リーフノードの固有検証鍵を送信するリーフノード送信部とを備えることが好ましい。
【００１８】
このような構成によれば、回覧システムでは、リーフノードにおいて、第３の送信署名情報（例えば、中間ノード署名情報）にリーフノードの固有署名鍵で暗号化を行ってリーフノード署名情報を生成し、第３の送信検証鍵（例えば、中間ノード経由検証鍵）にリーフノードの固有署名鍵で暗号化を行ってリーフノード署名情報の検証鍵であるリーフノード確認検証鍵を生成する。そして、リーフノードは、ツリー構造における一階層上のノード（中間ノード又はルートノード）に対して、リーフノード署名情報と、リーフノード確認検証鍵と、リーフノードの固有検証鍵を送信する。
【００１９】
したがって、回覧システムでは、ルートノードは、リーフノードの固有検証鍵と、リーフノード署名情報と、リーフノード確認検証鍵と、中間ノードの固有検証鍵と、中間ノード経由検証鍵とを受信するので、第１の検証部により、中間ノード経由検証鍵に対して、当該中間ノード経由検証鍵を送信してきた中間ノードの固有検証鍵と、ルートノードの固有検証鍵とを用いて正当性を検証し、つぎに、リーフノード確認検証鍵に対して、リーフノードの固有検証鍵と、正当性が検証された中間ノード経由検証鍵とを用いて正当性を検証し、つぎに、第２の検証部により、正当性が検証されたリーフノード確認検証鍵と中間ノード経由検証鍵に基づいて、前記リーフノード署名情報の正当性を検証するので、回覧物がどの中間ノード及びリーフノードに流通し、誰が回覧したのかを知ることができる。
【００２０】
（４）本発明に係る回覧方法は、上記課題を解決するために、ツリー構造化された回覧システムにおいて、電子的な回覧物を発信するルートノードから前記ルートノードよりも下位の階層に属する下位ノードへ段階的に前記回覧物を回覧する回覧方法であって、前記ルートノードと前記下位ノードには予め重複しない固有署名鍵と固有検証鍵が割り当てられており、前記ルートノードは、前記回覧物にハッシュ演算を行うハッシュ演算工程と、前記ハッシュ演算が行われた回覧物にルートノードの固有署名鍵で暗号化を行ってルートノード署名情報を生成するルートノード署名情報生成工程と、前記回覧物と、前記ルートノード署名情報と、ルートノードの固有検証鍵をツリー構造における一階層下の前記下位ノードに送信するルートノード送信工程と、ツリー構造における最下層の下位ノードであるリーフノードから送信されてくる当該リーフノードの固有検証鍵と、当該リーフノードで生成されるリーフノード署名情報とリーフノード確認検証鍵とを受信し、前記ルートノードと前記リーフノードの間に他の下位ノードである中間ノードが存在する場合には、当該中間ノードから送信されてくる当該中間ノードの固有検証鍵と、当該中間ノードで生成される中間ノード経由検証鍵とを受信するルートノード受信工程と、前記中間ノード経由検証鍵に対して、当該中間ノード経由検証鍵を送信してきた中間ノードの固有検証鍵と、一階層上の中間ノードの前記中間ノード経由検証鍵又は前記ルートノードの固有検証鍵とを用いて正当性を検証し、前記リーフノード確認検証鍵に対して、前記リーフノードの固有検証鍵と、前記正当性が検証された一階層上の前記中間ノード経由検証鍵又はルートノードの固有検証鍵とを用いて正当性を検証する第１の検証工程と、正当性が検証された前記リーフノード確認検証鍵に基づいて、前記リーフノード署名情報の正当性を検証する第２の検証工程とを備えることを特徴とする。
【００２１】
このような構成によれば、回覧方法は、ツリー構造における最下層の下位ノードであるリーフノードから当該リーフノードの固有検証鍵と、当該リーフノードで生成されるリーフノード署名情報とリーフノード確認検証鍵がルートノードに送信される。また、回覧方法では、ルートノードとリーフノードの間に他の下位ノードである中間ノードが存在する場合には、当該中間ノードから送信されてくる当該中間ノードの固有検証鍵と、当該中間ノードで生成される中間ノード経由検証鍵もルートノードに受信される。また、回覧方法では、第１の検証工程により、中間ノード経由検証鍵に対して、当該中間ノード経由検証鍵を送信してきた中間ノードの固有検証鍵と、ルートノードの固有検証鍵とを用いて正当性を検証し、つぎに、リーフノード確認検証鍵に対して、リーフノードの固有検証鍵と、正当性が検証された中間ノード経由検証鍵とを用いて正当性を検証する。また、回覧システムでは、第２の検証工程により、正当性が検証されたリーフノード確認検証鍵に基づいて、リーフノード署名情報の正当性が検証される。
【００２２】
したがって、回覧方法では、回覧物がどの中間ノード及びリーフノードに流通し、誰が回覧したのかを知ることができる。
【００２３】
（５）本発明に係る回覧プログラムは、上記課題を解決するために、ツリー構造化された回覧システムにおいて、電子的な回覧物を発信するルートノードから前記ルートノードよりも下位の階層に属する下位ノードへ段階的に前記回覧物を回覧する方法をコンピュータによって実現するための回覧プログラムであって、前記ルートノードと前記下位ノードには予め重複しない固有署名鍵と固有検証鍵が割り当てられており、前記回覧物にハッシュ演算を行うハッシュ演算工程と、前記ハッシュ演算が行われた回覧物にルートノードの固有署名鍵で暗号化を行ってルートノード署名情報を生成するルートノード署名情報生成工程と、前記回覧物と、前記ルートノード署名情報と、ルートノードの固有検証鍵をツリー構造における一階層下の前記下位ノードに送信するルートノード送信工程と、ツリー構造における最下層の下位ノードであるリーフノードから送信されてくる当該リーフノードの固有検証鍵と、当該リーフノードで生成されるリーフノード署名情報とリーフノード確認検証鍵とを受信し、前記ルートノードと前記リーフノードの間に他の下位ノードである中間ノードが存在する場合には、当該中間ノードから送信されてくる当該中間ノードの固有検証鍵と、当該中間ノードで生成される中間ノード経由検証鍵とを受信するルートノード受信工程と、前記中間ノード経由検証鍵に対して、当該中間ノード経由検証鍵を送信してきた中間ノードの固有検証鍵と、一階層上の中間ノードの前記中間ノード経由検証鍵又は前記ルートノードの固有検証鍵とを用いて正当性を検証し、前記リーフノード確認検証鍵に対して、前記リーフノードの固有検証鍵と、前記正当性が検証された一階層上の前記中間ノード経由検証鍵又はルートノードの固有検証鍵とを用いて正当性を検証する第１の検証工程と、正当性が検証された前記リーフノード確認検証鍵に基づいて、前記リーフノード署名情報の正当性を検証する第２の検証工程とが前記ルートノードによって実行されるようにコンピュータによって実現するためのものである。
【００２４】
このような構成によれば、回覧プログラムは、ツリー構造における最下層の下位ノードであるリーフノードから当該リーフノードの固有検証鍵と、当該リーフノードで生成されるリーフノード署名情報とリーフノード確認検証鍵がルートノードに送信される。また、回覧プログラムでは、ルートノードとリーフノードの間に他の下位ノードである中間ノードが存在する場合には、当該中間ノードから送信されてくる当該中間ノードの固有検証鍵と、当該中間ノードで生成される中間ノード経由検証鍵もルートノードに受信される。また、回覧プログラムでは、第１の検証工程により、中間ノード経由検証鍵に対して、当該中間ノード経由検証鍵を送信してきた中間ノードの固有検証鍵と、ルートノードの固有検証鍵とを用いて正当性を検証し、つぎに、リーフノード確認検証鍵に対して、リーフノードの固有検証鍵と、正当性が検証された中間ノード経由検証鍵とを用いて正当性を検証する。また、回覧システムでは、第２の検証工程により、正当性が検証されたリーフノード確認検証鍵に基づいて、リーフノード署名情報の正当性が検証される。
【００２５】
したがって、回覧プログラムでは、回覧物がどの中間ノード及びリーフノードに流通し、誰が回覧したのかを知ることができる。
【発明の効果】
【００２６】
本発明によれば、回覧物がどの中間ノード及びリーフノードに流通し、誰が回覧したのかを知ることができる。
【図面の簡単な説明】
【００２７】
【図１】本発明に係る回覧システムの構成を模式的に示す図である。
【図２】本発明に係る回覧システムにより回覧物が回覧される手順についての説明に供するフローチャートである。
【図３】回覧物（Ｍ）の流通と署名の作成についての説明に供する図である。
【図４】２分木４階層によるツリー構造を模式的に示す図である。
【発明を実施するための形態】
【００２８】
以下、本発明の実施形態の一例について図１を参照しながら説明する。本発明の実施形態に係る回覧システム１は、電子的な回覧物を発信するルートノード１１からルートノード１１よりも下位の階層に属する下位ノード（中間ノード２１、リーフノード３１）へ段階的に回覧物を回覧するツリー構造化されたシステムである。なお、ルートノード１１と下位ノード（中間ノード２１、リーフノード３１）には、認証局（ＣＡ、Ｃｅｒｔｉｆｉｃａｔｅ  Ａｕｔｈｏｒｉｔｙ）により予め重複しない固有署名鍵と固有検証鍵がそれぞれ割り当てられている。また、以下では、一つのルートノード１１から、一つの中間ノード２１を経由して一つのリーフノード３１へ回覧物（Ｍ）が回覧される場合を想定して説明する。なお、回覧物（Ｍ）とは、電子データにより構成される情報を表す概念である。
【００２９】
ルートノード１１は、図１に示すように、一方向性ハッシュ関数演算部１２と、ルートノード署名情報生成部１３と、ルートノード送信部１４と、ルートノード受信部１５と、第１の検証部１６と、第２の検証部１７とを備える。
【００３０】
一方向性ハッシュ関数演算部１２は、電子的な回覧物（Ｍ）に一方向性ハッシュ関数演算を行う。一方向性ハッシュ関数演算が行われた回覧物（Ｍ）は、以降、単にハッシュ（ｈ）という。
【００３１】
ルートノード署名情報生成部１３は、ハッシュ（ｈ）にルートノード１１の固有署名鍵（ｘｒ）で暗号化を行ってルートノード署名情報（ｘｒｈ（＝ａｘｒｇ））を生成する。なお、詳細は後述するが、ｇは、ＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループと呼ばれるある特定の楕円曲線上の点の集合Ｇの要素である。
ここで、一方向性ハッシュ関数演算部１２による演算においては、一方向性ハッシュ関数Ｈを、通常使用される任意のビット長のサイズの数値データを固定のビット長のサイズの数値データに写像変換される方式とは異なり、
Ｈ：｛０，１｝＊→Ｇ
のように任意のビット長のサイズの数値データを楕円曲線上の点として表現されるＧＤＨグループＧの要素に写像変換する方式であると定義する（例えば、ｓをＳＨＡ−１（ｐｌａｉｎｔｅｘｔ）のように通常使用される一方向性ハッシュ関数としたとき、ｓｇとして表される式は、ここで定義する一方向性ハッシュ関数Ｈの条件を満たす）。また、集合Ｇは、ＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループを示し、ｇは、集合Ｇの要素となる点を示している。なお、一方向性ハッシュ関数Ｈについての詳細は後述する。
【００３２】
ルートノード送信部１４は、回覧物（Ｍ）と、ルートノード署名情報（ｘｒｈ）と、ルートノード１１の固有検証鍵（ｘｒｇ）をツリー構造における一階層下の下位ノード（例えば、中間ノード２１）に送信する。
【００３３】
また、ルートノード受信部１５は、ツリー構造における最下層の下位ノードであるリーフノード３１から送信されてくる当該リーフノード３１の固有検証鍵（ｘ１１１ｇ）と、当該リーフノード３１で生成されるリーフノード署名情報（σｃｉｒｃ−１１１（＝ｘ１１１（ｘｒｘ１ｈ）））とリーフノード確認検証鍵（ｖｃｉｒｃ−１１１（＝ｘ１１１（ｘｒｘ１ｇ）））とを受信し、ルートノード１１とリーフノード３１の間に他の下位ノードである中間ノード２１が存在する場合には、当該中間ノード２１から送信されてくる当該中間ノード２１の固有検証鍵（ｘ１ｇ）と、当該中間ノード２１で生成される中間ノード経由検証鍵（ｖｐａｓｓ−１（＝ｘ１（ｘｒｇ）））とを受信する。
【００３４】
第１の検証部１６は、中間ノード経由検証鍵（ｖｐａｓｓ−１）に対して、当該中間ノード経由検証鍵（ｖｐａｓｓ−１）を送信してきた中間ノード２１の固有検証鍵（ｘ１ｇ）と、ルートノード１１の固有検証鍵（ｘｒｇ）とを用いて正当性を検証し、リーフノード確認検証鍵（ｖｃｉｒｃ−１１１）に対して、リーフノード３１の固有検証鍵（ｘ１１１ｇ）と、正当性が検証された中間ノード経由検証鍵（ｖｐａｓｓ−１）とを用いて正当性を検証する。
【００３５】
第２の検証部１７は、正当性が検証されたリーフノード確認検証鍵（ｖｃｉｒｃ−１１１）に基づいて、リーフノード署名情報（σｃｉｒｃ−１１１（＝ｘ１１１（ｘｒｘ１ｘ１１ｇ）））の正当性を検証する。
【００３６】
このような構成によれば、回覧システム１では、ツリー構造における最下層の下位ノードであるリーフノード３１から送信されてくる当該リーフノード３１の固有検証鍵（ｘ１１１ｇ）と、当該リーフノード３１で生成されるリーフノード署名情報（σｃｉｒｃ−１１１）とリーフノード確認検証鍵（ｖｃｉｒｃ−１１１）がルートノード１１に受信される。
【００３７】
また、回覧システム１では、ルートノード１１とリーフノード３１の間に他の下位ノードである中間ノード２１が存在する場合には、当該中間ノード２１から送信されてくる当該中間ノード２１の固有検証鍵（ｘ１ｇ）と、当該中間ノード２１で生成される中間ノード経由検証鍵（ｖｐａｓｓ−１）もルートノード１１に受信される。
【００３８】
また、回覧システム１では、第１の検証部１６により、中間ノード経由検証鍵（ｖｐａｓｓ−１）に対して、当該中間ノード経由検証鍵（ｖｐａｓｓ−１）を送信してきた中間ノード２１の固有検証鍵（ｘ１ｇ）と、ルートノード１１の固有検証鍵（ｘｒｇ）とを用いて正当性を検証し、つぎに、リーフノード確認検証鍵（ｖｃｉｒｃ−１１１）に対して、リーフノード３１の固有検証鍵（ｘ１１１ｇ）と、正当性が検証された中間ノード経由検証鍵（ｖｐａｓｓ−１）とを用いて正当性を検証される。また、回覧システム１では、第２の検証部１７により、正当性が検証されたリーフノード確認検証鍵（ｖｃｉｒｃ−１１１）に基づいて、リーフノード署名情報（σｃｉｒｃ−１１１）の正当性が検証される。
【００３９】
したがって、回覧システム１では、回覧物（Ｍ）がどの中間ノード２１及びリーフノード３１に流通し、誰が回覧したのかを知ることができる。
【００４０】
また、中間ノード２１は、図１に示すように、中間ノード受信部２２と、中間ノード署名情報生成部２３と、中間ノード経由検証鍵生成部２４と、中間ノード送信部２５とを備える。
【００４１】
中間ノード受信部２２は、ツリー構造における一階層上のノードから送信されてくる回覧物（Ｍ）と第１の送信署名情報と第１の送信検証鍵を受信し、ツリー構造における一階層下のノードから送信されてくる第２の送信署名情報（例えば、σｃｉｒｃ−１１１）と第２の送信検証鍵を受信する。なお、第２の送信検証鍵には、一階層下のノード自身の固有検証鍵（例えば、ｘ１１１ｇ）と、リーフノード確認検証鍵（例えば、ｖｃｉｒｃ−１１１）が含まれている。
【００４２】
中間ノード署名情報生成部２３は、第１の送信署名情報に中間ノード２１の固有署名鍵（ｘ１）で暗号化を行って中間ノード署名情報（σｐａｓｓ−１）を生成する。中間ノード経由検証鍵生成部２４は、第１の送信検証鍵に中間ノード２１の固有署名鍵（ｘ１）で暗号化を行って中間ノード署名情報（σｐａｓｓ−１）の検証鍵である中間ノード経由検証鍵（ｖｐａｓｓ−１）を生成する。
【００４３】
中間ノード送信部２５は、ツリー構造における一階層上のノードに対して、第２の送信署名情報（例えば、σｃｉｒｃ−１１１）と、第２の送信検証鍵（例えば、ｘ１１１ｇと、ｖｃｉｒｃ−１１１）と、中間ノード経由検証鍵（ｖｐａｓｓ−１）と、中間ノード２１の固有検証鍵（ｘ１ｇ）を送信し、ツリー構造における一階層下のノードに対して、回覧物（Ｍ）とともに中間ノード経由検証鍵（ｖｐａｓｓ−１）と中間ノード署名情報（σｐａｓｓ−１）を送信する。
【００４４】
このような構成によれば、回覧システム１では、ルートノード１１とリーフノード３１の間に他の下位ノードである中間ノード２１が存在する場合には、中間ノード２１において、受信した第１の送信署名情報（例えば、ルートノード署名情報（ｘｒｈ））に中間ノード２１の固有署名鍵（ｘ１）で暗号化を行って中間ノード署名情報（σｐａｓｓ−１）を生成し、第１の送信検証鍵（例えば、ルートノード１１の固有検証鍵（ｘｒｇ））に中間ノード２１の固有署名鍵（ｘ１）で暗号化を行って中間ノード署名情報（σｐａｓｓ−１）の検証鍵である中間ノード経由検証鍵（ｖｐａｓｓ−１）を生成する。
【００４５】
そして、中間ノード２１は、ツリー構造における一階層上のノード（例えば、ルートノード１１）に対して、第２の送信署名情報（例えば、リーフノード署名情報（σｃｉｒｃ−１１１））と、第２の送信検証鍵（例えば、リーフノード３１の固有検証鍵（ｘ１１１ｇ）及びリーフノード確認検証鍵（例えば、ｖｃｉｒｃ−１１１））と、中間ノード経由検証鍵（ｖｐａｓｓ−１）と、中間ノード２１の固有検証鍵（ｘ１ｇ）を送信し、ツリー構造における一階層下のノードに対して、回覧物（Ｍ）とともに中間ノード経由検証鍵（ｖｐａｓｓ−１）と中間ノード署名情報（σｐａｓｓ−１）を送信する。
【００４６】
したがって、回覧システム１では、ルートノード１１は、中間ノード２１が生成した中間ノード経由検証鍵（ｖｐａｓｓ−１）と中間ノード２１の固有検証鍵（ｘ１ｇ）を受信するので、第１の検証部１６により、中間ノード経由検証鍵（ｖｐａｓｓ−１）に対して、当該中間ノード経由検証鍵（ｖｐａｓｓ−１）を送信してきた中間ノード２１の固有検証鍵（ｘ１ｇ）と、ルートノード１１の固有検証鍵（ｘｒｇ）とを用いて正当性を検証し、つぎに、リーフノード確認検証鍵（ｖｃｉｒｃ−１１１）に対して、リーフノード３１の固有検証鍵（ｘ１１１ｇ）と、正当性が検証された中間ノード経由検証鍵（ｖｐａｓｓ−１）を用いて正当性を検証することができる。
【００４７】
また、リーフノード３１は、図１に示すように、リーフノード受信部３２と、リーフノード署名情報生成部３３と、リーフノード確認検証鍵生成部３４と、リーフノード送信部３５とを備える。
【００４８】
リーフノード受信部３２は、ツリー構造における一階層上のノードから送信されてくる回覧物（Ｍ）と第３の送信署名情報（例えば、σｐａｓｓ−１）と第３の送信検証鍵を受信する。リーフノード署名情報生成部３３は、第３の送信署名情報にリーフノード３１の固有署名鍵で暗号化を行ってリーフノード署名情報（σｃｉｒｃ−１１１）を生成する。
【００４９】
リーフノード確認検証鍵生成部３４は、第３の送信検証鍵にリーフノード３１の固有署名鍵で暗号化を行ってリーフノード署名情報（σｃｉｒｃ−１１１）の検証鍵であるリーフノード確認検証鍵（ｖｃｉｒｃ−１１１）を生成する。リーフノード送信部３５は、ツリー構造における一階層上のノードに対して、リーフノード署名情報（σｃｉｒｃ−１１１）と、リーフノード確認検証鍵（ｖｃｉｒｃ−１１１）と、リーフノード３１の固有検証鍵（ｘ１１１ｇ）を送信する。
【００５０】
このような構成によれば、回覧システム１では、リーフノード３１において、第３の送信署名情報（例えば、中間ノード署名情報（σｐａｓｓ−１））にリーフノード３１の固有署名鍵で暗号化を行ってリーフノード署名情報（σｃｉｒｃ−１１１）を生成し、第３の送信検証鍵（例えば、中間ノード経由検証鍵（ｖｐａｓｓ−１））にリーフノード３１の固有署名鍵で暗号化を行ってリーフノード署名情報（σｃｉｒｃ−１１１）の検証鍵であるリーフノード確認検証鍵（ｖｃｉｒｃ−１１１）を生成する。
【００５１】
そして、リーフノード３１は、ツリー構造における一階層上のノード（中間ノード２１又はルートノード１１）に対して、リーフノード署名情報（σｃｉｒｃ−１１１）と、リーフノード確認検証鍵（ｖｃｉｒｃ−１１１）と、リーフノード３１の固有検証鍵（ｘ１１１ｇ）を送信する。
【００５２】
したがって、回覧システム１では、ルートノード１１は、リーフノード３１の固有検証鍵（ｘ１１１ｇ）と、リーフノード署名情報（σｃｉｒｃ−１１１）と、リーフノード確認検証鍵（ｖｃｉｒｃ−１１１）と、中間ノード２１の固有検証鍵（ｘ１ｇ）と、中間ノード経由検証鍵（ｖｐａｓｓ−１）を受信するので、第１の検証部１６により、中間ノード経由検証鍵（ｖｐａｓｓ−１）に対して、当該中間ノード経由検証鍵（ｖｐａｓｓ−１）を送信してきた中間ノード２１の固有検証鍵（ｘ１ｇ）と、ルートノード１１の固有検証鍵（ｘｒｇ）を用いて正当性を検証する。つぎに、第１の検証部１６は、リーフノード確認検証鍵（ｖｃｉｒｃ−１１１）に対して、リーフノード３１の固有検証鍵（ｘ１１１ｇ）と、正当性が検証された中間ノード経由検証鍵（ｖｐａｓｓ−１）とを用いて正当性を検証する。
【００５３】
そして、第２の検証部１７は、正当性が検証されたリーフノード確認検証鍵（ｖｃｉｒｃ−１１１）に基づいて、前記リーフノード署名情報（σｃｉｒｃ−１１１）の正当性を検証する。よって、回覧システム１は、回覧物（Ｍ）がどの中間ノード２１及びリーフノード３１に流通し、誰が回覧したのかを知ることができる。
【００５４】
つぎに、回覧システム１において、回覧物（Ｍ）をルートノード１１から下位ノードへ段階的に回覧する回覧方法について図２に示すフローチャートを参照しながら説明する。また、以下では、一つのルートノード１１から、一つの中間ノード２１を経由して一つのリーフノード３１へ回覧物（Ｍ）が回覧される場合を想定して説明する。
【００５５】
一方向性ハッシュ関数演算工程ＳＴ１において、一方向性ハッシュ関数演算部１２は、電子的な回覧物（Ｍ）に一方向性ハッシュ関数演算を行う。
【００５６】
ルートノード署名情報生成工程ＳＴ２において、ルートノード署名情報生成部１３は、ハッシュ（ｈ）にルートノード１１の固有署名鍵（ｘｒ）で暗号化を行ってルートノード署名情報（ｘｒｈ（＝ａｘｒｇ））を生成する。なお、ｇは、楕円曲線上の点の集合Ｇの要素であり、詳細は後述する。
【００５７】
ルートノード送信工程ＳＴ３において、ルートノード送信部１４は、回覧物（Ｍ）と、ルートノード署名情報（ｘｒｈ）と、ルートノード１１の固有検証鍵（ｘｒｇ）をツリー構造における一階層下の下位ノード（本実施例においては、中間ノード２１）に送信する。
【００５８】
中間ノード受信工程ＳＴ４において、中間ノード受信部２２は、ツリー構造における一階層上のノード（本実施例においては、ルートノード１１）から送信されてくる回覧物（Ｍ）と、第１の送信署名情報（例えば、ルートノード署名情報（ｘｒｈ））と、第１の送信検証鍵（例えば、ルートノード１１の固有検証鍵（ｘｒｇ））を受信する。
【００５９】
中間ノード署名情報生成工程ＳＴ５において、中間ノード署名情報生成部２３は、第１の送信署名情報に中間ノード２１の固有署名鍵（ｘ１）で暗号化を行って中間ノード署名情報（σｐａｓｓ−１）を生成する。
【００６０】
中間ノード経由検証鍵生成工程ＳＴ６において、中間ノード経由検証鍵生成部２４は、第１の送信検証鍵に中間ノード２１の固有署名鍵（ｘ１）で暗号化を行って中間ノード署名情報（σｐａｓｓ−１）の検証鍵である中間ノード経由検証鍵（ｖｐａｓｓ−１）を生成する。
【００６１】
中間ノード送信工程ＳＴ７において、中間ノード送信部２５は、ツリー構造における一階層下のノード（本実施例においては、リーフノード３１）に対して、回覧物（Ｍ）とともに中間ノード経由検証鍵（ｖｐａｓｓ−１）と中間ノード署名情報（σｐａｓｓ−１）を送信する。
【００６２】
リーフノード受信工程ＳＴ８において、リーフノード受信部３２は、ツリー構造における一階層上のノード（本実施例においては、中間ノード２１）から送信されてくる回覧物（Ｍ）と、第３の送信署名情報（例えば、σｐａｓｓ−１）と、第３の送信検証鍵（例えば、中間ノード経由検証鍵（ｖｐａｓｓ−１））を受信する。
【００６３】
リーフノード署名情報生成工程ＳＴ９において、リーフノード署名情報生成部３３は、第３の送信署名情報にリーフノード３１の固有署名鍵で暗号化を行ってリーフノード署名情報（σｃｉｒｃ−１１１）を生成する。
【００６４】
リーフノード確認検証鍵生成工程ＳＴ１０において、リーフノード確認検証鍵生成部３４は、第３の送信検証鍵にリーフノード３１の固有署名鍵で暗号化を行ってリーフノード署名情報（σｃｉｒｃ−１１１）の検証鍵であるリーフノード確認検証鍵（ｖｃｉｒｃ−１１１）を生成する。
【００６５】
リーフノード送信工程ＳＴ１１において、リーフノード送信部３５は、ツリー構造における一階層上のノード（本実施例においては、中間ノード２１）に対して、リーフノード署名情報（σｃｉｒｃ−１１１）と、リーフノード確認検証鍵（ｖｃｉｒｃ−１１１）と、リーフノード３１の固有検証鍵（ｘ１１１ｇ）を送信する。
【００６６】
中間ノード受信工程ＳＴ１２において、中間ノード受信部２２は、ツリー構造における一階層下のノード（本実施例においては、リーフノード３１）から送信されてくる第２の送信署名情報（例えば、リーフノード署名情報（σｃｉｒｃ−１１１））と第２の送信検証鍵（例えば、リーフノード確認検証鍵（ｖｃｉｒｃ−１１１）とリーフノード３１の固有検証鍵（ｘ１１１ｇ））を受信する。
【００６７】
中間ノード送信工程ＳＴ１３において、中間ノード送信部２５は、ツリー構造における一階層上のノード（本実施例においては、ルートノード１１）に対して、第２の送信署名情報と、第２の送信検証鍵と、中間ノード経由検証鍵（ｖｐａｓｓ−１）と、中間ノード２１の固有検証鍵（ｘ１ｇ）を送信する。
【００６８】
ルートノード受信工程ＳＴ１４において、ルートノード受信部１５は、ツリー構造における最下層の下位ノードであるリーフノード３１の固有検証鍵（ｘ１１１ｇ）と、当該リーフノード３１で生成されるリーフノード署名情報（σｃｉｒｃ−１１１（＝ｘ１１１（ｘｒｘ１ｈ）））と、リーフノード確認検証鍵（ｖｃｉｒｃ−１１１（＝ｘ１１１（ｘｒｘ１ｇ）））とを受信する。また、本実施例では、ルートノード１１とリーフノード３１の間に他の下位ノードである中間ノード２１が存在するので、ルートノード受信部１５は、中間ノード２１の固有検証鍵（ｘ１ｇ）と、当該中間ノード２１で生成される中間ノード経由検証鍵（ｖｐａｓｓ−１（＝ｘ１（ｘｒｇ）））とを受信する。
【００６９】
第１の検証工程ＳＴ１５において、第１の検証部１６は、中間ノード経由検証鍵（ｖｐａｓｓ−１）に対して、当該中間ノード経由検証鍵（ｖｐａｓｓ−１）を送信してきた中間ノード２１の固有検証鍵（ｘ１ｇ）と、ルートノード１１の固有検証鍵（ｘｒｇ）とを用いて正当性を検証し、リーフノード確認検証鍵（ｖｃｉｒｃ−１１１）に対して、リーフノード３１の固有検証鍵（ｘ１１１ｇ）と、正当性が検証された中間ノード経由検証鍵（ｖｐａｓｓ−１）とを用いて正当性を検証する。なお、本工程では、すべての正当性が検証されたことを条件として第２の検証工程ＳＴ１６に進む。
【００７０】
第２の検証工程ＳＴ１６において、第２の検証部１７は、正当性が検証されたリーフノード確認検証鍵（ｖｃｉｒｃ−１１１）に基づいて、リーフノード署名情報（σｃｉｒｃ−１１１（＝ｘ１１１（ｘｒｘ１ｇ）））の正当性を検証する。
【００７１】
このようにして、回覧システム１では、第１の検証部１６により、中間ノード経由検証鍵（ｖｐａｓｓ−１）に対して、当該中間ノード経由検証鍵（ｖｐａｓｓ−１）を送信してきた中間ノード２１の固有検証鍵（ｘ１ｇ）と、ルートノード１１の固有検証鍵（ｘｒｇ）とを用いて正当性を検証し、つぎに、リーフノード確認検証鍵（ｖｃｉｒｃ−１１１）に対して、リーフノード３１の固有検証鍵（ｘ１１１ｇ）と、正当性が検証された中間ノード経由検証鍵（ｖｐａｓｓ−１）とを用いて正当性を検証される。また、回覧システム１では、第２の検証部１７により、正当性が検証されたリーフノード確認検証鍵（ｖｃｉｒｃ−１１１）に基づいて、リーフノード署名情報（σｃｉｒｃ−１１１）の正当性が検証される。
【００７２】
したがって、本実施形態に係る回覧方法によれば、回覧物（Ｍ）がどの中間ノード２１及びリーフノード３１に流通し、誰が回覧したのかを知ることができる。
【００７３】
＜署名方式について＞
つぎに、上述した本発明によって採用される具体的な署名方式について説明する。回覧システム１では、ベースとなる署名方式としてＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＧＤＨ）署名を採用する。ＧＤＨ署名とは、Ｄｅｃｉｓｉｏｎ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＤＤＨ）問題をペアリングと呼ばれるある種のブラックボックス関数ｅ（Ｐ，Ｑ）を用いることで、解くことが可能であることを利用した署名である。
【００７４】
つぎに、ペアリング演算を用いたＧＤＨ署名について説明する。楕円曲線上のＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題に関連して、ＧＤＨグループが定義されている。ＧＤＨグループについて簡単に説明する。Ｇをある楕円曲線上の点の集合とする。ｇを集合Ｇの要素としたとき、集合Ｇにおける楕円曲線上のＤｅｃｉｓｉｏｎａｌ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＤＤＨ）問題とＣｏｍｐｕｔａｔｉｏｎａｌ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＣＤＨ）問題が以下のように定義される。
【００７５】
ＤＤＨ問題：あるａ、ｂ、ｃという自然数があり、ｇ、ａｇ、ｂｇ、ｃｇが与えられた時、ｃ＝ａｂかどうかを判定する問題
ＣＤＨ問題：あるａ、ｂ、ｃという自然数があり、ｇ、ａｇ、ｂｇが与えられた時、ａｂｇを計算する問題
【００７６】
このとき、ＤＤＨ問題は、計算量的に簡単であるが、ＣＤＨ問題は、計算量的に難問である場合、この集合ＧをＧＤＨグループと定義する。
【００７７】
これに対し、ある楕円曲線上の点をＰ，Ｑとし、そのＰ，Ｑによっては次にあげる性質を持つことができるペアリングと呼ばれるブラックボックス関数ｅ（Ｐ，Ｑ）を定義できるものが存在する。
ｅ（ａＰ，ｂＱ）＝ｅ（ｂＰ，ａＱ）＝ｅ（ａｂＰ，Ｑ）＝ｅ（Ｐ，ａｂＱ）＝ｅ（Ｐ，Ｑ）ａｂ・・・（１）
【００７８】
よって、ｇがペアリング演算が可能な楕円曲線上の点である場合には、上記の性質から、（１）式にｇ、ａｇ、ｂｇ、ｃｇを入力すると、
ｅ（ａｇ，ｂｇ）＝ｅ（ｇ，ｇ）ａｂ・・・（２）
ｅ（ｇ，ｃｇ）＝ｅ（ｇ，ｇ）ｃ・・・（３）
となり、両者の値が一致するかどうかにより、「ａｂ＝ｃ」であるかどうかを判定でき、ｇはＧＤＨグループＧの要素となりうる。
【００７９】
この性質を利用してＧＤＨ署名が構成される。集合Ｇは、ＧＤＨグループであり、ｇは集合Ｇの要素となる点とする。また、一方向性ハッシュ関数Ｈを、通常使用される任意のビット長のサイズの数値データを固定のビット長のサイズの数値データに写像変換される方式とは異なり、
Ｈ：｛０，１｝＊→Ｇ
のように任意のビット長のサイズの数値データを楕円曲線上の点として表現されるＧＤＨグループＧの要素に写像変換する方式であると定義する（例えば、ｓをＳＨＡ−１（ｐｌａｉｎｔｅｘｔ）のように通常使用される一方向性ハッシュ関数としたとき、ｓｇとして表される式は、ここで定義する一方向性ハッシュ関数Ｈの条件を満たす）。
【００８０】
このとき、ＧＤＨ署名は以下のように定義される。
鍵生成：自然数ｘを選び、ｇからｖ＝ｘｇを計算する。ｘを署名鍵、楕円上の点ｖを検証鍵とする。
署名：署名者は、メッセージ「ｍ∈｛０，１｝＊」に対しｈ＝Ｈ（ｍ）を計算し、さらに自分の署名鍵を用いてσ＝ｘｈを計算する。σをｍに対する署名として公開する。
検証：検証者は、メッセージｍからｈ＝Ｈ（ｍ）を計算し、ｇ、ｖ、ｈ、σを準備する。ｅ（ｇ，σ）とｅ（ｖ，ｈ）を計算し、両者の値が一致したら、署名σは、正しい署名と判定する。
【００８１】
このとき、ｈの値は集合Ｇの要素となるので、ある自然数ｙを用いてｈ＝ｙｇと表現できる。その結果、正しく署名が行われていれば（ｇ，ｖ，ｈ，σ）＝（ｇ，ｘｇ，ｙｇ，ｘｙｇ）となる。したがって、正当な署名であれば上記の検証でのペアリング演算は、ｅ（ｇ，σ）＝ｅ（ｇ，ｘｙｇ）＝ｅ（ｇ，ｇ）ｘｙ＝ｅ（ｘｇ，ｙｇ）＝ｅ（ｖ，ｈ）となり、値が一致することから、検証可能となる。なお、ＧＤＨグループの条件であるＣＤＨ問題の困難性から、署名鍵ｘを知らない第三者がｇ、ｖ、ｈの値から署名σを導出することは不可能である。
【００８２】
また、本実施例における検証方式の手順の概要は以下の通りである。なお、以下では、説明の便宜上、図４に示す中間ノード２１ａから２１ｆを中間ノード２１といい、リーフノード３１ａから３１ｈをリーフノード３１という。
【００８３】
（手順１）組織内のグループ又は部署の関係を木構造（ツリー構造）とする。その際に、ルートノード１１が配置される最上位層Ａには、回覧物（Ｍ）の発信者がおり、中間ノード２１が配置される中位層Ｂには、回覧物（Ｍ）の責任仲介者（グループ又は部署の責任者）がおり、リーフノード３１が配置される最下位層Ｃには一般メンバーがいる。
【００８４】
（手順２）ルートノード１１は、回覧物（Ｍ）のハッシュ（楕円曲線上の点）を作成し、それに署名鍵をかけて署名を作成する。回覧物、署名、公開鍵を直下のノードに送信する。
【００８５】
（手順３）ルートノード１１の直下にある中間ノード２１は、受信した署名に自分の署名鍵をかけたものを作成し、これをこの中間ノード２１までの経由署名とする。また、受信したルートノード１１の検証鍵に自分の署名鍵をかけたものを作成し、これをこの中間ノードまでの経由署名の検証鍵（以後、経由検証鍵という。）とする。回覧物（Ｍ）、経由署名、経由検証鍵を直下のノードに送る。
【００８６】
（手順４）以後、中間ノード２１は、直上のノードから受信した経由署名に自分の署名鍵をかけたものを作成し、これをこの中間ノード２１までの新たな経由署名とする。また、受信した直上のノードの経由検証鍵に自分の署名鍵をかけたものを作成し、これをこの中間ノード２１までの新たな経由検証鍵とする。回覧物（Ｍ）、この中間ノード２１で作成した経由署名、経由検証鍵を直下のノードに送る。
【００８７】
（手順５）リーフノード３１は、直上のノードから受信した経由署名に自分の署名鍵をかけたものを作成し、これをリーフノード３１の回覧確認署名とする。また、受信した直上のノードの経由検証鍵に自分の署名鍵をかけたものを作成し、これをリーフノード３１の回覧確認署名の検証鍵（以後、回覧確認検証鍵という。）とする。このリーフノード３１が作成した回覧確認署名、回覧確認検証鍵を直上のノードに送信する。
【００８８】
（手順６）リーフノード３１の直上にある中間ノード２１は、直下のリーフノードから受信した回覧確認署名をリーフノード３１から自分までの回覧確認署名として、ルートノード１１に送信する。自分の直下のリーフノード３１で作成した回覧確認検証鍵とこの中間ノード２１で作成した回覧確認署名と経由検証鍵（手順３及び手順４）を直上のノードに送る。なお、中間ノード２１の直下にリーフノード３１が２つ配置されている場合には、中間ノード２１は、直下のリーフノード３１から受信した全回覧確認署名を足し合わせて、これをリーフノード３１から自分までの回覧確認署名として、ルートノード１１に送信する。
【００８９】
（手順７）以後、中間ノード２１は、直下のノードから受信したその直下のノードで作成された全回覧確認署名を足し合わせて、これをそれぞれリーフノード３１から自分までの回覧確認署名とする。自分のノードからたどれるリーフノード３１すべての回覧確認検証鍵と自分のノードからたどれる下位の中間ノード２１すべての経由検証鍵（手順３及び手順４）と、この中間ノード２１で作成した回覧確認署名を直上のノードに送る。
【００９０】
（手順８）ルートノード１１は、直下の中間ノード２１から受信した回覧確認署名を検証することで、回覧物（Ｍ）がどの中間ノード２１及びリーフノード３１に流通しているかを確認する。
ここで、回覧確認署名の検証は、以下の通りに実行する。
（ａ）ルートノード１１直下の中間ノード２１が作成した経由検証鍵に対し、それに対応するルートノード１１及びルートノード１１直下の検証鍵を用いて、ペアリング演算によるＤＤＨ判定にて正当性を検証する。
【００９１】
（ｂ）以後、途中の中間ノード２１で作成された経由検証鍵に対し、正当性が保証された直上の中間ノード２１で作成された経由検証鍵と、正当性を検証しようとしている経由検証鍵を作成した中間ノード２１の検証鍵を用いて、ペアリング演算によるＤＤＨ判定にて正当性を検証する。これを順にリーフノード３１直上の中間ノード２１で作成された経由検証鍵まで繰り返す。
【００９２】
（ｃ）リーフノード３１直上の中間ノード２１で作成された経由検証鍵まで正当性が保証されたら、その経由検証鍵とリーフノード３１の検証鍵を用いて、ペアリング演算によるＤＤＨ判定にて回覧確認検証鍵の正当性を検証する。
【００９３】
（ｄ）そして、回覧確認検証鍵を使って、回覧確認署名を検証する。
【００９４】
＜実施例＞
つぎに、上述した本発明を利用して、回覧物（Ｍ）の流通と署名の作成について、図３を参照しながら具体的に説明する。図３（ａ）には、各ノードにおいて行われる回覧物（Ｍ）の流通と署名の作成の様子を模式的に示し、図３（ｂ）には、ルートノード１１において実行される署名の検証方法について模式的に示し、図３（ｃ）には、署名鍵と検証鍵が認証局（ＣＡ）によって重複しないように各ノードに付与されている様子を模式的に示している。また、図３には、一部のノードの動作のみを示し、他のノードの動作を省略しているが、他のノードにおいても図示したノードと同様の動作が行われる。
【００９５】
また、以下の説明では、２分木４階層によるツリー構造であって、図４に示すように、ルートノード１１が属する最上位層Ａと、複数の中間ノード２１が属する中位層Ｂと、複数のリーフノード３１が属する最下位層Ｃとにより構成されているものとする。また、中位層Ｂは、ルートノード１１の直下の階層に配置される中間ノード２１ａと中間ノード２１ｂと、中間ノード２１ａの直下の階層に配置される中間ノード２１ｃと中間ノード２１ｄと、中間ノード２１ｂの直下の階層に配置される中間ノード２１ｅと中間ノード２１ｆとにより構成される。また、最下位層Ｃは、中間ノード２１ｃの直下に配置されるリーフノード３１ａとリーフノード３１ｂと、中間ノード２１ｄの直下に配置されるリーフノード３１ｃとリーフノード３１ｄと、中間ノード２１ｅの直下に配置されるリーフノード３１ｅとリーフノード３１ｆと、中間ノード２１ｆの直下に配置されるリーフノード３１ｇとリーフノード３１ｈとにより構成される。
【００９６】
また、中位層Ｂにおいて、ルートノード１１の直下に配置される中間ノード２１ａ、２１ｂは、第１中間ノードといい、第１中間ノードの直下に配置される中間ノード２１ｃから２１ｆは、第２中間ノードという。
【００９７】
（過程１）認証局（ＣＡ）によって付与される、回覧物発信者（ルートノード１１）、責任仲介者（中間ノード２１ａから２１ｆ）及び一般メンバー（リーフノード３１ａから３１ｈ）の署名鍵と検証鍵は以下の通りとする。
ルートノード：（ｘｒ，ｖｒ）＝（ｘｒ，ｘｒｇ）
第１中間ノード：（ｘｍ，ｖｍ）＝（ｘｍ，ｘｍｇ）
第２中間ノード：（ｘｍｎ，ｖｍｎ）＝（ｘｍｎ，ｘｍｎｇ）
リーフノード：（ｘｍｎｏ，ｖｍｎｏ）＝（ｘｍｎｏ，ｘｍｎｏｇ）
（ただし、ｍ，ｎ，ｏは、１≦ｍ，ｎ，ｏ≦２となる整数の符号である。）
【００９８】
（過程２）ルートノード１１は、回覧物（Ｍ）に対しし、そのハッシュ値ｈ＝Ｈａｓｈ（Ｍ）（＝ａｇ）を求める。このハッシュ値ｈに自分の署名鍵（ｘｒ）をかけて、
ｘｒｈ（＝ａｘｒｇ）・・・（４）
を求め、これを署名とする。この署名（ｘｒｈ）に回覧物（Ｍ）、自分の検証鍵（ｖｒ）を直下のノード（中間ノード２１ａ及び中間ノード２１ｂ）に送信する。
【００９９】
（過程３）第１中間ノード（中間ノード２１ａと中間ノード２１ｂ）は、ルートノード１１から受け取った署名（ｘｒｈ）に自分の署名鍵（ｘｍ）をかけて、
σｐａｓｓ−ｍ＝ｘｍ（ｘｒｈ）＝ｘｒｘｍｈ・・・（５）
を作成し、σｐａｓｓ−ｍをこの第１中間ノードまでの経由署名とする。
【０１００】
また、ルートノード１１から受け取った検証鍵ｖｒに自分の署名鍵ｘｍをかけて
ｖｐａｓｓ−ｍ＝ｘｍ（ｘｒｇ）＝ｘｒｘｍｇ・・・（６）
を作成し、ｖｐａｓｓ−ｍをこの第１中間ノードまでの経由検証鍵とする。
【０１０１】
回覧物（Ｍ）、この第１中間ノードで作成した経由署名σｐａｓｓ−ｍと経由検証鍵ｖｐａｓｓ−ｍを直下の第２中間ノード（中間ノード２１ｃから２１ｆ）に送信する。
【０１０２】
（過程４）第２中間ノードは、第１中間ノードから受け取った経由署名σｐａｓｓ−ｍに自分の署名鍵ｘｍｎをかけて
σｐａｓｓ−ｍｎ＝ｘｍｎ（ｘｍｘｒｈ）＝ｘｒｘｍｘｍｎｈ・・・（７）
を作成し、σｐａｓｓ−ｍｎをこの第２中間ノードまでの経由署名とする。
【０１０３】
また、第１中間ノードから受け取った経由検証鍵ｖｐａｓｓ−ｍに自分の署名鍵ｘｍｎをかけて
ｖｐａｓｓ−ｍｎ＝ｘｍｎ（ｘｍｘｒｇ）＝ｘｒｘｍｘｍｎｇ・・・（８）
を作成し、ｖｐａｓｓ−ｍｎをこの第２中間ノードまでの経由検証鍵とする。
【０１０４】
回覧物（Ｍ）、この第２中間ノードで作成した経由署名σｐａｓｓ−ｍｎと経由検証鍵ｖｐａｓｓ−ｍｎを直下のリーフノード３１に送信する。
【０１０５】
（過程５）リーフノード３１（３１ａから３１ｈ）は、第２中間ノードから受け取った経由署名σｐａｓｓ−ｍｎに自分の署名鍵ｘｍｎｏをかけて
σｃｉｒｃ−ｍｎｏ＝ｘｍｎｏ（ｘｍｎｘｍｘｒｈ）＝ｘｒｘｍｘｍｎｘｍｎｏｈ・・・（９）
を作成し、σｃｉｒｃ−ｍｎｏをこのリーフノードまでの回覧確認署名とする。
【０１０６】
また、第２中間ノードから受け取った経由検証鍵ｖｐａｓｓ−ｍｎに自分の署名鍵ｘｍｎｏをかけて
ｖｃｉｒｃ−ｍｎｏ＝ｘｍｎｏ（ｘｍｎｘｍｘｒｇ）＝ｘｒｘｍｘｍｎｘｍｎｏｇ・・・（１０）
を作成し、ｖｃｉｒｃ−ｍｎｏをこのリーフノードまでの回覧確認検証鍵とする。
【０１０７】
このリーフノードで作成した回覧確認署名σｃｉｒｃ−ｍｎｏと経由検証鍵ｖｃｉｒｃ−ｍｎｏを直上の第２中間ノード（中間ノード２１ｃから２１ｆ）に送信する。
【０１０８】
（過程６）第２中間ノード（中間ノード２１ｃから２１ｆ）のそれぞれは、直下のリーフノードから受信した回覧確認署名σｃｉｒｃ−ｍｎｏを足し合わせた
σｃｉｒｃ−ｍｎ＝ｘｒｘｍｘｍｎ（ｘｍｎ１＋ｘｍｎ２）ｈ・・・（１１）
を作成し、σｃｉｒｃ−ｍｎをリーフノードからこの第２中間ノードまでの回覧確認署名とする。なお、本実施例では、第２中間ノードの直下には２つのリーフノードが配置されている構成を想定しているが、３つ以上のリーフノードが配置される構成の場合には、第２中間ノードは、リーフノードから送信されてくる３つ以上の回覧確認署名を足し合わせて「σｃｉｒｃ−ｍｎ」を作成する。
【０１０９】
また、第２中間ノードは、自分の直下で作成した回覧確認検証鍵ｖｃｉｒｃ−ｍｎｏと、自身で作成した回覧確認署名σｃｉｒｃ−ｍｎ及び経由検証鍵ｖｐａｓｓ−ｍｎを直上の第１中間ノードに送信する。
【０１１０】
（過程７）第１中間ノードは、直下の第２中間ノードから受信したすべての回覧確認署名σｃｉｒｃ−ｍｎを足し合わせた
σｃｉｒｃ−ｍ＝ｘｒｘｍ（ｘｍ１（ｘｍ１１＋ｘｍ１２）＋ｘｍ２（ｘｍ２１＋ｘｍ２２））ｈ・・・（１２）
を作成し、σｃｉｒｃ−ｍをリーフノードからこの第１中間ノードまでの回覧確認署名とする。
【０１１１】
第１中間ノードのそれぞれは、自分からたどれるリーフノードで作成した回覧確認検証鍵ｖｃｉｒｃ−ｍｎｏと、自身で作成した回覧確認署名σｃｉｒｃ−ｍ及び経由検証鍵ｖｐａｓｓ−ｍ、自分の配下すべての経由検証鍵ｖｐａｓｓ−ｍｎを直上のルートノード１１に送信する。
【０１１２】
＜ルートノード１１による検証＞
ルートノード１１は、検証を次のように行う。
（検証１）ルートノード１１は、第１中間ノード（中間ノード２１ａ及び中間ノード２１ｂ）の検証鍵ｖｍと、第１中間ノードが作成した経由検証鍵ｖｐａｓｓ−ｍと自分の検証鍵ｖｒ（とｇ）を使って、ｅ（ｇ，ｖｐａｓｓ−ｍ）とｅ（ｖｒ，ｖｍ）を計算する。両者の値が一致した場合には、第１中間ノードが作成した経由検証鍵ｖｐａｓｓ−ｍは、正当性が検証されたことになる。なお、本工程においては、第１中間ノードは、２つの中間ノード（中間ノード２１ａ及び中間ノード２１ｂ）により構成されているので、２つの経由検証鍵ｖｐａｓｓ−ｍについて正当性を検証する。
【０１１３】
具体的には、
【数１】
2011029782.tif 000003
と、
【数２】
2011029782.tif 000004
となり、正当な過程（ノード）を経由していれば両者の値が一致する。
【０１１４】
（検証２）ルートノード１１は、第２中間ノード（中間ノード２１ｃから２１ｆ）の検証鍵ｖｍｎと、第２中間ノードが作成した経由検証鍵ｖｐａｓｓ−ｍｎと、上記（１）で正当性が検証された第１中間ノード作成の経由検証鍵ｖｐａｓｓ−ｍ（とｇ）を使って、ｅ（ｇ，ｖｐａｓｓ−ｍｎ）とｅ（ｖｐａｓｓ−ｍ，ｖｍｎ）を計算する。両者の値が一致した場合には、第２中間ノードが作成した経由検証鍵ｖｐａｓｓ−ｍｎは、正当性が検証されたことになる。なお、本工程においては、第２中間ノードは、４つの中間ノード（中間ノード２１ｃから２１ｆ）により構成されているので、４つの経由検証鍵ｖｐａｓｓ−ｍｎについて正当性を検証する。
【０１１５】
具体的には、
【数３】
2011029782.tif 000005
と、
【数４】
2011029782.tif 000006
となり、正当な過程（ノード）を経由していれば両者の値が一致する。
【０１１６】
（検証３）ルートノード１１は、リーフノード３１の検証鍵ｖｍｎｏと、リーフノード３１が作成した回覧確認検証鍵ｖｃｉｒｃ−ｍｎｏと、上記（２）で正当性が検証された第２中間ノードによって作成された経由検証鍵ｖｐａｓｓ−ｍｎ（とｇ）を使って、ｅ（ｇ，ｖｃｉｒｃ−ｍｎｏ）とｅ（ｖｐａｓｓ−ｍｎ，ｖｍｎｏ）を計算する。両者の値が一致した場合には、リーフノードが作成したｖｃｉｒｃ−ｍｎｏは、正当性が検証されたことになる。なお、本工程においては、リーフノードは、８つのノード（リーフノード３１ａから３１ｈ）により構成されているので、８つの経由検証鍵ｖｐａｓｓ−ｍｎｏについて正当性を検証する。
【０１１７】
具体的には、
【数５】
2011029782.tif 000007
と、
【数６】
2011029782.tif 000008
となり、正当な過程（ルート）を経由していれば両者の値が一致する。
【０１１８】
（検証４）ルートノード１１は、正当性が検証された８つの経由検証鍵ｖｃｉｒｃ−ｍｎｏとルートノードが受信した２つの回覧確認署名σｃｉｒｃ−ｍとハッシュｈ（とｇ）を使って、
【数７】
2011029782.tif 000009
【数８】
2011029782.tif 000010
を計算する。両者の値が一致した場合には、受信した回覧確認署名の正当性が検証されることになる。
【０１１９】
本工程では、ｖｃｉｒｃ−ｍｎｏの正当性が検証されれば、これを検証鍵と見立ててＧＤＨ署名の検証と同じことをしており、これにより多重署名の検証が可能となる。
【０１２０】
また、上述した回覧物（Ｍ）の流通と署名作成の（過程２）から（過程４）において、同時に上位のノードから送信されてきている経由検証鍵も下位のノードが共有できるように配布（例えば、回覧物（Ｍ）と一緒に配布）しておくことで、（検証１）から（検証４）と同様の手順により、どのノードにおいても自分の手元にある経由署名や回覧確認署名を検証することが可能となる。これにより、流通過程の正当性の保証や、中間ノードの段階での回覧状況確認が可能となる。
【０１２１】
また、本実施形態に係る回覧システム１では、全署名（経由署名や回覧確認署名）及び全検証鍵（経由検証鍵や回覧確認検証鍵）は、署名鍵の入れ子構造による式で演算されており、これにより流通過程が把握できる。当該式については、ＣＤＨ問題や楕円曲線上の離散対数問題から、秘密情報である署名鍵を知らない者が、式中の任意の署名鍵を排除や改ざんすることができないため、第三者による不正は困難であると言える。
【０１２２】
このようにして、本実施形態に係る回覧システム１では、ツリー構造によってメンバー構成を示すことが可能な電子署名を用いることによって、例えば、会社の組織状況に合わせて、回覧物（Ｍ）がどのように流通し、誰が回覧したかを確認することができる。
【０１２３】
なお、本実施例においては、２分木４階層によるツリー構造における回覧物（Ｍ）の回覧方法について説明したが、これに限らず、本発明に係る回覧システム１は、３分木３階層等の多分木多階層によるツリー構造においても適用可能である。
【０１２４】
また、上述で説明した回覧システム１による一連の処理は、ソフトウェアにより行うこともできる。一連の処理をソフトウェアによって行う場合には、そのソフトウェアを構成するプログラムが、汎用のコンピュータ等にインストールされる。また、当該プログラムは、ＣＤ−ＲＯＭのようなリムーバブルメディアに記録されてユーザに配布されても良いし、ネットワークを介してユーザのコンピュータにダウンロードされることにより配布されても良い。
【符号の説明】
【０１２５】
１  回覧システム
１１  ルートノード
１２  一方向性ハッシュ関数演算部
１３  ルートノード署名情報生成部
１４  ルートノード送信部
１５  ルートノード受信部
１６  第１の検証部
１７  第２の検証部
２１  中間ノード
２２  中間ノード受信部
２３  中間ノード署名情報生成部
２４  中間ノード経由検証鍵生成部
２５  中間ノード送信部
３１  リーフノード
３２  リーフノード受信部
３３  リーフノード署名情報生成部
３４  リーフノード確認検証鍵生成部
３５  リーフノード送信部
【図１】
2011029782.tif 000011
【図２】
2011029782.tif 000012
【図３】
2011029782.tif 000013
【図４】
2011029782.tif 000014
【手続補正書】
【提出日】平成21年8月12日(2009.8.12)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００３１
【補正方法】変更
【補正の内容】
【００３１】
ルートノード署名情報生成部１３は、ハッシュ（ｈ）にルートノード１１の固有署名鍵（ｘｒ）で暗号化を行ってルートノード署名情報（ｘｒｈ（＝ａｘｒｇ））を生成する。なお、詳細は後述するが、ｇは、ＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループと呼ばれるある特定の楕円曲線上の点の集合Ｇの要素である。
ここで、一方向性ハッシュ関数演算部１２による演算においては、一方向性ハッシュ関数Ｈを、通常使用される任意のビット長のサイズの数値データを固定のビット長のサイズの数値データに写像変換される方式とは異なり、
Ｈ：｛０，１｝＊→Ｇ
のように任意のビット長のサイズの数値データを楕円曲線上の点として表現されるＧＤＨグループＧの要素に写像変換する方式であると定義する。また、集合Ｇは、ＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループを示し、ｇは、集合Ｇの要素となる点を示している。なお、一方向性ハッシュ関数Ｈについての詳細は後述する。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００７９
【補正方法】変更
【補正の内容】
【００７９】
この性質を利用してＧＤＨ署名が構成される。集合Ｇは、ＧＤＨグループであり、ｇは集合Ｇの要素となる点とする。また、一方向性ハッシュ関数Ｈを、通常使用される任意のビット長のサイズの数値データを固定のビット長のサイズの数値データに写像変換される方式とは異なり、
Ｈ：｛０，１｝＊→Ｇ
のように任意のビット長のサイズの数値データを楕円曲線上の点として表現されるＧＤＨグループＧの要素に写像変換する方式であると定義する。