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