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