(57)【要約】【課題】元データにデータを追加する場合に、署名に要する処理時間を短縮できる多段署名検証システム、電子署名付与装置、データ追加装置及び電子署名検出装置を提供する。【解決手段】多段署名検証システムは、あらかじめ生成された元データ、取得した落とし戸ハッシュ値、落とし戸付ハッシュ値を生成したデータ追加装置を特定する識別情報に電子署名を付与する電子署名付与装置と、新たな生成データ及び識別情報を元データに追加データとして付与し、秘密情報を利用し、追加データ及び落とし戸ハッシュ値と共に落とし戸ハッシュ関数に入力したときの出力が落とし戸付ハッシュ値と等しくなる確定値を計算するデータ追加装置と、落とし戸付ハッシュ値により、追加データの正当性を検証する電子署名検証装置とを備える。【選択図】図１
2005210277.tif 000002
【特許請求の範囲】
【請求項１】
署名が付与された元データに、新たに追加データを付与し、前記元データと前記追加データの正当性を検証する多段署名検証システムであって、
あらかじめ生成された元データと、取得した落とし戸付ハッシュ値と、該落とし戸付ハッシュ値を生成したデータ追加装置を特定する識別情報とに電子署名を付与する電子署名付与手段を有する電子署名付与装置と、
新たな生成データ及び前記識別情報を前記元データに追加データとして付与するデータ追加手段と、秘密情報を利用し、前記追加データ及び前記落とし戸ハッシュ値と共に落とし戸ハッシュ関数に入力したときの出力が前記落とし戸付ハッシュ値と等しくなる確定値を計算する確定値計算手段とを有するデータ追加装置と、
前記追加データと前記確定値とに基づいて、前記落とし戸付ハッシュ値を計算する落とし戸付ハッシュ値計算手段と、該落とし戸付ハッシュ値計算手段によって計算された落とし戸付ハッシュ値により、前記追加データの正当性を検証する検証手段とを有する電子署名検証装置と
を備えることを特徴とする多段署名検証システム。
【請求項２】
前記識別情報は、前記落とし戸ハッシュ値を生成する際に生成されたパラメータであることを特徴とする請求項１に記載の多段署名検証システム。
【請求項３】
電子署名を付与する電子署名付与装置であって、
落とし戸付ハッシュ値と、該落とし戸付ハッシュ値を生成したデータ追加装置を特定する識別情報とを取得する取得手段と、
あらかじめ生成された元データと、前記落とし戸付ハッシュ値と、前記識別情報とに電子署名を付与する電子署名付与手段と、
前記電子署名を付与された前記元データ及び前記識別情報を前記データ追加装置へ出力する出力手段と
を備えることを特徴とする電子署名付与装置。
【請求項４】
前記出力手段は、更に前記落とし戸付ハッシュ値を出力することを特徴とする請求項３に記載の電子署名付与装置。
【請求項５】
ｎを１以上の自然数、ｋを１以上ｎ以下の自然数とし、新たなデータを付与するｎ個の前記データ追加装置を備える多段署名検証システムにおいて用いられる前記電子署名付与装置であって、
前記取得手段は、第１番目〜第ｋ番目のデータ追加装置から、それぞれ第１番目〜第ｋ番目の前記落とし戸付ハッシュ値と前記識別情報とを取得し、
前記出力手段は、第１番目〜第ｋ番目の前記識別情報を第１番目のデータ追加装置へ出力する
ことを特徴とする請求項３又は４に記載の電子署名付与装置。
【請求項６】
前記データ追加装置がデータを追加する場所を指定するプレースホルダを生成する生成手段を更に備えることを特徴とする請求項３〜５のいずれか１項に記載の電子署名付与装置。
【請求項７】
電子署名付与装置において生成された元データに、新たなデータを付与するデータ追加装置であって、
落とし戸付ハッシュ値を生成する落とし戸付ハッシュ値生成手段と、
前記落とし戸付ハッシュ値と、前記落とし戸付ハッシュ値を生成したデータ追加装置を特定する識別情報とを出力する第１の出力手段と、
新たな生成データ及び前記識別情報を前記元データに追加データとして付与するデータ追加手段と、
秘密情報を利用し、前記追加データ及び前記落とし戸付ハッシュ値と共に落とし戸ハッシュ関数に入力したときの出力が前記落とし戸付ハッシュ値と等しくなる確定値を計算する確定値計算手段と、
前記追加データと前記確定値とを出力する第２の出力手段と
を備えることを特徴とするデータ追加装置。
【請求項８】
前記第２の出力手段は、更に前記落とし戸付ハッシュ値を出力することを特徴とする請求項７に記載のデータ追加装置。
【請求項９】
ｎを１以上の自然数、ｉを１以上ｎ以下の自然数とし、電子署名付与装置において生成された元データに、新たなデータを付与するｎ個の前記データ追加装置の中で、第ｉ番目に新たなデータを付与する前記データ追加装置であって、
前記第１の出力手段は、ｉが１である場合、前記落とし戸付ハッシュ値と前記識別情報とを前記電子署名付与装置へ出力し、ｉが２以上である場合、前記落とし戸付ハッシュ値と前記識別情報とを第ｉ−１番目のデータ追加装置へ出力し、
前記第２の出力手段は、ｉがｎより小さい場合、前記追加データと前記確定値とを第ｉ＋１番目のデータ追加装置へ出力し、ｉがｎである場合、前記追加データと前記確定値とを前記元データ及び前記追加データの正当性を検証する電子署名検証装置へ出力する
ことを特徴とする請求項７又は８に記載のデータ追加装置。
【請求項１０】
ｍを１以上の自然数とし、第ｉ＋１番目〜第ｉ＋ｍ番目のデータ追加装置から、それぞれ前記落とし戸付ハッシュ値と前記識別情報とを取得する取得手段とを更に備え、
前記追加データには、前記生成データ、第ｉ＋１番目〜第ｉ＋ｍ番目の識別情報が含まれることを特徴とする請求項９に記載のデータ追加装置。
【請求項１１】
データを追加する場所を指定するプレースホルダを生成する生成手段を更に備えることを特徴とする請求項７〜１０のいずれか１項に記載のデータ追加装置。
【請求項１２】
電子署名が付与された元データと、該元データに新たに付与された追加データとの正当性を検証する電子署名検証装置であって、
前記追加データと、前記追加データ及び落とし戸付ハッシュ値と共に落とし戸ハッシュ関数に入力したときの出力が前記落とし戸付ハッシュ値と等しくなる確定値とをデータ追加装置から取得するデータ取得手段と、
前記追加データと前記確定値とに基づいて、前記落とし戸付ハッシュ値を計算する落とし戸付ハッシュ値計算手段と、
該落とし戸付ハッシュ値計算手段によって計算された落とし戸付ハッシュ値により、前記追加データの正当性を検証する検証手段と
を備えることを特徴とする電子署名検証装置。
【請求項１３】
ｎを１以上の自然数とし、ｎ個の追加データを含む取得データを取得する前記電子署名検証装置であって、前記追加データに落とし戸付ハッシュ値が含まれる場合、
前記落とし戸付ハッシュ値計算手段は、第１番目〜第ｎ番目の追加データと、第１番目〜第ｎ番目の確定値とに基づいて、第１番目〜第ｎ番目の前記落とし戸付ハッシュ値を計算し、
前記検証手段は、前記取得したデータに含まれる落とし戸付ハッシュ値と、前記落とし戸付ハッシュ値計算手段によって計算された落とし戸付ハッシュ値とを比較することにより、前記追加データの正当性を検証する
ことを特徴とする請求項１２に記載の電子署名検証装置。
【請求項１４】
ｎを１以上の自然数とし、ｎ個の追加データを含む取得データを取得する前記電子署名検証装置であって、前記追加データに落とし戸付ハッシュ値が含まれない場合、
前記落とし戸付ハッシュ値計算手段は、第ｎ番目の追加データと、第ｎ番目の確定値とに基づいて、第ｎ番目の前記落とし戸付ハッシュ値を計算し、第ｎ−１番目の追加データ、前記第ｎ番目の落とし戸付ハッシュ値、第ｎ−１番目の確定値から第ｎ−１番目の落とし戸付ハッシュ値を計算するステップを第１の落とし戸付ハッシュ値を算出するまで再帰的に繰り返し、
前記検証手段は、前記電子署名を用いて、前記第１番目〜第ｎ番目の落とし戸付ハッシュ値の検証を行うことにより、前記追加データの正当性を検証する
ことを特徴とする請求項１２に記載の電子署名検証装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、多段署名検証システム、電子署名付与装置、データ追加装置及び電子署名検証装置に関する。
【背景技術】
【０００２】
従来、一つ以上の中間ノードが、初期ノードであるデータの出力者と最終ノードであるデータの入力者との間に存在し、データの追加や転送を行うマルチホップの通信がある。例えば、ユーザのコンテンツプロバイダに対するリクエストに、中間ノードである課金情報生成者がリクエスト対象のコンテンツや、リクエストの宛先に応じた課金情報を付与する場合を考える。この場合、コンテンツプロバイダや課金代行サーバは、付与された課金情報を元にユーザに対して課金を行う。ここで、課金者がユーザを信頼できるのであれば課金は滞りなく行われるが、もしユーザが信頼できない場合、課金を行う根拠として、リクエストが確かにユーザにより生成されたというメッセージの出自を明確にする必要がある。
【０００３】
メッセージの出自を明確にするには、各端末間においてＩＰＳｅｃやＳＳＬなどの技術を用いてセキュアな通信路を確立することで相互認証を行うか、メッセージに生成者の電子署名を付与する方法が考えられる。前者は認証を行う際、各端末同士が同時にオンラインでなければならないのに対し、後者はコンテンツに署名を付与する時刻と、メッセージの入力者が署名を検証する時刻とが異なっても良いため、検証処理を任意の時刻に行うことが可能であり、例えば負荷を分散して行うことができるといった利点がある。
【０００４】
上記の例において電子署名を用いた場合は、ユーザは生成したリクエストに対して署名を付与し、同様に課金情報生成者は生成した課金情報に署名を付与することで、課金側はそれらの端末の信頼性に係わらず課金を行うことができ、それに対してユーザがリクエストの事後否認を行うことはできない。このような多段に追加されるデータに対して署名・検証を行う技術がいくつか考案されている。
【０００５】
例えば、第１番目の署名者が署名を付与し出力した元データに、第２番目の署名者がさらにデータを追加し、追加データに対して署名を付与し、同様にして第ｉ−１番目の署名者からデータを入力した第ｉ番目の署名者は、データを追加し、追加データに署名を付与した後で、第ｉ＋１番目の署名者に出力するという多段署名方式は開示されている（例えば、特許文献１）。こうして多段に追加されたデータに対する署名を、検証者は検証することができる。以下、第ｉ番目の署名者についてこの署名方式の説明を行う。
【０００６】
ｉ番目の署名者は入力データにデータを追加した場合、追加後のデータと追加前のデータの差分データｍiをとる。署名は、このｍiのハッシュ値と署名者のＩＤiを結合した結合データとｉ−１番目の確定値とに対して逆演算可能な演算を行い、得られたデータを秘密鍵で暗号化することで生成される。ｉ＋１番目の署名者には、ｉ番目までの差分データ、ＩＤ、ｉ番目の確定値が出力される。ｎ番目の署名者からデータを入力した検証者は、公開鍵を用いてｎ番目の確定値を復号し、得られた値に、逆演算ｆ-1を施すことで、ｎ−１番目の確定値を導出し、これを繰り返すことで１番目の署名者が追加したデータｍ1とＩＤ1との結合データを得る。これが、元の入力データが有するｍ1とＩＤ1との結合データに等しければ、入力データの正当性が保証されることになる。
【０００７】
又、他の多段署名方式として、データＭに対して１番目の署名者は生成したデータＭ1に対して、署名δ1を生成し、δ＝δ1をＭ1に付与された署名とする方式が開示されている（例えば、非特許文献１）。（Ｍ1，δ）を取得した２番目の署名者は、生成したデータＭ2を生成後、Ｍ2に対して、署名δ2を生成する。その後、δ＝δ1・δ2とし、このδをＭ1，Ｍ2に関する署名とする。同様に、（Ｍ1，Ｍ2，Ｍ3，...，Ｍn-1，δ）を取得したｎ番目の署名者は、生成したデータＭnを生成後、Ｍnに対して、署名δnを生成する。その後、
【数１】
2005210277.tif 000003
とし、このδをＭ1，Ｍ2，...，Ｍnに関する署名とする。署名側では、各署名対象と各署名者の公開鍵から得られた値を全て掛け合わせ、確定値と比較することで検証を行う。
【特許文献１】特開２００２−４０９３５号公報
【非特許文献１】D. Boneh, C. Gentry, B. Lynn, and H. Shacham, “Aggregate and verifiably encrypted signatures from bilinear map” in Proc. of Eurocrypt 2003, volume 2656 of LNCS, pages 416-432. Springer-Verlag 2003.
【発明の開示】
【発明が解決しようとする課題】
【０００８】
特許文献１では、署名者は入力したデータに付与された確定値を用いて追加データに署名を付与する方法をとっている。こうすることで、もし、ある追加データとそれに付与された確定値が消去された場合は、検証者側で検証することにより、追加データが削除されたことを検出することができる。
【０００９】
又、非特許文献１では、データに付与された署名を一つに結合することで、署名長を短縮することができる。
【００１０】
しかしながら、電子署名の付与は一般に計算時間がかかることが知られており、これらの多段署名方式は、電子署名の付与が多段に行われることで、オーバーヘッドが大きくなる可能性があった。
【００１１】
そこで、本発明は、上記の課題に鑑み、元データにデータを追加する場合に、署名に要する処理時間を短縮できる多段署名検証システム、電子署名付与装置、データ追加装置及び電子署名検証装置を提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記目的を達成するため、本発明の第１の特徴は、署名が付与された元データに、新たに追加データを付与し、元データと追加データの正当性を検証する多段署名検証システムであって、（イ）署名が付与された元データに、新たに追加データを付与し、元データと追加データの正当性を検証する多段署名検証システムであって、あらかじめ生成された元データと、取得した落とし戸付ハッシュ値と、落とし戸付ハッシュ値を生成したデータ追加装置を特定する識別情報とに電子署名を付与する電子署名付与手段を有する電子署名付与装置と、（ロ）新たな生成データ及び識別情報を元データに追加データとして付与するデータ追加手段と、秘密情報を利用し、追加データ及び落とし戸ハッシュ値と共に落とし戸ハッシュ関数に入力したときの出力が落とし戸付ハッシュ値と等しくなる確定値を計算する確定値計算手段とを有するデータ追加装置と、（ハ）追加データと確定値とに基づいて、落とし戸付ハッシュ値を計算する落とし戸付ハッシュ値計算手段と、落とし戸付ハッシュ値計算手段によって計算された落とし戸付ハッシュ値により、追加データの正当性を検証する検証手段とを有する電子署名検証装置とを備える多段署名検証システムであることを要旨とする。
【００１３】
第１の特徴に係る多段署名検証システムによると、データ追加装置は署名が付与された元データにデータを追加する場合に、追加データに対して電子署名を付与する必要がなく、署名に要する計算時間を短縮することができる。
【００１４】
又、第１の特徴に係る多段署名検証システムに置いて、識別情報は、落とし戸ハッシュ値を生成する際に生成されたパラメータであってもよい。この多段署名検証システムによると、電子署名検証装置がパラメータを用いて落とし戸付ハッシュ値を計算することができる。
【００１５】
本発明の第２の特徴は、電子署名を付与する電子署名付与装置であって、（イ）落とし戸付ハッシュ値と、落とし戸付ハッシュ値を生成したデータ追加装置を特定する識別情報とを取得する取得手段と、（ロ）あらかじめ生成された元データと、落とし戸付ハッシュ値と、識別情報とに電子署名を付与する電子署名付与手段と、（ハ）電子署名を付与された元データ及び識別情報をデータ追加装置へ出力する出力手段とを備える電子署名付与装置であることを要旨とする。
【００１６】
第２の特徴に係る電子署名付与装置によると、元データ、落とし戸ハッシュ値と、識別情報とに電子署名を付与することができる。
【００１７】
又、第２の特徴に係る電子署名付与装置の出力手段は、更に前記落とし戸付ハッシュ値を出力してもよい。この電子署名付与装置によると、元データ及び識別情報だけでなく、落とし戸付ハッシュ値を出力することができる。
【００１８】
又、第２の特徴に係る電子署名付与装置は、ｎを１以上の自然数、ｋを１以上ｎ以下の自然数とし、新たなデータを付与するｎ個のデータ追加装置を備える多段署名検証システムにおいて用いられ、取得手段は、第１番目〜第ｋ番目のデータ追加装置から、それぞれ第１番目〜第ｋ番目の落とし戸付ハッシュ値と識別情報とを取得し、出力手段は、第１番目〜第ｋ番目の識別情報を第１番目のデータ追加装置へ出力してもよい。この電子署名付与装置によると、複数のデータ追加装置の識別情報（パラメータ）に電子署名を付与することができる。
【００１９】
又、第２の特徴に係る電子署名付与装置は、データ追加装置がデータを追加する場所を指定するプレースホルダを生成する生成手段を更に備えてもよい。この電子署名付与装置によると、追加データを挿入する場所を指定することができる。
【００２０】
本発明の第３の特徴は、電子署名付与装置において生成された元データに、新たなデータを付与するデータ追加装置であって、（イ）落とし戸付ハッシュ値を生成する落とし戸付ハッシュ値生成手段と、（ロ）落とし戸付ハッシュ値と、落とし戸付ハッシュ値を生成したデータ追加装置を特定する識別情報とを出力する第１の出力手段と、（ハ）新たな生成データ及び識別情報を元データに追加データとして付与するデータ追加手段と、（ニ）秘密情報を利用し、追加データ及び落とし戸ハッシュ値と共に落とし戸ハッシュ関数に入力したときの出力が落とし戸付ハッシュ値と等しくなる確定値を計算する確定値計算手段と、（ホ）追加データと確定値とを出力する第２の出力手段とを備えるデータ追加装置であることを要旨とする。
【００２１】
第３の特徴に係るデータ追加装置によると、電子署名を付与する代わりに、確定値を付与することで署名に要する処理時間を短縮し、確定値により生成データの正当性を保障することができる。
【００２２】
又、第３の特徴に係るデータ追加装置の第２の出力手段は、更に前記落とし戸付ハッシュ値を出力してもよい。このデータ追加装置によると、追加データ及び識別情報だけでなく、落とし戸付ハッシュ値を出力することができる。この落とし戸ハッシュ値は、追加データに含まれる情報として出力されてもよい。
【００２３】
又、第３の特徴に係るデータ追加装置は、ｎを１以上の自然数、ｉを１以上ｎ以下の自然数とし、電子署名付与装置において生成された元データに、新たなデータを付与するｎ個のデータ追加装置の中で、第ｉ番目に新たなデータを付与するデータ追加装置であって、第１の出力手段は、ｉが１である場合、落とし戸付ハッシュ値と識別情報とを電子署名付与装置へ出力し、ｉが２以上である場合、落とし戸付ハッシュ値と識別情報とを第ｉ−１番目のデータ追加装置へ出力し、第２の出力手段は、ｉがｎより小さい場合、追加データと確定値とを第ｉ＋１番目のデータ追加装置へ出力し、ｉがｎである場合、追加データと確定値とを元データ及び追加データの正当性を検証する電子署名検証装置へ出力してもよい。このデータ追加装置によると、落とし戸付ハッシュ値と識別情報とを電子署名付与装置、あるいは、第ｉ−１番目のデータ追加装置へ出力することができ、追加データと確定値とを第ｉ＋１番目のデータ追加装置、あるいは、電子署名検証装置へ出力することができる。
【００２４】
又、第３の特徴に係るデータ追加装置は、ｍを１以上の自然数とし、第ｉ＋１番目〜第ｉ＋ｍ番目のデータ追加装置から、それぞれ落とし戸付ハッシュ値と識別情報とを取得する取得手段とを更に備え、追加データには、生成データ、第ｉ＋１番目〜第ｉ＋ｍ番目の識別情報が含まれてもよい。このデータ追加装置によると、第ｉ＋１番目〜第ｉ＋ｍ番目の複数のデータ追加装置の識別情報を取得したデータに追加し、共に付与する確定値により正当性を保障することができる。
【００２５】
又、第３の特徴に係るデータ追加装置は、データを追加する場所を指定するプレースホルダを生成する生成手段を更に備えてもよい。このデータ追加装置によると、追加データを挿入する場所を指定することができる。
【００２６】
本発明の第４の特徴は、電子署名が付与された元データと、元データに新たに付与された追加データとの正当性を検証する電子署名検証装置であって、（イ）追加データと、追加データ及び落とし戸付ハッシュ値と共に落とし戸ハッシュ関数に入力したときの出力が落とし戸付ハッシュ値と等しくなる確定値とをデータ追加装置から取得するデータ取得手段と、（ロ）追加データと確定値とに基づいて、落とし戸付ハッシュ値を計算する落とし戸付ハッシュ値計算手段と、（ハ）落とし戸付ハッシュ値計算手段によって計算された落とし戸付ハッシュ値により、追加データの正当性を検証する検証手段とを備える電子署名検証装置であることを要旨とする。
【００２７】
第４の特徴に係る電子署名検証装置によると、電子署名、落とし戸付ハッシュ値により、元データ及び追加データの正当性を検証することができる。
【００２８】
第４の特徴に係る電子署名検証装置は、ｎを１以上の自然数とし、ｎ個の追加データを含む取得データを取得する電子署名検証装置であって、追加データに落とし戸付ハッシュ値が含まれる場合、落とし戸付ハッシュ値計算手段は、第１番目〜第ｎ番目の追加データと、第１番目〜第ｎ番目の確定値とに基づいて、第１番目〜第ｎ番目の落とし戸付ハッシュ値を計算し、検証手段は、取得したデータに含まれる落とし戸付ハッシュ値と、落とし戸付ハッシュ値計算手段によって計算された落とし戸付ハッシュ値とを比較することにより、追加データの正当性を検証してもよい。この電子署名検証装置によると、電子署名により、元データの正当性を検証し、取得データに含まれる落とし戸付ハッシュ値と計算された落とし戸付ハッシュ値とを比較することにより、追加データの正当性を検証することができる。
【００２９】
又、第４の特徴に係る電子署名検証装置は、ｎを１以上の自然数とし、ｎ個の追加データを含む取得データを取得する電子署名検証装置であって、追加データに落とし戸付ハッシュ値が含まれない場合、落とし戸付ハッシュ値計算手段は、第ｎ番目の追加データと、第ｎ番目の確定値とに基づいて、第ｎ番目の落とし戸付ハッシュ値を計算し、第ｎ−１番目の追加データ、第ｎ番目の落とし戸付ハッシュ値、第ｎ−１番目の確定値から第ｎ−１番目の落とし戸付ハッシュ値を計算するステップを第１の落とし戸付ハッシュ値を算出するまで再帰的に繰り返し、検証手段は、電子署名を用いて、第１番目〜第ｎ番目の落とし戸付ハッシュ値の検証を行うことにより、追加データの正当性を検証してもよい。この電子署名検証装置によると、複数のデータ追加装置の生成データ（ｎ）と確定値（ｎ）により、各データ追加装置における落とし戸付ハッシュ値（１）〜落とし戸付ハッシュ値（ｎ）を導出することが可能であり、付与された電子署名を検証することにより、全ての追加データの正当性を検証することができる。
【発明の効果】
【００３０】
本発明によると、元データにデータを追加する場合に、署名に要する処理時間を短縮できる多段署名検証システム、電子署名付与装置、データ追加装置及び電子署名検証装置を提供することができる。 
【発明を実施するための最良の形態】
【００３１】
次に、図面を参照して、本発明の実施形態を説明する。以下の図面の記載において、同一又は類似の部分には、同一又は類似の符号を付している。ただし、図面は模式的なものであることに留意すべきである。
【００３２】
まず、本実施形態において用いる落とし戸付ハッシュ関数、落とし戸付ハッシュ値について説明する。以下、ｙをハッシュ鍵、ｘを秘密鍵とし、前者は公開情報、後者は秘密情報とする。又、表１に落とし戸付ハッシュ関数に関わる値を示す。
【表１】
2005210277.tif 000004
【００３３】
落とし戸付ハッシュ値は、ｙを伴う落とし戸付ハッシュ関数ｈyに対する２数の入力により、ｈy（ｍ，ｒ）と表され、以下の性質を満たす。
【００３４】
１）ｙとｈy（ｍ’，ｒ’）のみが与えられている場合は、ｈy（ｍ，ｒ）＝ｈy（ｍ’，ｒ’）となるような、ｍ，ｒの組を導出するのが非常に困難であること。
【００３５】
２）ｘが与えられている場合は、ｘ，ｍ’，ｒ’を用いて、任意のｍに対してｈy（ｍ’，ｒ’）＝ｈy（ｍ，ｒ）となるようなｒを導出することができること。
【００３６】
このように、ある秘密情報（ここでは秘密鍵ｘ）を用いることで、意図的に衝突を作り出すことができるハッシュ関数を総称して、落とし戸付ハッシュ関数と呼ぶ。落とし戸付ハッシュ関数は、最低２数の入力を伴う。
【００３７】
次に、落とし戸付ハッシュ関数に関わる過程を、以下の３過程に分けて説明する。
【００３８】
１）落とし戸付ハッシュ値の導出
（ア）表１に示すような、ｑ，ｋ，ｐ，ｍ’，ｒ’，ｘを選択し、ｇ，ｙを導出する。
【００３９】
（イ）ｈy＝ｈy（ｍ’，ｒ’）＝ｇm’ｙr’（mod ｐ）とし、これを落とし戸付ハッシュ値とする。
【００４０】
２）衝突の検出（ｈy，ｍ’，ｒ’，ｑ，ｘが与えられている。）
（ア）任意のｍを選択する。
【００４１】
（イ）ｍ＋ｘｒ＝ｍ’＋ｘｒ’（mod ｐ）となるｒを導出する。このｒはｈy（ｍ’，ｒ’）＝ｈy（ｍ，ｒ）を満たす。
【００４２】
３）落とし戸付ハッシュ値の検証（ｇ，ｐ，ｙ，ｍ，ｒ，ｈy（ｍ’，ｒ’）が与えられている。）
（ア）ｈy（ｍ，ｒ）＝ｇmｙr（mod ｐ）＝ｈy（ｍ’，ｒ’）となるか検証する。
【００４３】
以下、上記に例を挙げた落とし戸付ハッシュ関数を用い、本発明の実施形態について説明する。尚、本発明は、上記に例を挙げた落とし戸付ハッシュ関数に限らず、落とし戸付ハッシュ関数の性質を有するどのような関数を用いても実現可能である。
【００４４】
（第１の実施形態）
第１の実施形態に係る多段署名認証システムは、図１に示すように、電子署名付与装置１０、一つのデータ追加装置２０、及び電子署名検証装置３０とを備える。電子署名付与装置１０、データ追加装置２０、電子署名検証装置３０の間でデータの入出力を行う際は、それぞれの装置間で直接入出力を行っても良く、通信ネットワークを介して入出力を行っても良い。ここで、「通信ネットワーク」とは、インターネット、移動電話網、公衆電話網などの通信網を含む。
【００４５】
電子署名検証装置１０は、データ追加装置２０が生成した落とし戸付ハッシュ値と、落とし戸付ハッシュ値導出に必要なパラメータとを取得し、これらと電子署名付与装置１０であらかじめ生成された元データに署名を付与し、データ追加装置２０へ出力する。
【００４６】
データ追加装置２０は、落とし戸付ハッシュ値、パラメータを有するデータを取得し、生成データを追加データとして、これを取得データに追加する。又、秘密情報を用いて追加データと共に落とし戸付ハッシュ関数に入力することで、落とし戸付ハッシュ値に等しくなる確定値を計算し、取得データと共に電子署名検証装置３０へ出力する。
【００４７】
電子署名検証装置３０は、電子署名が付与されたデータを取得し、取得データが有するパラメータと確定値より落とし戸付ハッシュ値を導出し、入力データが有する落とし戸付ハッシュ値と比較検証を行うことで、追加データの正当性を検証する。又、落とし戸付ハッシュ値、パラメータ、及び電子署名付与装置の元データに付与された署名を検証し、落とし戸付ハッシュ値、元データの正当性を検証する。
【００４８】
以下、電子署名付与装置１０、データ追加装置２０、電子署名検証装置３０のより詳細な構成について説明する。
【００４９】
電子署名付与装置１０は、電子署名付与部１１と、データ入出力部１２とを備える。
【００５０】
データ入出力部１２は、データ追加装置２０が出力した、落とし戸付ハッシュ値、パラメータの取得を行う。取得方法は、通信を介してデータ追加装置２０より直接入力するか、あるいはあらかじめネットワーク上に登録されているものを取得する。具体的には、落とし戸付ハッシュ値はｈy（ｍ’，ｒ’）であり、パラメータはｇ，ｐ，ｙである。
【００５１】
電子署名付与部１１は、従来の電子署名技術により、あらかじめ生成された元データ、パラメータ、落とし戸付ハッシュ値に署名を付与する。
【００５２】
データ入出力部１２は、元データ、パラメータ、落とし戸付ハッシュ値、及びそれらに付与された署名をデータ追加装置２０に対して出力する。
【００５３】
尚、電子署名付与装置１０は、図示していないがデータ保持部を備え、データ追加装置から入力された落とし戸ハッシュ値、パラメータ、元データなどを保持する。データ保持部は、ＲＡＭ、ＲＯＭ、ハードディスク、フレキシブルディスク、コンパクトディスク、ＩＣチップ、カセットテープなどの記録媒体である。
【００５４】
データ追加装置２０は、落とし戸付ハッシュ値生成部２１と、データ入出力部２２と、データ追加部２３と、確定値計算部２４とを備える。
【００５５】
落とし戸付ハッシュ値生成部２１は、表１記載の各値のうち、ｍ，ｒ以外を生成し、落とし戸付ハッシュ値、パラメータをデータ入出力部２２に渡し、秘密鍵、及び確定値ｒの計算に必要な値を確定値計算部２４に渡す。秘密鍵は具体的にはｘであり、確定値計算に必要な値は、ｍ’，ｒ’，ｑである。データ入出力部２２は、落とし戸付ハッシュ値、パラメータを出力する。出力方法は、通信を介して電子署名付与装置へ直接出力するか、ネットワーク上に登録する。
【００５６】
データ追加部２３は、生成データを追加データとし、これをデータ入出力部２２が電子署名付与装置１０より取得したデータに追加する。追加データは具体的にはｍである。
【００５７】
確定値計算部２４は、ｘ，ｍ，ｍ’，ｒ’，ｑより確定値ｒを生成し、データ入出力部２２は、追加データを追加した取得データと確定値ｒを共に電子署名検証装置３０へ出力する。
【００５８】
尚、データ追加装置２０は、図示していないがデータ保持部を備え、落とし戸付ハッシュ値、秘密鍵ｘ、確定値ｒなどの表１に挙げた値や追加データを保持する。データ保持部は、ＲＡＭ、ＲＯＭ、ハードディスク、フレキシブルディスク、コンパクトディスク、ＩＣチップ、カセットテープなどの記録媒体である。
【００５９】
電子署名検証装置３０は、データ取得部３１、電子署名検証部３２、落とし戸付ハッシュ値計算部３３を備える。
【００６０】
データ取得部３１は、データ追加装置２０が出力したデータ、及び確定値を取得する。
【００６１】
電子署名検証部３２は、取得データが有する電子署名付与装置１０が付与した電子署名により、元データ、落とし戸付ハッシュ値、及びパラメータの正当性を検証する。
【００６２】
落とし戸付ハッシュ値計算部３３は、取得データが有する追加データ、パラメータ、及び確定値より落とし戸付ハッシュ値ｈy（ｍ，ｒ）を計算する。この値を取得データが有する落とし戸付ハッシュ値と比較検証を行う。ここで、もし両者が等しければ、電子署名検証部３２により、落とし戸付ハッシュ値、パラメータの正当性が検証できていた場合、追加データよりも正当なものであるといえる。上記２段階の検証により、電子署名付与装置１０の元データ、及びデータ追加装置２０の追加データの正当性が保障される。
【００６３】
尚、電子署名検証装置３０は、図示していないがデータ保持部を備え、データ追加装置から入力された取得データなどを保持する。データ保持部は、ＲＡＭ、ＲＯＭ、ハードディスク、フレキシブルディスク、コンパクトディスク、ＩＣチップ、カセットテープなどの記録媒体である。
【００６４】
上記の例では、電子署名付与装置１０やデータ追加装置２０はパラメータや落とし戸付ハッシュ値を出力しているが、検証方法からも分かるように、これらの値は検証時にのみ必要である。したがって、落とし戸付ハッシュ値とパラメータを一意に識別できるような識別子があり、その識別子を用いて電子署名検証装置３０が、落とし戸付ハッシュ値、及びパラメータを取得できるのであれば、電子署名付与装置や、各データ追加装置は、落とし戸付ハッシュ値、パラメータの換わりに識別子を出力しても構わない。
【００６５】
次に、第１の実施形態に係る多段署名認証方法について、図２を用いて説明する。
【００６６】
（イ）まず、ステップＳ１０１において、データ追加装置２０は、表１に示す各値を生成する。そして、ステップＳ１０２において、落とし戸付ハッシュ値及びパラメータを電子署名付与装置１０へ出力する。
【００６７】
（ロ）次に、ステップＳ１０３において、電子署名付与装置１０は、あらかじめ電子署名付与装置１０において生成されている元データ、落とし戸付ハッシュ値、パラメータの署名を付与する。そして、ステップＳ１０４において、これらのデータ及び署名をデータ追加装置２０へ出力する。
【００６８】
（ハ）次に、ステップＳ１０５において、データ追加装置２０は、生成データを追加データとし、これを電子署名付与装置１０より取得したデータに追加する。そして、ステップＳ１０６において、秘密情報を用いて追加データと共に落とし戸付ハッシュ関数に入力することで、落とし戸付ハッシュ値に等しくなる確定値を計算する。そして、ステップＳ１０７において、電子署名が付与された元データ、パラメータ、落とし戸付ハッシュ値と共に確定値が付与された追加データを電子署名検証装置３０へ出力する。
【００６９】
（ニ）電子署名検出装置３０が取得するデータが、図３に示すようなデータ構造である。即ち、電子署名が付与された元データ、パラメータ、落とし戸付ハッシュ値と確定値が付与された追加データとを取得する。そして、ステップＳ１０８において、電子署名検出装置３０は、電子署名付与装置１０が付与した電子署名により、元データ、落とし戸付ハッシュ値、及びパラメータの正当性を検証する。
【００７０】
（ホ）次に、ステップＳ１０９において、電子署名検出装置３０は、取得データが有する追加データ、パラメータ、及び確定値より落とし戸付ハッシュ値ｈy（ｍ，ｒ）を計算する。そして、ステップＳ１１０において、計算して得られた値を取得データが有する落とし戸付ハッシュ値と比較する。ここで、両者が等しく、ステップＳ１０８において、落とし戸付ハッシュ値、パラメータの正当性が検証できていた場合、追加データよりも正当なものであるといえる。ステップＳ１０８及びステップＳ１１０の２段階の検証により、電子署名付与装置１０の元データ、及びデータ追加装置２０の追加データの正当性が保障される。
【００７１】
第１の実施形態に係る多段署名認証システムによると、データ追加装置は署名が付与された元データにデータを追加する場合に、追加データに対して電子署名を付与する必要がなく、署名に要する計算時間を短縮することができる。又、第１の実施形態に係る多段署名認証システムにおいて、識別情報は、落とし戸ハッシュ値を生成する際に生成されたパラメータである。このため、電子署名検証装置がパラメータを用いて落とし戸付ハッシュ値を計算することができる。
【００７２】
又、第１の実施形態に係る電子署名付与装置によると、元データ、識別情報（パラメータ）、及び落とし戸付ハッシュ値に電子署名を付与することができる。又、第１の実施形態に係る電子署名付与装置によると、通信ネットワークを介して、識別情報（パラメータ）、及び落とし戸付ハッシュ値を入力することができる。
【００７３】
又、第１の実施形態に係るデータ追加装置によると、電子署名を付与する代わりに、確定値を付与することで署名の時間を短縮し、確定値により生成データの正当性を保障することができる。又、第１の実施形態に係るデータ追加装置によると、通信ネットワークを介して、識別情報（パラメータ）、及び落とし戸付ハッシュ値を出力することができる。
【００７４】
又、第１の実施形態に係る電子署名検証装置によると、電子署名、落とし戸付ハッシュ値により、元データ及び追加データの正当性を検証することができる。更に詳しくは、第１の実施形態に係る電子署名検証装置によると、電子署名により、元データの正当性を検証し、取得データに含まれる落とし戸付ハッシュ値と計算された落とし戸付ハッシュ値とを比較することにより、追加データの正当性を検証することができる。又、落とし戸付ハッシュ値とパラメータを一意に識別できるような識別子があり、第１の実施形態に係る電子署名検証装置は、その識別子を用いて落とし戸付ハッシュ値及びパラメータを取得することとしてもよい。この場合、取得したデータに落とし戸付ハッシュ値やパラメータ等が含まれていなくても、識別子を用いてそれらを取得することで、落とし戸付ハッシュ値の計算が可能となる。
【００７５】
（第２の実施形態）
第２の実施形態に係る多段署名認証システムは、図４に示すように、電子署名付与装置１０と、ｎ個（ｎは自然数）のデータ追加装置２０と、電子署名検証装置３０とを備える。以下の説明において、ｉ番目にデータを追加するデータ追加装置や、そのデータ追加装置であらかじめ生成される生成データ、そのデータ追加装置が追加する追加データ、生成した落とし戸付ハッシュ値、識別情報、及び確定値には、後ろに（ｉ）を記述するものとする。又、データ追加装置２０（ｉ）が生成した落とし戸付ハッシュ値に係わる各値は、ｘi，ｙiのような添え字付で記述するものとする。
【００７６】
電子署名付与装置１０の動作は、第１の実施形態と同様のため、ここでは説明を省略する。
【００７７】
データ追加装置２０（ｉ）は、ｉが１以上ｎ−１以下である場合、生成した落とし戸付ハッシュ値（ｉ）と、パラメータ（ｉ）を出力し、それらを含むデータを取得する。又、データ追加装置２０（ｉ＋１）から取得した落とし戸付ハッシュ値（ｉ＋１）、パラメータ（ｉ＋１）、及びデータ追加装置２０（ｉ）があらかじめ生成した生成データ（ｉ）を追加データ（ｉ）とし、取得データに追加する。さらに、秘密情報を用いて、追加データ（ｉ）と共に落とし戸付ハッシュ関数に入力することで落とし戸付ハッシュ値（ｉ）に等しくなるような確定値（ｉ）を導出し、取得データと共に出力する。データ追加装置２０（ｎ）は、追加データ（ｎ）が生成データ（ｎ）のみであるという点を除けば、上記データ追加装置２０（ｉ）の動作と等しい。
【００７８】
電子署名検証装置３０の落とし戸付ハッシュ値計算部３３は、取得データが有するパラメータ（ｉ）、追加データ（ｉ）及び確定値（ｉ）から落とし戸付ハッシュ値（ｉ）を導出し、取得データが有する落とし戸付ハッシュ値（ｉ）と比較検証を行う操作を、ｉ＝１からｉ＝ｎまで施す。電子署名検証部３２の動作は、第１の実施形態と同様である。
【００７９】
以下、データ追加装置２０（ｉ）と、電子署名検証装置３０の落とし戸付ハッシュ値計算部３３について、詳細に説明を行う。
【００８０】
図５に、データ追加装置２０（ｉ−１）、データ追加装置２０（ｉ）、データ追加装置２０（ｉ＋１）間の情報の流れを示す。データ追加装置２０（ｉ）の落とし戸付ハッシュ値生成部２１は、表１記載の各値を生成し、落とし戸付ハッシュ値（ｉ）、パラメータ（ｉ）をデータ入出力部２２に渡し、秘密鍵、及び確定値であるｒiの計算に必要な値を確定値計算部２４に渡す。秘密鍵は具体的にはｘiであり、確定値計算に必要な値は、ｍi’，ｒi’，ｑiである。データ入出力部２２は、落とし戸付ハッシュ値（ｉ）、パラメータ（ｉ）を出力する。具体的には、落とし戸付ハッシュ値（ｉ）は、ｈyi（ｍi’，ｒi’）であり、パラメータ（ｉ）は、ｇi，ｐi，ｙiである。データ追加部２３は、生成データ（ｉ）、データ入出力部２２がデータ追加装置（ｉ＋１）より取得した落とし戸付ハッシュ値（ｉ＋１）、パラメータ（ｉ＋１）を合わせて追加データ（ｉ）とし、データ入出力部２２がデータ追加装置（ｉ−１）より取得したデータに追加する。具体的には、落とし戸付ハッシュ値（ｉ＋１）はｈyi+1（ｍi+1’，ｒi+1’）であり、パラメータ（ｉ＋１）はｇi+1，ｐi+1，ｙi+1であり、追加データ（ｉ）はｍiである。確定値計算部２４は、ｘi，ｍi，ｍi’，ｒi’，ｑiより確定値（ｉ）であるｒiを生成し、データ入出力部２２は、追加データ（ｉ）を追加した取得データと確定値（ｉ）を共にデータ追加装置（ｉ＋１）へ出力する。ここで、ｉ，ｊをｎ以下の異なる自然数として、データ追加装置２０（ｉ）と、データ追加装置２０（ｊ）は、同じデータ追加装置であって構わない。この場合、上記操作を追加データ（ｉ）について、追加データ（ｊ）について、それぞれ行うことになる。
【００８１】
図６に、電子署名検証装置の取得データを示す。この取得データには、電子署名付与装置１０及び各データ追加装置２０（ｉ）が出力するデータを含まれる。
【００８２】
電子署名検証装置３０の落とし戸付ハッシュ値計算部３３は、データ取得部３１が取得したデータが有するパラメータ（ｉ）、確定値（ｉ）、追加データ（ｉ）より落とし戸付ハッシュ値（ｉ）を計算する。具体的には、ｈyi（ｍi，ｒi）となる。この値を、第１の実施形態と同様に、取得データが有する落とし戸付ハッシュ値（ｉ）と比較検証を行う。もし両者が等しく、追加データ（ｉ−１）の正当性が検証されていれば、追加データ（ｉ−１）に含まれる落とし戸付ハッシュ値（ｉ）、パラメータ（ｉ）の正当性も検証されており、追加データ（ｉ）も正当なものであるといえる。落とし戸付ハッシュ値計算部３３は、上記検証をｉ＝１からｎまで順に行うことで、全ての追加データの正当性を検証する。
【００８３】
又、第２の実施形態において、電子署名付与装置１０の電子署名付与部１１は、データ追加装置２０がデータを追加する場所を指定するプレースホルダを生成し、データ追加装置２０（ｉ）のデータ追加部２３は、識別情報が付与されたデータがプレースホルダを有する場合、プレースホルダ内に追加データを挿入する。プレースホルダは、データ挿入のためのテンプレートなどで、データ追加装置２０がデータを追加する場所を指定できれば良い。例えば、データがＳＭＩＬ文書の場合で、テンプレートを用いた場合は、電子署名付与装置１０やデータ追加装置２０（ｉ）は、図７に示すようなＳＭＩＬ文書において、データ追加装置２０を指定するＩＤを有する＜video＞要素を生成し、src属性を空にしておく。このＳＭＩＬ文書を取得したデータ追加装置２０（ｉ＋１）は、取得したプレースホルダ付ＳＭＩＬ文書内の自分のＩＤがある要素のsrc属性に、生成データであるＵＲＬを追加する。例えば、生成データ追加後のＳＭＩＬ文書は図８のようになる。もし複数のデータ追加装置２０（ｉ）が多段にプレースホルダを出力する場合は、追加が入れ子状に行われていき、結果的に図９に示すようなデータ構造となる。
【００８４】
尚、第１の実施形態において、電子署名付与装置１０あるいはデータ追加装置２０が、追加データを挿入する場所を指定するためのプレースホルダを出力することとしてもよい。
【００８５】
第２の実施形態に係る多段署名認証システムによると、複数のデータ追加装置が署名が付与された元データにデータを追加する場合に、各追加データに対して電子署名を付与する必要がなく、署名に要する計算時間を短縮することができる。
【００８６】
第２の実施形態に係る電子署名付与装置によると、追加データを挿入する場所を指定することができる。
【００８７】
又、第２の実施形態に係るデータ追加装置によると、複数のデータ追加装置にそれぞれにおいて、電子署名を付与する代わりに、確定値を付与することで署名の時間を短縮し、確定値により生成データの正当性を保障することができる。又、第２の実施形態に係るデータ装置によると、追加データを挿入する場所を指定することができる。
【００８８】
又、第２の実施形態に係る電子署名認証装置によると、追加データが落とし戸付ハッシュ値を含む場合に、各追加データの正当性を検証することができる。又、第１の落とし戸付ハッシュ値から順に検証を行っていくことで、追加データに改ざんが行われた場合に、それがどの追加データによって行われ、どのデータ追加装置が出力したデータに行われたか検出することができる。
【００８９】
（第３の実施形態）
第３の実施形態に係る多段署名認証システムは、図１０に示すように、電子署名付与装置１０と、ｎ個（ｎは自然数）のデータ追加装置２０と、電子署名検証装置３０とを備える。第３の実施形態においては、電子署名付与装置１０あるいはデータ追加装置２０（ｉ）は、複数のデータ追加装置２０より落とし戸付ハッシュ値、及びパラメータを取得する。以下、電子署名付与装置１０及びデータ追加装置２０（ｉ）について詳細に説明を行う。
【００９０】
まず、電子署名付与装置１０が複数のデータ追加装置２０より落とし戸付ハッシュ値、及びパラメータを取得する場合について説明する。電子署名付与装置１０の構成は、図１と同様である。
【００９１】
電子署名付与装置１０のデータ入出力部１２は、ｋをｎ以下の自然数として、データ追加装置２０（１）〜データ追加装置２０（ｋ）がそれぞれ出力した落とし戸付ハッシュ値（１）〜落とし戸付ハッシュ値（ｋ）、パラメータ（１）〜パラメータ（ｋ）の取得を行う。電子署名付与部１１は、電子署名付与装置１０の元データ、落とし戸付ハッシュ値（１）〜落とし戸付ハッシュ値（ｋ）、パラメータ（１）〜パラメータ（ｋ）までに署名を付与する。データ入出力部１２は、元データ、パラメータ（１）〜パラメータ（ｋ）、落とし戸付ハッシュ値（１）〜落とし戸付ハッシュ値（ｋ）をデータ追加装置２０（１）へ出力する。
【００９２】
このとき、ｉがｋ以下であるデータ追加装置２０（ｉ）のデータ入出力部２２は、落とし戸付ハッシュ値生成部２１が生成した落とし戸付ハッシュ値（ｉ）、パラメータ（ｉ）を、電子署名付与装置１０に対して出力する。又、ｉがｋ−１以下であるデータ追加装置２０（ｉ）のデータ入出力部２２が、電子署名付与装置１０あるいはデータ追加装置（ｉ−１）から、落とし戸付ハッシュ値（ｉ）、パラメータ（ｉ）を有するデータを取得した場合、そのデータはすでに落とし戸付ハッシュ値（ｉ＋１）、パラメータ（ｉ＋１）を有するため、生成データ（ｉ）を追加データ（ｉ）とする。
【００９３】
次に、データ追加装置２０（ｉ）が複数のデータ追加装置２０より落とし戸付ハッシュ値、及びパラメータを取得する場合について説明する。ｍをｎ−ｉ以下の自然数として、データ追加装置２０（ｉ）のデータ入出力部２２は、データ追加装置２０（ｉ＋１）〜データ追加装置２０（ｉ＋ｍ）がそれぞれ出力した落とし戸付ハッシュ値（ｉ＋１）〜落とし戸付ハッシュ値（ｉ＋ｍ）、パラメータ（ｉ＋１）〜パラメータ（ｉ＋ｍ）を取得し、生成データ（ｉ）、落とし戸付ハッシュ値（ｉ＋１）〜落とし戸付ハッシュ値（ｉ＋ｍ）、パラメータ（ｉ＋１）〜パラメータ（ｉ＋ｌ）を追加データ（ｉ）とする。また、ｊをｍ以下として、データ追加装置２０（ｉ＋ｊ）は、生成データ（ｉ＋ｊ）を追加データ（ｉ＋ｊ）とする。
【００９４】
又、電子署名検証装置については、第１の実施形態と同様であるので、ここでは説明を省略する。
【００９５】
尚、第３の実施形態においても、第２の実施形態において説明したように、電子署名付与装置１０あるいはデータ追加装置２０が、追加データを挿入する場所を指定するためのプレースホルダを出力することとしてもよい。
【００９６】
第３の実施形態に係る多段署名認証システムによると、複数のデータ追加装置が署名が付与された元データにデータを追加する場合に、各追加データに対して電子署名を付与する必要がなく、署名に要する計算時間を短縮することができる。
【００９７】
又、第３の実施形態に係る電子署名付与装置によると、複数のデータ追加装置の落とし戸付ハッシュ値、及び識別情報（パラメータ）に電子署名を付与することができる。
【００９８】
又、第３の実施形態に係るデータ追加装置によると、複数のデータ追加装置の識別情報、及び落とし戸付ハッシュ値を取得したデータに追加し、共に付与する確定値により正当性を保障することができる。
【００９９】
（第４の実施形態）
本発明の第４の実施形態では、電子署名付与装置１０が、取得した落とし戸付ハッシュ値を出力せず、又、各データ追加装置２０の追加データに落とし戸付ハッシュ値が含まれない場合について、説明する。多段署名認証システムの構成は、図１と同様である。以下、電子署名付与装置１０、データ追加装置２０（ｉ）、電子署名検証装置３０について詳細に説明する。
【０１００】
電子署名付与装置１０の電子署名付与部１１は、元データ、落とし戸付ハッシュ値（１）、パラメータ（１）に電子署名を付与し、データ入出力部は元データ、パラメータ（１）、電子署名を出力する。
【０１０１】
データ追加装置（ｉ）のデータ追加部２３は、元データとパラメータ（ｉ＋１）を追加データ（ｉ）とする。また、確定値計算部２４は、追加データ（ｉ）、落とし戸付ハッシュ値（ｉ＋１）を合わせてｍiとし、確定値（ｉ）を計算する。
【０１０２】
この場合、電子署名検証装置３０が取得するデータは、図１１のようになる。落とし戸付ハッシュ値（１）は、落とし戸付ハッシュ値計算部３２により計算されるが、落とし戸付ハッシュ値（１）は、追加データ（１）、落とし戸付ハッシュ値（２）、確定値（１）から計算されるため、落とし戸付ハッシュ値（２）が必要である。同様にして、ｎ−１以下であるｉに対して、落とし戸付ハッシュ値（ｉ）を導出するには落とし戸付ハッシュ値（ｉ＋１）が必要である。ここで、落とし戸付ハッシュ値（ｎ）は、データ追加装置２０（ｎ）の生成データ（ｎ）と確定値（ｎ）により計算されるため、導出することができる。従って、落とし戸付ハッシュ値（１）は、落とし戸付ハッシュ値計算部３２により再帰的に落とし戸付ハッシュ値を計算することで導出可能である。電子署名検証部３２は、以上求めた落とし戸付ハッシュ値（１）に付与された署名の検証を行い、もし検証の結果、落とし戸付ハッシュ値（１）が正当なものであれば、落とし戸付ハッシュ値（１）の導出に用いた追加データ（１）〜追加データ（ｎ）までの全ての追加データの正当性が保障されることになる。
【０１０３】
尚、第４の実施形態においても、第２の実施形態において説明したように、電子署名付与装置１０あるいはデータ追加装置２０が、追加データを挿入する場所を指定するためのプレースホルダを出力することとしてもよい。
【０１０４】
第４の実施形態に係る多段署名認証システムによると、電子署名付与装置及びデータ追加装置において、落とし戸付ハッシュ値を出力しないため、出力するデータ量を減らすことができる。
【０１０５】
又、第４の実施形態に係る電子署名付与装置によると、落とし戸付ハッシュ値を出力しないため、出力するデータ量を減らすことができる。
【０１０６】
又、第４の実施形態に係るデータ追加装置によると、落とし戸付ハッシュ値を取得したデータに追加しないため、出力するデータ量を少なくすることができる。
【０１０７】
又、第４の実施形態に係る電子署名検証装置によると、データ追加装置２０（ｎ）の生成データ（ｎ）と確定値（ｎ）により、各データ追加装置における落とし戸付ハッシュ値（１）〜落とし戸付ハッシュ値（ｎ）を導出することが可能であり、付与された電子署名を検証することにより、全ての追加データの正当性を検証することができる。
【０１０８】
（第５の実施形態）
本発明の第５の実施形態では、図１２に示すように、第２の実施形態において、データ追加装置２０（ｉ）がｊ番目に再びデータを追加する場合について説明する。再びデータを追加する方法としては、それぞれの追加データ用に落とし戸付ハッシュ値を生成する方法と、複数の追加データに対して一つの落とし戸付ハッシュ値しか生成しない場合がある。ここで、それぞれの追加データに対して落とし戸付ハッシュ値を生成する場合は、第２の実施形態において、データ追加装置２０（ｉ）がデータ追加装置２０（ｊ）として振る舞うことに他ならないため、ここでは省略する。
【０１０９】
以下、一つの落とし戸付ハッシュ値を用いた複数回のデータの追加について詳細に説明する。具体的には、ｊをｉ＋１より大きい自然数として、データ追加装置（ｉ）がデータ追加装置（ｉ−１）よりデータを取得し、ｉ番目に再びデータを追加する場合について考える。尚、以下データ追加装置（ｉ）が２回のデータ追加を行う場合について説明するが、実際には本実施形態を何度も適用することで、２回以上のデータ追加も可能である。
【０１１０】
データ追加装置２０（ｉ）は、データ追加装置２０（ｉ−１）からデータを取得した場合に、第２実施形態において説明したように、追加データ（ｉ）と確定値（ｉ）を出力する。それらを含むデータをデータ追加装置２０（ｊ−ｉ）が取得した場合に、データ追加装置２０（ｊ−１）は、データ追加装置２０（ｉ）が出力したパラメータ（ｉ）、落とし戸付ハッシュ値（ｉ）、生成データ（ｊ−１）を追加データ（ｊ−１）として、確定値（ｊ−１）と共に出力する。ｊ番目に再びデータを追加するデータ追加装置２０（ｉ）は、データ追加装置２０（ｊ＋１）よりパラメータ（ｊ＋１）、落とし戸付ハッシュ値（ｊ＋１）を取得し、生成データ（ｊ）、パラメータ（ｊ＋１）、落とし戸付ハッシュ値（ｊ＋１）を追加データ（ｊ）とし、取得データに追加し、確定値（ｊ）と共に出力する。
【０１１１】
第５の実施形態に係る電子署名付与装置及び電子署名検証装置３０の動作は、第２の実施形態と同様であるので、ここでは説明を省略する。
【０１１２】
尚、第５の実施形態においても、第２の実施形態において説明したように、電子署名付与装置１０あるいはデータ追加装置２０が、追加データを挿入する場所を指定するためのプレースホルダを出力することとしてもよい。
【０１１３】
第５の実施形態に係る多段署名認証システムによると、同じデータ追加装置が、２度以上データを追加することができる。
【０１１４】
第５の実施形態に係るデータ追加装置によると、一つのデータに対して、何度もデータを追加することができる。
【０１１５】
（その他の実施形態）
本発明は上記の実施形態によって記載したが、この開示の一部をなす論述及び図面はこの発明を限定するものであると理解すべきではない。この開示から当業者には様々な代替実施形態、実施例及び運用技術が明らかとなろう。
【０１１６】
例えば、第１〜第５の実施形態において、電子署名付与装置、データ追加装置、電子署名検証装置を異なる装置として説明したが、これらの機能を一つの装置にまとめても構わない。
【０１１７】
同様に、電子署名付与装置、データ追加装置、電子署名検証装置はそれぞれ複数の機能を有するが、それぞれの機能毎に装置を分けても構わない。例えば、データ追加装置において、落とし戸付ハッシュ値生成部と確定値計算部とを異なる装置に配置しても構わない。この場合、それぞれの機能部を有線あるいは無線で接続するものとする。
【０１１８】
このように、本発明はここでは記載していない様々な実施形態等を含むことは勿論である。従って、本発明の技術的範囲は上記の説明から妥当な特許請求の範囲に係る発明特定事項によってのみ定められるものである。
【図面の簡単な説明】
【０１１９】
【図１】第１の実施形態に係る多段署名検証システムの構成ブロック図である。
【図２】第１の実施形態に係る多段署名検証方法を示すフローチャートである。
【図３】第１の実施形態に係る電子署名検証装置が取得するデータ例である。
【図４】第２の実施形態に係る多段署名検証システムの構成ブロック図である。
【図５】第２の実施形態に係るデータ追加装置間のデータの流れを説明する図である。
【図６】第２の実施形態に係る電子署名検証装置が取得するデータ例である。
【図７】第２の実施形態に係るプレースホルダを含むＳＭＩＬ文書の例である。
【図８】図７においてプレースホルダにデータを挿入した例である。
【図９】第２の実施形態に係るプレースホルダが多段に形成された場合のデータ構造の例である。
【図１０】第３の実施形態に係る多段署名検証システムの構成ブロック図である。
【図１１】第４の実施形態に係る電子署名検証装置が取得するデータ例である。
【図１２】第５の実施形態に係る多段署名検証システムの構成ブロック図である。
【符号の説明】
【０１２０】
１０  電子署名付与装置
１１  電子署名付与部
１２  データ入出力部
２０  データ追加装置
２１  落とし戸付ハッシュ値生成部
２２  データ入出力部
２３  データ追加部
２４  確定値計算部
３０  電子署名検証装置
３１  データ取得部
３２  電子署名検証部
３３  落とし戸付ハッシュ値計算部
【図１】
2005210277.tif 000005
【図２】
2005210277.tif 000006
【図３】
2005210277.tif 000007
【図４】
2005210277.tif 000008
【図５】
2005210277.tif 000009
【図６】
2005210277.tif 000010
【図７】
2005210277.tif 000011
【図８】
2005210277.tif 000012
【図９】
2005210277.tif 000013
【図１０】
2005210277.tif 000014
【図１１】
2005210277.tif 000015
【図１２】
2005210277.tif 000016