(57)【要約】【課題】署名者がどの階層に属しているかを表現できるアグリゲート署名生成システム、アグリゲート署名生成方法、およびアグリゲート署名生成プログラムを提供すること。【解決手段】署名を行う署名者ごとにノードを設け、これら複数のノードを複数層のヒエラルキーを形成して配置する。互いに異なるメッセージに対して各署名者が自身のノードを用いて署名を行い、これら署名を集めたアグリゲート署名σを、メッセージｍｆ−ｑのハッシュｈｆ−ｑに対して各署名者の署名鍵と、自身が属する階層ごとに異なる所定値と、でべき乗演算を行うことで表す。【選択図】図１
2010087590.tif 000002
【特許請求の範囲】
【請求項１】
署名者が署名を行うために用いる署名生成装置が複数階層の階層構造を形成して複数配置され、各署名者が異なるメッセージに対して署名を行うアグリゲート署名生成システムであって、
前記複数の署名生成装置のそれぞれは、
互いに異なる秘密鍵と、所定のパラメータに対して自身の前記秘密鍵でべき乗演算した公開鍵と、を格納する鍵格納部と、
自身のメッセージのハッシュに対して自身の前記秘密鍵でべき乗演算を行って、署名を生成する署名生成部と、
前記署名生成部により生成された前記署名に対して、自身が属する階層ごとに異なる所定値でべき乗演算を行うべき乗演算部と、
を備え、
前記複数の署名生成装置のうち所定の署名生成装置は、前記べき乗演算部による演算結果の総和を階層ごとに算出し、階層ごとの算出結果を乗算して、アグリゲート署名を生成するアグリゲート署名生成部をさらに備えることを特徴とするアグリゲート署名生成システム。
【請求項２】
前記所定値は、自身が属する階層と、最下位層と、の階層数の差だけ特定値をべき乗演算した値であることを特徴とする請求項１に記載のアグリゲート署名生成システム。
【請求項３】
前記アグリゲート署名を検証する署名検証装置をさらに備え、
前記署名検証装置は、前記所定のパラメータ、前記公開鍵、前記メッセージのハッシュ、および前記アグリゲート署名を入力として、ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ署名の演算を行って、前記アグリゲート署名の正当性を検証するアグリゲート署名検証部を備えることを特徴とする請求項１または２に記載のアグリゲート署名生成システム。
【請求項４】
署名者が署名を行うために用いる署名生成装置が複数階層の階層構造を形成して複数配置されたアグリゲート署名生成システムにおいて、各署名者が異なるメッセージに対して署名を行うアグリゲート署名生成方法であって、
前記複数の署名生成装置のそれぞれにより、互いに異なる秘密鍵と、所定のパラメータに対して自身の前記秘密鍵でべき乗演算した公開鍵と、を格納する第１のステップと、
前記複数の署名生成装置のそれぞれにより、自身のメッセージのハッシュに対して自身の前記秘密鍵でべき乗演算を行って、署名を生成する第２のステップと、
前記複数の署名生成装置のそれぞれにより、前記第２のステップにより生成された前記署名に対して、自身が属する階層ごとに異なる所定値でべき乗演算を行う第３のステップと、
前記複数の署名生成装置のうち所定の署名生成装置により、前記第３のステップによる演算結果の総和を階層ごとに算出し、階層ごとの算出結果を乗算して、アグリゲート署名を生成する第４のステップと、
を備えることを特徴とするアグリゲート署名生成方法。
【請求項５】
前記所定値は、自身が属する階層と、最下位層と、の階層数の差だけ特定値をべき乗演算した値であることを特徴とする請求項４に記載のアグリゲート署名生成方法。
【請求項６】
前記アグリゲート署名を検証する署名検証装置がさらに配置された前記アグリゲート署名生成システムにおけるアグリゲート署名生成方法であって、
前記署名検証装置により、前記所定のパラメータ、前記公開鍵、前記メッセージのハッシュ、および前記アグリゲート署名を入力として、ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ署名の演算を行って、前記アグリゲート署名の正当性を検証する第５のステップを備えることを特徴とする請求項４または５に記載のアグリゲート署名生成方法。
【請求項７】
署名者が署名を行うために用いる署名生成装置が複数階層の階層構造を形成して複数配置されたアグリゲート署名生成システムにおいて、各署名者が異なるメッセージに対して署名を行うアグリゲート署名生成方法を、コンピュータに実行させるためのアグリゲート署名生成プログラムであって、
前記複数の署名生成装置のそれぞれにより、互いに異なる秘密鍵と、所定のパラメータに対して自身の前記秘密鍵でべき乗演算した公開鍵と、を格納する第１のステップと、
前記複数の署名生成装置のそれぞれにより、自身のメッセージのハッシュに対して自身の前記秘密鍵でべき乗演算を行って、署名を生成する第２のステップと、
前記複数の署名生成装置のそれぞれにより、前記第２のステップにより生成された前記署名に対して、自身が属する階層ごとに異なる所定値でべき乗演算を行う第３のステップと、
前記複数の署名生成装置のうち所定の署名生成装置により、前記第３のステップによる演算結果の総和を階層ごとに算出し、階層ごとの算出結果を乗算して、アグリゲート署名を生成する第４のステップと、
をコンピュータに実行させるためのアグリゲート署名生成プログラム。
【請求項８】
前記所定値は、自身が属する階層と、最下位層と、の階層数の差だけ特定値をべき乗演算した値であることを特徴とする請求項７に記載のアグリゲート署名生成プログラム。
【請求項９】
前記アグリゲート署名を検証する署名検証装置がさらに配置された前記アグリゲート署名生成システムにおけるアグリゲート署名生成プログラムであって、
前記署名検証装置により、前記所定のパラメータ、前記公開鍵、前記メッセージのハッシュ、および前記アグリゲート署名を入力として、ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ署名の演算を行って、前記アグリゲート署名の正当性を検証する第５のステップを備えることを特徴とする請求項７または８に記載のアグリゲート署名生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、アグリゲート署名生成システム、アグリゲート署名生成方法、およびアグリゲート署名生成プログラムに関する。
【背景技術】
【０００２】
従来、様々な電子情報がネットワークやメディアを介して送信されているが、電子情報の発信源を保証する仕組みとして、電子署名がある。電子署名とは、特定の人しか知り得ない署名鍵と電子情報とを入力値として署名の演算を行い、検証者が検証鍵と言われる公開された情報と署名されたデータとを入力値として検証演算を行うことで、上述の特定の人がデータの発信源であるか否かを確認できるものである。この電子署名によれば、検証鍵から署名鍵を導出することが計算量的に困難であるため、特定の人ではない人が特定の人に成りすまして署名を行うことができず、署名の正当性を保証できる。
【０００３】
ここで、電子情報によっては、複数の人が介在して署名を行うケースが想定される。このケースとしては、例えば、電子データの回覧や、会社における承認システムが該当する。そこで、複数人の署名を行う方式として、多重署名（非特許文献１）やグループ署名（特許文献１）が提案されている。
【０００４】
ところが、上述の多重署名やグループ署名は、１つのメッセージに対して複数の署名者が署名を行うものであるため、メッセージを追加する回覧などでは利用できない。そこで、各署名者が互いに異なるメッセージに署名を行い、これら署名が行われたものを集合させる方式として、アグリゲート電子署名（非特許文献２および３）が提案されている。このアグリゲート電子署名によれば、署名者数に関係なく署名サイズを一定のサイズで納めつつ、各署名者が異なるメッセージに署名したものを集合させることができる。このため、アグリゲート電子署名をメッセージを追加する回覧などでは利用できる。
【非特許文献１】新保、「多重署名に適したＥｌＧａｍａｌ署名の一変形方式」、暗号と情報セキュリティシンポジウム（ＣＳＳ）、２Ｃ、電子情報通信学会、１９９４
【非特許文献２】寺西勇、佐古和恵、野田潤、田口大悟、「署名長が署名者数に比例しないＲＳＡベースＳｅｑｕｅｎｃｉａｌ  Ａｇｇｒｅｇａｔｅ署名方式」、ＣＳＥＣ−２８、２００５
【非特許文献３】Ｄ．Ｂｏｎｅｈ，Ｃ．Ｇｅｎｔｒｙ，Ｂ．Ｌｙｎｎ，  ａｎｄ  Ｈ．Ｓｈａｃｈａｍ，“Ａｇｇｒｅｇａｔｅ  ａｎｄ  Ｖｅｒｉｆｉａｂｌｙ  Ｅｎｃｒｙｐｔｅｄ  Ｓｉｇｎａｔｕｒｅｓ  ｆｒｏｍ  Ｂｉｌｉｎｅａｒ  Ｍａｐｓ，”Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  ＥＵＲＯＣＲＹＰＴ２００３，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，２００３
【特許文献１】特開２００１−１６６６８７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述のアグリゲート電子署名方式では、署名者がどの階層に属しているかを表現できなかった。
【０００６】
そこで、本発明は、上述の課題に鑑みてなされたものであり、署名者がどの階層に属しているかを表現できるアグリゲート署名生成システム、アグリゲート署名生成方法、およびアグリゲート署名生成プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明は、上記の課題を解決するために、以下の事項を提案している。
【０００８】
（１）本発明は、署名者が署名を行うために用いる署名生成装置が複数階層の階層構造を形成して複数配置され、各署名者が異なるメッセージに対して署名を行うアグリゲート署名生成システムであって、前記複数の署名生成装置のそれぞれは、互いに異なる秘密鍵と、所定のパラメータに対して自身の前記秘密鍵でべき乗演算した公開鍵と、を格納する鍵格納部と、自身のメッセージのハッシュに対して自身の前記秘密鍵でべき乗演算を行って、署名を生成する署名生成部と、前記署名生成部により生成された前記署名に対して、自身が属する階層ごとに異なる所定値でべき乗演算を行うべき乗演算部と、を備え、前記複数の署名生成装置のうち所定の署名生成装置は、前記べき乗演算部による演算結果の総和を階層ごとに算出し、階層ごとの算出結果を乗算して、アグリゲート署名を生成するアグリゲート署名生成部をさらに備えることを特徴とするアグリゲート署名生成システムを提案している。
【０００９】
この発明によれば、複数の署名生成装置のそれぞれは、署名生成部により、自身のメッセージのハッシュに対して自身の秘密鍵でべき乗演算を行って、署名を生成する。そして、べき乗演算部により、署名生成部により生成された署名に対して、自身が属する階層ごとに異なる所定値でべき乗演算を行う。そして、複数の署名生成装置のうち所定の署名生成装置は、アグリゲート署名生成部により、べき乗演算部による演算結果の総和を階層ごとに算出し、階層ごとの算出結果を乗算して、アグリゲート署名を生成する。
【００１０】
このため、アグリゲート署名は、メッセージのハッシュに対して、各自の秘密鍵と、所定値と、でべき乗演算が行われた構造で表される。そして、この所定値は、自身が属する階層ごとに異なる値である。したがって、アグリゲート署名を表す数式の指数の構造により、署名生成装置がどの階層に属するのかを表現できる。よって、各署名者が互いに異なる署名生成装置を用いることで、署名者がどの階層に属するのかを表現できる。
【００１１】
また、アグリゲート署名は、各署名者の署名と同じ巡回群にあるため、署名者の人数にかかわらず、一定のサイズに納めることができる。
【００１２】
（２）本発明は、（１）のアグリゲート署名生成システムについて、前記所定値は、自身が属する階層と、最下位層と、の階層数の差だけ特定値をべき乗演算した値であることを特徴とするアグリゲート署名生成システムを提案している。
【００１３】
この発明によれば、所定値は、自身が属する階層と、最下位層と、の階層数の差だけ特定値をべき乗演算した値で表される。このため、アグリゲート署名を表す数式の指数のうち、特定値により、署名生成装置がどの階層に属するのかを表現できる。
【００１４】
（３）本発明は、（１）または（２）のアグリゲート署名生成システムについて、前記アグリゲート署名を検証する署名検証装置をさらに備え、前記署名検証装置は、前記所定のパラメータ、前記公開鍵、前記メッセージのハッシュ、および前記アグリゲート署名を入力として、ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ署名の演算を行って、前記アグリゲート署名の正当性を検証するアグリゲート署名検証部を備えることを特徴とする記載のアグリゲート署名生成システムを提案している。
【００１５】
この発明によれば、署名検証装置は、アグリゲート署名検証部により、所定のパラメータ、公開鍵、メッセージのハッシュ、およびアグリゲート署名を入力として、ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ署名の演算を行って、アグリゲート署名の正当性を検証する。
【００１６】
ここで、以下に、ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ署名の演算について説明する。ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＧＤＨ）署名とは、Ｄｅｃｉｓｉｏｎ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＤＤＨ）問題をペアリングと呼ばれるある種のブラックボックス関数ｅ（Ｐ，Ｑ）を用いることで解けることを利用した署名である。
【００１７】
まず、ＤＤＨ問題について説明する。ＤＤＨ問題とは、ｇ、ｇａ、ｇｂ、ｇｃが与えられたときにａｂ＝ｃを満たすか否かを判定する問題のことである。この問題に対して、関数ｅ（Ｐ，Ｑ）には、以下の性質がある。
【００１８】
【数１】
2010087590.tif 000003
【００１９】
数１に示す性質から、関数ｅ（Ｐ，Ｑ）にｇ、ｇａ、ｇｂ、ｇｃを入力すると、数２、３のようになる。
【００２０】
【数２】
2010087590.tif 000004
【００２１】
【数３】
2010087590.tif 000005
【００２２】
このため、数２の値と数３の値とが一致するか否かにより、上述のａｂ＝ｃを満たすか否かを判定できる。
【００２３】
次に、ＧＤＨ署名の手順について説明する。ＧＤＨ署名では、鍵を生成し、この生成した鍵を用いて署名を行う。
【００２４】
鍵を生成する際には、Ｚｐ＊からランダムにｘを選択し、ｖ＝ｇｘとなるｖを算出する。そして、ｖを公開鍵とし、ｘを秘密鍵とする。
【００２５】
署名を行う際には、秘密鍵ｘとメッセージｍとを用意する。そして、メッセージｍからハッシュｈを算出し、ハッシュｈに対してｘ乗したものを署名σとする。
【００２６】
署名σを検証する際には、以下のように行う。ここで、ＧＤＨ署名はＧ＊の元を用いるため、ハッシュｈもＧ＊の元となり、その結果、ｈ＝ｇａが成り立つ。このため、署名σが正しければ、以下の式が成り立つ。
【００２７】
【数４】
2010087590.tif 000006
【００２８】
また、（ｇ，ｖ，ｈ，σ）を関数ｅ（Ｐ，Ｑ）に入力すると、以下の式が成り立つ。
【００２９】
【数５】
2010087590.tif 000007
【００３０】
【数６】
2010087590.tif 000008
【００３１】
上述のように、署名σが正しければ、数５の値と数６の値とは一致する。このため、数５の値と数６の値とが一致するか否かにより、署名σを検証できる。
【００３２】
以上によれば、ＧＤＨ署名の演算により、アグリゲート署名の正当性を検証できる。
【００３３】
（４）本発明は、署名者が署名を行うために用いる署名生成装置が複数階層の階層構造を形成して複数配置されたアグリゲート署名生成システムにおいて、各署名者が異なるメッセージに対して署名を行うアグリゲート署名生成方法であって、前記複数の署名生成装置のそれぞれにより、互いに異なる秘密鍵と、所定のパラメータに対して自身の前記秘密鍵でべき乗演算した公開鍵と、を格納する第１のステップと、前記複数の署名生成装置のそれぞれにより、自身のメッセージのハッシュに対して自身の前記秘密鍵でべき乗演算を行って、署名を生成する第２のステップと、前記複数の署名生成装置のそれぞれにより、前記第２のステップにより生成された前記署名に対して、自身が属する階層ごとに異なる所定値でべき乗演算を行う第３のステップと、前記複数の署名生成装置のうち所定の署名生成装置により、前記第３のステップによる演算結果の総和を階層ごとに算出し、階層ごとの算出結果を乗算して、アグリゲート署名を生成する第４のステップと、を備えることを特徴とするアグリゲート署名生成方法を提案している。
【００３４】
この発明によれば、複数の署名生成装置のそれぞれでは、自身のメッセージのハッシュに対して自身の秘密鍵でべき乗演算を行って、署名を生成する。そして、生成した署名に対して、自身が属する階層ごとに異なる所定値でべき乗演算を行う。そして、複数の署名生成装置のうち所定の署名生成装置では、べき乗演算の演算結果の総和を階層ごとに算出し、階層ごとの算出結果を乗算して、アグリゲート署名を生成する。
【００３５】
このため、アグリゲート署名は、メッセージのハッシュに対して、各自の秘密鍵と、所定値と、でべき乗演算が行われた構造で表される。そして、この所定値は、自身が属する階層ごとに異なる値である。したがって、アグリゲート署名を表す数式の指数の構造により、署名生成装置がどの階層に属するのかを表現できる。よって、各署名者が互いに異なる署名生成装置を用いることで、署名者がどの階層に属するのかを表現できる。
【００３６】
また、アグリゲート署名は、各署名者の署名と同じ巡回群にあるため、署名者の人数にかかわらず、一定のサイズに納めることができる。
【００３７】
（５）本発明は、（４）のアグリゲート署名生成方法について、前記所定値は、自身が属する階層と、最下位層と、の階層数の差だけ特定値をべき乗演算した値であることを特徴とするアグリゲート署名生成方法を提案している。
【００３８】
この発明によれば、所定値は、自身が属する階層と、最下位層と、の階層数の差だけ特定値をべき乗演算した値で表される。このため、アグリゲート署名を表す数式の指数のうち、特定値により、署名生成装置がどの階層に属するのかを表現できる。
【００３９】
（６）本発明は、（４）または（５）のアグリゲート署名生成方法について、前記アグリゲート署名を検証する署名検証装置がさらに配置された前記アグリゲート署名生成システムにおけるアグリゲート署名生成方法であって、前記署名検証装置により、前記所定のパラメータ、前記公開鍵、前記メッセージのハッシュ、および前記アグリゲート署名を入力として、ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ署名の演算を行って、前記アグリゲート署名の正当性を検証する第５のステップを備えることを特徴とするアグリゲート署名生成方法を提案している。
【００４０】
この発明によれば、署名検証装置では、所定のパラメータ、公開鍵、メッセージのハッシュ、およびアグリゲート署名を入力として、ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ署名の演算を行って、アグリゲート署名の正当性を検証する。このため、アグリゲート署名の正当性を検証できる。
【００４１】
（７）本発明は、署名者が署名を行うために用いる署名生成装置が複数階層の階層構造を形成して複数配置されたアグリゲート署名生成システムにおいて、各署名者が異なるメッセージに対して署名を行うアグリゲート署名生成方法を、コンピュータに実行させるためのアグリゲート署名生成プログラムであって、前記複数の署名生成装置のそれぞれにより、互いに異なる秘密鍵と、所定のパラメータに対して自身の前記秘密鍵でべき乗演算した公開鍵と、を格納する第１のステップと、前記複数の署名生成装置のそれぞれにより、自身のメッセージのハッシュに対して自身の前記秘密鍵でべき乗演算を行って、署名を生成する第２のステップと、前記複数の署名生成装置のそれぞれにより、前記第２のステップにより生成された前記署名に対して、自身が属する階層ごとに異なる所定値でべき乗演算を行う第３のステップと、前記複数の署名生成装置のうち所定の署名生成装置により、前記第３のステップによる演算結果の総和を階層ごとに算出し、階層ごとの算出結果を乗算して、アグリゲート署名を生成する第４のステップと、をコンピュータに実行させるためのアグリゲート署名生成プログラムを提案している。
【００４２】
この発明によれば、アグリゲート署名生成プログラムをコンピュータに実行させることで、自身のメッセージのハッシュに対して自身の秘密鍵でべき乗演算を行って、署名を生成する。そして、生成した署名に対して、自身が属する階層ごとに異なる所定値でべき乗演算を行う。そして、べき乗演算の演算結果の総和を階層ごとに算出し、階層ごとの算出結果を乗算して、アグリゲート署名を生成する。
【００４３】
このため、アグリゲート署名は、メッセージのハッシュに対して、各自の秘密鍵と、所定値と、でべき乗演算が行われた構造で表される。そして、この所定値は、自身が属する階層ごとに異なる値である。したがって、アグリゲート署名を表す数式の指数の構造により、署名生成装置がどの階層に属するのかを表現できる。よって、各署名者が互いに異なる署名生成装置を用いることで、署名者がどの階層に属するのかを表現できる。
【００４４】
また、アグリゲート署名は、各署名者の署名と同じ巡回群にあるため、署名者の人数にかかわらず、一定のサイズに納めることができる。
【００４５】
（８）本発明は、（７）のアグリゲート署名生成プログラムについて、前記所定値は、自身が属する階層と、最下位層と、の階層数の差だけ特定値をべき乗演算した値であることを特徴とするアグリゲート署名生成プログラムを提案している。
【００４６】
この発明によれば、アグリゲート署名生成プログラムをコンピュータに実行させることで、所定値は、自身が属する階層と、最下位層と、の階層数の差だけ特定値をべき乗演算した値で表される。このため、アグリゲート署名を表す数式の指数のうち、特定値により、署名生成装置がどの階層に属するのかを表現できる。
【００４７】
（９）本発明は、（７）または（８）のアグリゲート署名生成プログラムについて、前記アグリゲート署名を検証する署名検証装置がさらに配置された前記アグリゲート署名生成システムにおけるアグリゲート署名生成プログラムであって、前記署名検証装置により、前記所定のパラメータ、前記公開鍵、前記メッセージのハッシュ、および前記アグリゲート署名を入力として、ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ署名の演算を行って、前記アグリゲート署名の正当性を検証する第５のステップを備えることを特徴とするアグリゲート署名生成プログラムを提案している。
【００４８】
この発明によれば、アグリゲート署名生成プログラムをコンピュータに実行させることで、所定のパラメータ、公開鍵、メッセージのハッシュ、およびアグリゲート署名を入力として、ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ署名の演算を行って、アグリゲート署名の正当性を検証する。このため、アグリゲート署名の正当性を検証できる。
【発明の効果】
【００４９】
この発明によれば、アグリゲート署名は、メッセージのハッシュに対して、各自の秘密鍵と、所定値と、でべき乗演算が行われた構造で表される。そして、この所定値は、自身が属する階層ごとに異なる値である。したがって、アグリゲート署名を表す数式の指数の構造により、署名生成装置がどの階層に属するのかを表現できる。よって、各署名者が互いに異なる署名生成装置を用いることで、署名者がどの階層に属するのかを表現できる。
【発明を実施するための最良の形態】
【００５０】
以下、本発明の実施形態について、図面を用いて、詳細に説明する。
なお、本実施形態における構成要素は適宜、既存の構成要素等との置き換えが可能であり、また、他の既存の構成要素との組合せを含む様々なバリエーションが可能である。したがって、本実施形態の記載をもって、特許請求の範囲に記載された発明の内容を限定するものではない。
【００５１】
アグリゲート署名システムは、署名を行う署名者ごとに設けられた複数のノードと、複数のノードで生成された署名を検証する署名検証装置と、を備える。各ノードは、署名鍵（秘密鍵）および検証鍵（公開鍵）を格納する鍵格納部と、署名を生成する署名生成部と、署名生成部により生成された署名に対して自身が属する階層ごとに異なる所定値でべき乗演算を行うべき乗演算部と、を備える。また、これらノードのうち所定のノードは、アグリゲート署名を生成するアグリゲート署名生成部を備える。署名検証装置は、アグリゲート署名の正当性を検証するアグリゲート署名検証部を備える。
【００５２】
図１に示すように、複数のノードは、ｄ層（ｄは、４≦ｄを満たす整数）のヒエラルキーを形成して配置される。最上位層である第１層には、ｐ台（ｐは、１≦ｐを満たす整数）のノードが配置され、第（ｄ−２）層には、ｏ台（ｏは、１≦ｏを満たす整数）のノードが配置され、第（ｄ−１）層には、ｎ台（ｎは、１≦ｎを満たす整数）のノードが配置され、最下位層である第ｄ層には、ｍ台（ｍは、１≦ｍを満たす整数）のノードが配置される。なお、本実施形態では、各署名者は、各自のノードを用いて互いに異なるメッセージに対して署名を行う。
【００５３】
＜ｄ階層のヒエラルキーが形成されている場合におけるアグリゲート署名の生成＞
以下に、図１のノードによりアグリゲート署名を生成する場合について説明する。
【００５４】
ここで、署名鍵（秘密鍵）および検証鍵（公開鍵）のペアは、第１層のノード（１−ｌ）のものを数７のように、第（ｄ−２）層のノード（（ｄ−２）―ｋ）のものを数８のように、第（ｄ−１）層のノード（（ｄ−１）―ｊ）のものを数９のように、第ｄ層のものを数１０のように表す。なお、数７において、ｌは、１≦ｌ≦ｐを満たす整数とし、数８において、ｋは、１≦ｋ≦ｏを満たす整数とし、数９において、ｊは、１≦ｊ≦ｎを満たす整数とし、数１０において、ｉは、１≦ｉ≦ｍを満たす整数とする。
【００５５】
【数７】
2010087590.tif 000009
【００５６】
【数８】
2010087590.tif 000010
【００５７】
【数９】
2010087590.tif 000011
【００５８】
【数１０】
2010087590.tif 000012
【００５９】
まず、第ｄ層の各ノード（ｄ−ｉ）は、数１１に示すように、ＧＤＨ署名を行って、メッセージｍｄ−ｉのハッシュｈｄ−ｉに対して自身の署名鍵ｘｄ−ｉでべき乗演算を行って、第ｄ層に属する自身の署名σｄ−ｉとする。
【００６０】
【数１１】
2010087590.tif 000013
【００６１】
次に、第（ｄ−１）層の各ノード（（ｄ−１）−ｊ）は、数１２に示すように、ＧＤＨ署名を行って、メッセージｍ（ｄ−１）―ｊのハッシュｈ（ｄ−１）―ｊに対して自身の署名鍵ｘ（ｄ−１）−ｊでべき乗演算を行った後に、さらに第１の値でべき乗演算を行って、第（ｄ−１）層に属する自身の署名σ（ｄ−１）−ｊとする。ここで、第１の値は、第（ｄ−１）層と、最下位層である第ｄ層と、の階層数の差に等しい「１」回だけ「２」をべき乗した値である「２（＝２１）」とする。
【００６２】
【数１２】
2010087590.tif 000014
【００６３】
次に、第（ｄ−２）層の各ノード（（ｄ−２）−ｋ）は、数１３に示すように、ＧＤＨ署名を行って、メッセージｍ（ｄ−２）−ｋのハッシュｈ（ｄ−２）−ｋに対して自身の署名鍵ｘ（ｄ−２）−ｋでべき乗演算を行った後に、さらに第２の値でべき乗演算を行って、第（ｄ−２）層に属する自身の署名σ（ｄ−２）−ｋとする。ここで、第２の値は、第（ｄ−２）層と、最下位層である第ｄ層と、の階層数の差に等しい「２」回だけ「２」をべき乗した値である「４（＝２２）」とする。
【００６４】
【数１３】
2010087590.tif 000015
【００６５】
第（ｄ−２）層よりも上位の階層に属する各ノードについても、上述の数１２、１３と同様に、署名を順次生成する。
【００６６】
例えば、第（ｄ−２）層よりも上位の階層である第１層の各ノード（１−ｌ）は、数１４に示すように、ＧＤＨ署名を行って、メッセージｍ１−ｌのハッシュｈ１−ｌに対して自身の署名鍵ｘ１−ｌでべき乗演算を行った後に、さらに所定の値でべき乗演算を行って、第１層に属する自身の署名σ１−ｌとする。ここで、所定の値は、第１層と、最下位層である第ｄ層と、の階層数の差に等しい「ｄ−１」回だけ「２」をべき乗した値である「２ｄ−１」とする。
【００６７】
【数１４】
2010087590.tif 000016
【００６８】
次に、全ての階層の全てのノードが自身の署名を生成した後、最後に自身の署名を生成したノードといった所定のノードは、数１５に示すように、全ての階層の全てのノードの署名を集め、これらを乗算したものをアグリゲート署名σとする。
【００６９】
【数１５】
2010087590.tif 000017
【００７０】
次に、（ｇ，ｈ，σ）を公開する。
【００７１】
＜ｄ階層のヒエラルキーが形成されている場合に生成されたアグリゲート署名の検証＞
以下に、図１のノードで生成されたアグリゲート署名を検証する場合について説明する。
【００７２】
まず、署名検証装置は、数１６、１７に示すように、（ｇ、・・・ｖｆ−ｑ、・・・ｈｆ−ｑ、・・・σ）を関数ｅ（Ｐ，Ｑ）に入力して、ＧＤＨ署名の演算を行う。ここで、ｖｆ−ｑは、第ｆ層（ｆは、１≦ｆ≦ｄを満たす整数）のノード（ｆ−ｑ）の検証鍵を示し、ｈｆ−ｑは、第ｆ層（ｆは、１≦ｆ≦ｄを満たす整数）のノード（ｆ−ｑ）におけるメッセージｍｆ−ｑのハッシュを示す。また、ｑは、１≦ｑ＜ｆを満たす整数とする。
【００７３】
【数１６】
2010087590.tif 000018
【００７４】
【数１７】
2010087590.tif 000019
【００７５】
数１６の値と数１７の値とが一致するか否かを検証して、アグリゲート署名σを検証する。具体的には、数１６の値と数１７の値とが一致すれば、アグリゲート署名σが正しいと判定し、数１６の値と数１７の値とが一致しなければアグリゲート署名σが正しくないと判定する。
【００７６】
以上によれば、数１５に示すように、メッセージｍｆ−ｑのハッシュｈｆ−ｑに対して所定値でべき乗演算を行うことで、アグリゲート署名σを表すことができる。ここで、この所定値は、ノードが属する階層ごとに異なる値で各自の署名鍵を乗算したもので表される。
【００７７】
そして、このノードが属する階層ごとに異なる値は、第ｄ層では「１」であり、第（ｄ−１）層では「２」であり、第（ｄ−２）層では「４」であり、第１層では「２ｄ−１」となる。このため、署名鍵の倍数により、ノードの属する階層を区別できる。したがって、アグリゲート署名σを表す数式の指数の構造により、各階層に属するノードを区別できるので、署名者がどの階層に属するのかを表現できる。
【００７８】
また、アグリゲート署名σは、各署名者の署名と同じ巡回群にあるため、署名者の人数にかかわらず、一定のサイズに納めることができる。
【００７９】
なお、本発明のノードおよび署名検証装置のそれぞれの処理をコンピュータ読み取り可能な記録媒体に記憶し、これら記録媒体に記録されたプログラムをノードおよび署名検証装置（いずれもコンピュータシステム）に読み込ませ、実行することによって、本発明を実現できる。
【００８０】
また、「コンピュータシステム」は、ＷＷＷ（Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ）システムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、上述のプログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
【００８１】
また、上述のプログラムは、上述の機能の一部を実現するためのものであってもよい。さらに、上述の機能をコンピュータシステムにすでに記録されているプログラムとの組合せで実現できるもの、いわゆる差分ファイル（差分プログラム）であってもよい。
【００８２】
以上、この発明の実施形態につき、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【図面の簡単な説明】
【００８３】
【図１】本発明の実施形態に係る複数のノードの配置を示す図である。
【符号の説明】
【００８４】
ｘ１−ｌ、ｘ（ｄ−１）―ｊ、ｘ（ｄ−２）−ｋ、ｘｄ−ｉ・・・署名鍵（秘密鍵）
ｖ１−ｌ、ｖ（ｄ−１）―ｊ、ｖ（ｄ−２）−ｋ、ｖｄ−ｉ・・・検証鍵（公開鍵）
σ・・・アグリゲート署名
【図１】
2010087590.tif 000020