(57)【要約】【課題】暗号関数が危殆化した際に効率的に再署名処理する電子署名装置を提供する。【解決手段】電子署名装置は、乱数のべき乗剰余演算を行った結果を、準同型性を有する一方向性関数によって演算した第１の演算結果と、署名対象である電子文書と、署名鍵と、第１のハッシュ関数とを用いて算出した第２の演算結果と第１の演算結果とを電子署名として生成し、乱数と第１の演算結果とを対応付けて記憶し、電子文書に再署名処理を行う場合に、記憶手段から読み出した複数の乱数に基づく第１の組み合わせ情報を算出し、読み出した複数の第１の演算結果に基づく第２の組み合わせ情報を算出し、第２の組み合わせ情報と電子文書と署名鍵と第２のハッシュ関数とを用いた演算結果と第１の組み合わせ情報とに基づいて第２の再演算結果を算出し、第１の再演算結果と第２の再演算結果とを再電子署名として生成する。【選択図】図１
2008258661.tif 000002
【特許請求の範囲】
【請求項１】
公開鍵に対応する署名鍵を有し、署名鍵を用いて複数の電子文書のそれぞれに電子署名を付与する電子署名装置であって、
乱数のべき乗剰余演算を行った結果を、準同型性を有する一方向性関数によって演算した第１の演算結果を算出する第１の演算手段と、
該第１の演算結果と、署名対象である電子文書と、署名鍵と、第１のハッシュ関数とを用いて第２の演算結果を算出し、前記第１の演算結果と前記第２の演算結果とを電子署名として生成する署名手段と、
前記乱数と前記第１の演算結果とを対応付けて再署名用情報として記憶する記憶手段と、
前記電子文書に再署名処理を行う場合に、複数の再署名用情報を前記記憶手段から読み出し、読み出した再署名用情報に含まれる複数の乱数に基づく第１の組み合わせ情報を算出し、読み出した再署名用情報に含まれる複数の第１の演算結果に基づく第２の組み合わせ情報を算出する第１の再演算手段と、
該第２の組み合わせ情報と前記電子文書と前記署名鍵と第２のハッシュ関数とを用いた演算結果と前記第１の組み合わせ情報とに基づいて第２の再演算結果を算出し、前記第１の再演算結果と前記第２の再演算結果とを再電子署名として生成する再署名手段と、
を備えることを特徴とする電子署名装置。
【請求項２】
入力された前記電子署名の保証期間が予め定められた一定の期間よりも短い場合に、前記再署名用情報を前記記憶手段に記憶させる再署名用情報登録手段
を備えることをさらに特徴とする請求項１に記載の電子署名装置。
【請求項３】
前記記憶手段は、前記再署名用情報に対応付けて、再署名処理に利用されたか否かを表す情報である再署名利用フラグを記憶し、
前記再署名手段は、前記再署名利用フラグが利用されていないことを表している再署名用情報を前記記憶手段から読み出して前記第２の再署名用情報とし、読み出した該第２の再署名用情報に対応する再署名利用フラグを、利用されたことを表す状態にして前記記憶手段に記憶させる
ことをさらに特徴とする請求項１または請求項２に記載の電子署名装置。
【請求項４】
公開鍵に対応する署名鍵を用いて複数の電子文書のそれぞれに電子署名を付与する電子署名方法であって、
第１の演算手段が、乱数のべき乗剰余演算を行った結果を、準同型性を有する一方向性関数によって演算した第１の演算結果を算出する工程と、
署名手段が、該第１の演算結果と、署名対象である電子文書と、署名鍵と、第１のハッシュ関数とを用いて第２の演算結果を算出し、前記第１の演算結果と前記第２の演算結果とを電子署名として生成する工程と、
記憶手段が、前記乱数と前記第１の演算結果とを対応付けて再署名用情報として記憶する工程と、
前記電子文書に再署名処理を行う場合に、第１の再演算手段が、複数の再署名用情報を前記記憶手段から読み出し、読み出した再署名用情報に含まれる複数の乱数に基づく第１の組み合わせ情報を算出し、読み出した再署名用情報に含まれる複数の第１の演算結果に基づく第２の組み合わせ情報を算出する工程と、
再署名手段が、該第２の組み合わせ情報と前記電子文書と前記署名鍵と第２のハッシュ関数とを用いた演算結果と前記第１の組み合わせ情報とに基づいて第２の再演算結果を算出し、前記第１の再演算結果と前記第２の再演算結果とを再電子署名として生成する工程と、
を備えることを特徴とする電子署名方法。
【請求項５】
公開鍵に対応する署名鍵を用いて複数の電子文書のそれぞれに電子署名を付与するコンピュータに、
第１の演算手段が、乱数のべき乗剰余演算を行った結果を、準同型性を有する一方向性関数によって演算した第１の演算結果を算出する工程と、
署名手段が、該第１の演算結果と、署名対象である電子文書と、署名鍵、第１のハッシュ関数とを用いて第２の演算結果を算出し、前記第１の演算結果と前記第２の演算結果とを電子署名として生成する工程と、
記憶手段が、前記乱数と前記第１の演算結果とを対応付けて再署名用情報として記憶する工程と、
前記電子文書に再署名処理を行う場合に、第１の再演算手段が、複数の再署名用情報を前記記憶手段から読み出し、読み出した再署名用情報に含まれる複数の乱数に基づく第１の組み合わせ情報を算出し、読み出した再署名用情報に含まれる複数の第１の演算結果に基づく第２の組み合わせ情報を算出する工程と、
再署名手段が、該第２の組み合わせ情報と前記電子文書と前記署名鍵と第２のハッシュ関数とを用いた演算結果と前記第１の組み合わせ情報とに基づいて第２の再演算結果を算出し、前記第１の再演算結果と前記第２の再演算結果とを再電子署名として生成する工程と、
を実行させるための電子署名プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子文書に電子署名を付与する電子署名装置であって、電子署名に用いる暗号関数が危殆化した場合に、別の関数にて再度電子署名を付与する再署名技術に関する。
【背景技術】
【０００２】
従来、情報システムの安全性を高めるための暗号技術が広く利用されており、電子署名技術もそのひとつである。電子署名は、電子文書に付与される電子情報であり、電子文書の受領者は、電子署名を検証することによって、紙文書での印やサインのように、電子文書の出所の確認を行ったり、偽造や改ざんを防止したりすることができる。
一般的に、電子署名は、電子署名の信頼性を保ちつつ処理を効率化するために、乱数のべき乗剰余演算を行う第１の演算処理を行った後、第１の演算処理の演算結果と、一方向性関数を用いて電子文書（以下、メッセージ）のダイジェスト値を計算するハッシュ関数と、署名者本人が署名を施したことを証明するための公開鍵暗号方式による秘密鍵とを用いた第２の演算処理とが組み合わされて実現されている。これらの署名手法として、ＲＳＡ署名やＤＳＡ（Digital Signature Algorithm）といった電子署名方式がある。
【０００３】
しかしながら、計算機能力の向上や暗号技術に対する新たな攻撃方法の発見により、暗号技術による電子署名の安全性は低下する場合がある。例えば、電子署名処理に用いたハッシュ関数のハッシュ値の衝突を見つける攻撃の発見等により暗号技術の危殆化が起きる。
また、一般的に、電子署名には、その必要性や利用する暗号関数の強度などに応じて保証期間が定められる。すなわち、電子署名者は、該保証期間の間のみ、その電子署名の正当性を保証する。このため、例えば契約に関するメッセージに電子署名を施していた場合で、契約期間の延長を行う場合には、この電子署名の保証期間を延長する必要性が生じる。
このように、電子署名の保証期間を延長する必要が生じた場合のために、既に配布している電子署名を回収して、異なるハッシュ関数を利用して再署名（打ち直し）を行い、再配布することで長期保証を実現する電子署名方式が考えられる。
【０００４】
図９と図１０を参照して、従来技術による再署名処理の動作例を説明する。
電子署名装置は、予め、署名鍵（秘密鍵）（ｘ）と公開鍵（ｐ、ｑ、ｇ、ｙ（ｙ＝ｇｘ））を生成する。そして、電子署名装置は、署名処理対象であるメッセージ（Ｍ）を予め記憶する。電子署名装置は、乱数（ｋ１）を生成して、以下式（１）により第１の演算結果（Ｒ１）を算出する第１の演算処理を行う。
【０００５】
【数１】
2008258661.tif 000003
【０００６】
（１）式における関数Ｆは一方向性関数であり、一般的に電子署名処理には、ハッシュ関数が利用されている。ハッシュ関数は、ある値の演算後の値から演算前の値が逆算できない一方向性と、ある値の演算後と他の値の演算後の値が一致しない非衝突性を有する関数である。
そして、予め生成した署名鍵（ｘ）を用いて、以下式（２）によりメッセージに対して第２の演算結果（ｔ１）を算出する第２の演算処理を行う。
【０００７】
【数２】
2008258661.tif 000004
【０００８】
ｈ１は、予め定められた第１のハッシュ関数である。
電子署名装置は、第１の演算結果（Ｒ１）と第２の演算結果（ｔ１）との組み合わせを、電子署名（σ１）とする。
電子署名装置は、該電子署名文書を複数（ｍ人）の検証者のために生成する必要がある場合には、上記で説明した乱数生成処理、第１の演算処理、第２の演算処理をｍ回繰り返すことも考えられる。そして、電子署名装置は、メッセージ（Ｍ）と、電子署名（σ１）との組み合わせである電子署名文書（Ｍ、σ１）を、検証者に送信する。
検証者は、検証装置によって以下式（３）による電子署名（σ１（σ１＝（Ｒ１、ｔ１）））の検証を行う。
【０００９】
【数３】
2008258661.tif 000005
【００１０】
上記電子署名（σ１）の保証期間が過ぎ、または暗号関数の危殆化が発生し、再署名を行う場合は、検証者は、電子署名文書（Ｍ、σ１）を電子署名装置に送信する。この際、電子署名が予めｍ個生成されていた場合、電子署名はｎ個（ｎ＜ｍ）の再署名を行うこととなる。電子署名装置は、受信した電子署名（Ｍ、σ１）を、上記（３）式により検証し、（３）式の左辺と右辺が一致した場合には、再署名処理を行う。すなわち、電子署名装置は、乱数（ｋ２）を生成し、ｈ１とは異なるハッシュ関数（ｈ２）を用意する。そして、以下式（４）によって第１の演算結果（Ｒ２）を算出する。
【００１１】
【数４】
2008258661.tif 000006
【００１２】
式（４）は、式（１）と同様の構成である。そして、電子署名装置は、以下式（５）によりメッセージに対して第２の演算結果（ｔ２）を算出する。
【００１３】
【数５】
2008258661.tif 000007
【００１４】
式（５）は、式（２）と同様の構成である。
第１の演算結果（Ｒ２）と第２の演算結果（ｔ２）との組み合わせを、再署名の電子署名（σ２）とし、メッセージ（Ｍ）と、電子署名（σ２）との組み合わせである電子署名文書（Ｍ、σ２）を、検証者に送信する。
検証者は、検証装置を用いて、以下式（６）により電子署名の検証を行う。
【００１５】
【数６】
2008258661.tif 000008
【００１６】
このように再署名を行うことで、電子署名の保証期間を延長することができる。
また、特許文献１に示される電子署名では、再署名の必要性が生じた場合には、秘密鍵と公開鍵を再生成して再署名を行い、さらにその動作ログに対して署名を施すことにより、長期保証に向けた署名の延長処理を行うことが提案されている。特許文献２は、新たな鍵を用いて再署名を行う際、その有効期限の更新履歴を電子署名情報に含ませることで、電子署名の延長処理を行っている。
【特許文献１】特開２００４−３２０４９４号公報
【特許文献２】特開２００５−２０４１２６号公報
【発明の開示】
【発明が解決しようとする課題】
【００１７】
このような再署名が必要になる場合とは、例えば、電子署名の保証期間が切れたときや、計算機能力の向上や、新たな攻撃法の発見によりハッシュ関数が危殆化したときである。電子署名の保証期間切れは個別の電子署名ごとに発生するが、ハッシュ関数の危殆化が起きたときには、そのハッシュ関数によって署名された電子署名の全てが再署名の対象となる。すなわち、電子署名処理で利用されるハッシュ関数が危殆化した場合、署名文書が偽造されてしまう恐れがあり、危殆化後も電子署名の有効性を検証する必要がある文書については、ハッシュ関数の危殆化が発生した際に、署名の打ち直し（再署名）が必要不可欠となる。この場合、一時に再署名処理の要求が集中し、署名者に膨大な負担がかかることが想定される。
【００１８】
さらに、上記式（１）および式（４）に利用されるべき乗剰余演算処理は、一般的に公開鍵暗号方式の核となる数学処理として行われるが、コンピュータにとって負荷の高い処理となっている。すなわち、コンピュータが式（１）で利用されるようなべき乗剰余演算を行う場合には、一回のべき乗ごとに順に剰余演算を行っていく計算方法がとられるため、複雑な計算を繰り返さなければならず、負荷の高い処理となる。暗号関数の危殆化によって再署名要求が集中した場合には、電子署名装置は一時に大量のべき乗剰余演算を行わなければならない。
【００１９】
本発明は、このような状況に鑑みてなされたもので、暗号関数が危殆化した際の再署名処理において、電子署名装置の負荷を軽減する電子署名装置を提供する。
【課題を解決するための手段】
【００２０】
上記課題を解決するために、本発明は、公開鍵（例えば、本実施形態における公開鍵（ｐ、ｑ、ｇ、ｙ（ｙ＝ｇｘ）））に対応する署名鍵（例えば、本実施形態における署名鍵（ｘ））を有し、署名鍵を用いて複数の電子文書（例えば、本実施形態におけるメッセージ（Ｍ））のそれぞれに電子署名（例えば、本実施形態における電子署名（σｊ）（σ´ｊ））を付与する電子署名装置（例えば、本実施形態における電子署名装置１００）であって、乱数（例えば、本実施形態におけるｋi）のべき乗剰余演算を行った結果を、準同型性を有する一方向性関数（例えば、本実施形態における関数Ｆ）によって演算した第１の演算結果（例えば、本実施形態におけるｒｉ）を算出する第１の演算手段（例えば、本実施形態における署名付与部１１１）と、第１の演算結果と、署名対象である電子文書と、署名鍵と、第１のハッシュ関数（例えば、本実施形態におけるｈ１）とを用いて第２の演算結果（例えば、本実施形態におけるｔｉ）を算出し、第１の演算結果と第２の演算結果とを電子署名（例えば、本実施形態におけるσｉ＝（ｒｉ、ｔｉ））として生成する署名手段（例えば、本実施形態における署名付与部１１１）と、乱数と第１の演算結果とを対応付けて再署名用情報として記憶する記憶手段（例えば、本実施形態における再署名用情報記憶部１２４）と、電子文書に再署名処理を行う場合に、複数の再署名用情報を記憶手段から読み出し、読み出した再署名用情報に含まれる複数の乱数（例えば、本実施形態におけるｋ２とｋ３）に基づく第１の組み合わせ情報（例えば、本実施形態におけるｋｒｅｓｉｇｎ）を算出し、読み出した再署名用情報に含まれる複数の第１の演算結果（例えば、本実施形態におけるｒ２とｒ３）に基づく第２の組み合わせ情報（例えば、本実施形態におけるｒｒｅｓｉｇｎ）を算出する第１の再演算手段（例えば、本実施形態における再署名付与部１１２）と、第２の組み合わせ情報と電子文書と署名鍵と第２のハッシュ関数（例えば、本実施形態におけるｈ２）とを用いた演算結果と第１の組み合わせ情報とに基づいて第２の再演算結果を算出し、第１の再演算結果と第２の再演算結果とを再電子署名として生成する再署名手段（例えば、本実施形態における再署名付与部１１２）と、を備えることを特徴とする電子署名装置である。
【００２１】
本発明は、入力された電子署名の保証期間が予め定められた一定の期間よりも短い場合に、再署名用情報を記憶手段に記憶させる再署名用情報登録手段（例えば、本実施形態における再署名用情報登録部１６０）を備えることをさらに特徴とする請求項１に記載の電子署名装置である。
【００２２】
本発明は、記憶手段は、再署名用情報に対応付けて、再署名処理に利用されたか否かを表す情報である再署名利用フラグを記憶し、再署名手段は、再署名利用フラグが利用されていないことを表している再署名用情報を記憶手段から読み出して第２の再署名用情報とし、読み出した該第２の再署名用情報に対応する再署名利用フラグを、利用されたことを表す状態にして記憶手段に記憶させることをさらに特徴とする請求項１または請求項２に記載の電子署名装置である。
【００２３】
本発明は、公開鍵に対応する署名鍵を用いて複数の電子文書のそれぞれに電子署名を付与する電子署名方法であって、第１の演算手段が、乱数のべき乗剰余演算を行った結果を、準同型性を有する一方向性関数によって演算した第１の演算結果を算出する工程と、署名手段が、第１の演算結果と、署名対象である電子文書と、署名鍵と、第１のハッシュ関数とを用いて第２の演算結果を算出し、第１の演算結果と第２の演算結果とを電子署名として生成する工程と、記憶手段が、乱数と第１の演算結果とを対応付けて再署名用情報として記憶する工程と、電子文書に再署名処理を行う場合に、第１の再演算手段が、複数の再署名用情報を記憶手段から読み出し、読み出した再署名用情報に含まれる複数の乱数に基づく第１の組み合わせ情報を算出し、読み出した再署名用情報に含まれる複数の第１の演算結果に基づく第２の組み合わせ情報を算出する工程と、再署名手段が、第２の組み合わせ情報と電子文書と署名鍵と第２のハッシュ関数とを用いた演算結果と第１の組み合わせ情報とに基づいて第２の再演算結果を算出し、第１の再演算結果と第２の再演算結果とを再電子署名として生成する工程と、を備えることを特徴とする電子署名方法である。
【００２４】
本発明は、公開鍵に対応する署名鍵を用いて複数の電子文書のそれぞれに電子署名を付与するコンピュータに、第１の演算手段が、乱数のべき乗剰余演算を行った結果を、準同型性を有する一方向性関数によって演算した第１の演算結果を算出する工程と、署名手段が、第１の演算結果と、署名対象である電子文書と、署名鍵と、第１のハッシュ関数とを用いて第２の演算結果を算出し、第１の演算結果と第２の演算結果とを電子署名として生成する工程と、記憶手段が、乱数と第１の演算結果とを対応付けて再署名用情報として記憶する工程と、電子文書に再署名処理を行う場合に、第１の再演算手段が、複数の再署名用情報を記憶手段から読み出し、読み出した再署名用情報に含まれる複数の乱数に基づく第１の組み合わせ情報を算出し、読み出した再署名用情報に含まれる複数の第１の演算結果に基づく第２の組み合わせ情報を算出する工程と、再署名手段が、第２の組み合わせ情報と電子文書と署名鍵と第２のハッシュ関数とを用いた演算結果と第１の組み合わせ情報とに基づいて第２の再演算結果を算出し、第１の再演算結果と第２の再演算結果とを再電子署名として生成する工程と、を実行させるための電子署名プログラムである。
【発明の効果】
【００２５】
以上説明したように、本発明によれば、準同型性を有する一方向性関数により電子署名処理を行い、この際算出したべき乗剰余演算結果を記憶して再署名処理に利用することにより、再署名処理時のべき乗剰余演算処理を行わないことで、効率良く再署名を行う電子署名装置を提供する。
【発明を実施するための最良の形態】
【００２６】
以下、本発明の一実施形態について、図面を参照して説明する。
本実施形態例の説明中で、メッセージとは、偽造や改ざんの防止のために暗号処理を行う対象となる平文をいい、電子文書の情報である。
また、電子署名処理とは、乱数を生成し、該乱数に基づいたべき乗剰余演算を行って第１の演算結果を得る第１の演算処理と、第１の演算結果とメッセージと署名鍵とを用いて、メッセージに関連するダイジェストを算出し、処理を行う第２の演算処理とを行い、第１の演算結果と第２の演算結果とを組み合わせた情報である電子署名を算出して、メッセージと電子署名とを組み合わせた情報である電子署名文書を生成する処理をいう。ハッシュ関数とは、一方向性と非衝突性を有する関数である。
【００２７】
図１は、本実施形態による再署名処理の動作概要を示す図である。
本実施形態例では、電子署名装置は、電子署名のための第１の演算処理に利用する一方向性関数として、一方向性と準同型性とを有する関数を用いる。準同型性については、後に説明する。電子署名装置は、生成する乱数に対してべき乗剰余演算を行い、演算結果を該関数によってさらに演算して第１の演算結果を得て、第１の演算結果とメッセージとの結合情報に基づいて、第２の演算結果を算出する。本発明は、このとき用いた乱数と第１の演算結果を記憶しておき、ハッシュ関数の危殆化が発生した際の再署名処理には第１演算結果の組み合わせを利用することにより、負荷の高いべき乗剰余演算の処理を行わずに電子署名を生成することで、処理効率性を向上するものである。すなわち、従来は再署名の際にはべき乗剰余演算を再度行う必要が生じるが、準同型性を利用することにより、複数の第１の演算結果の積を計算すればよくなる。
【００２８】
図２は、本実施形態による電子署名装置１００の構成を示すブロック図である。
電子署名装置１００は、署名処理部１１０と、記憶部１２０と、通信部１３０と、署名検証部１４０と、乱数生成部１５０と、再署名用情報登録部１６０と、入力部１７０とを備えている。
署名処理部１１０は、電子文書に電子署名を付与し、電子署名文書を出力する機能を有し、署名付与部１１１と、再署名付与部１１２とを備えている。
署名付与部１１１は、乱数に基づいたべき乗剰余演算を行う第１の演算処理と、ハッシュ関数を用いて演算を行う第２の演算処理とを行い、電子署名を生成する。再署名付与部１１２は、再署名用情報記憶部１２４に記憶された再署名用情報を読み出して、電子文書の再署名処理を行う。
【００２９】
記憶部１２０は、電子署名処理に必要な情報を記憶し、例えば、メッセージ記憶部１２１と、配布先記憶部１２２と、署名鍵記憶部１２３と、再署名用情報記憶部１２４とを備える。
メッセージ記憶部１２１は、電子署名を付与する対象であるメッセージと、このメッセージの保証期間を示す情報とを記憶する。配布先記憶部１２２は、生成した電子署名文書を配布する検証装置２００の位置情報を記憶する。鍵記憶部１２３は、電子署名処理に利用するための署名鍵（ｘ）と公開鍵（ｐ、ｑ、ｇ、ｙ（ｙ＝ｇｘ））とを記憶する。
【００３０】
再署名用情報記憶部１２４は、再署名に利用するための乱数と第１の演算結果との再署名用情報と、再署名用情報が再署名処理に利用されたか否かを示す再署名利用フラグとを記憶する。上記乱数は、電子署名を行うために生成されるランダムな情報であり、第１の演算結果は、乱数と公開鍵とを用いてべき乗剰余演算を行った結果である。再署名利用フラグは例えば、ＯＮであれば再署名に利用されたことを、ＯＦＦであれば再署名に利用されていないことを示す。図４は、再署名用情報記憶部１２４の構成を示す図である。図４では、例えば、乱数「Ｋ１」と、第１の演算結果「ｒ１」との再署名用情報に再署名利用フラグ「ＯＮ」が記憶されている。
【００３１】
通信部１３０は、ネットワークを介して検証装置２００と情報通信を行う。署名検証部１４０は、電子署名文書の電子署名が、メッセージと対応しているか否かの検証を行う。乱数生成部１５０は、乱数を生成する。入力部１７０は、署名者からの入力を受け付け、例えば、保証期間入力部１７１と配布先入力部１７２とを備える。
図３は、電子署名文書を配布される検証装置２００の構成を示すブロック図である。検証装置２００は、通信部２１０と、記憶部２２０と、署名検証部２３０とを備えている。通信部２１０は、ネットワークを介して電子署名装置１００と情報通信を行う。記憶部２２０は、電子署名文書等の情報を記憶する。署名検証部２３０は、署名検証部１４０と同様の機能を有しており、電子署名文書の検証を行う。
【００３２】
次に、図５と図６と図７とを参照して、本実施形態による再署名処理の動作例を説明する。
電子署名装置１００の鍵記憶部１２３は、署名鍵（秘密鍵）（ｘ）と、公開鍵（ｐ、ｑ、ｇ、ｙ（ｙ＝ｇｘ））とを予め記憶している。なお、各鍵は、電子署名装置１００が鍵生成部を有することとして生成しても良いし、予め記憶しておいても良いし、鍵生成部を外部装置が備えることとして、ネットワークを介して受信することとしても良いし、鍵が記憶された電子媒体から読み出すことによって鍵を得ても良い。
【００３３】
また、メッセージ記憶部１２１は、電子署名処理の処理対象であるメッセージを予め記憶している。乱数生成部１５０が、乱数（ｋ1）を生成する（ステップＳ１０１）。ここで、ｉは（ｉ＝１、…、ｍ）の値を取り、ｍは電子署名文書を配布する検証者の数である。すなわち、本実施形態において、署名付与部１１１は、検証者（ｍ人）にそれぞれ電子署名文書を生成する。そして、署名付与部１１１は、乱数（ｋ１）と公開鍵（ｇ）と公開鍵（ｐ）とを用いて、以下式（７）により第１の演算結果（ｒｉ）を算出する（ステップＳ１０２）。
【００３４】
【数７】
2008258661.tif 000009
【００３５】
ここで、関数Ｆは、通常の電子署名で用いられる一方向性を有する関数であって、かつ、準同型性を有する関数である。準同型性とは、特定の数学的構造に関する類似性のことであり、例えば、ある値（ｍ１）とある値（ｍ２）との値を知らずに、Ｆ（ｍ１）とＦ（ｍ２）のみを用いて何らかの処理を加えることによりＦ（ｍ１＋ｍ２）、Ｆ（ｍ１×ｍ２）等の演算結果を得ることが可能な関数Ｆの性質をいう。例えば、Ｒ１＝Ｆ（ｍ１）、Ｒ２＝（ｍ２）であってＲ１とＲ２とだけが与えられており、ｍ１とｍ２との値は明らかでない場合でも、Ｒ１×Ｒ２の算出結果とＦ（ｍ１＋ｍ２）の算出結果が一致する。
【００３６】
例えば、公開鍵暗号のような落とし戸付一方向性関数が用いられている場合には、（ｍ１、ｍ２）の演算結果の暗号文を得るためには、一度ｍ１、ｍ２を復号する必要があり、復号処理量増加や秘匿性が損なわれてしまうといった問題が生じる。ここで準同型性を有する関数を利用することにより、ｍ１の暗号文、ｍ２の暗号文のみから（ｍ１、ｍ２）の暗号文を計算することができ、効率的に、かつ情報を秘匿したまま演算結果を得ることが可能となる。
【００３７】
特に、本実施形態例にて用いる関数Ｆが有する準同型性は、以下のような性質であることを特徴とする。すなわち、第１の乱数（例えば、本実施形態におけるｋｉ）と、第２の乱数と、第１の公開鍵（例えば、本実施形態におけるｇ）と第２の公開鍵（例えば、本実施形態におけるｐ）とが与えられたときに、第１の公開鍵を底として第１の乱数を指数とするべき乗数を、第２の公開鍵でべき乗剰余演算を行った結果と、第１の公開鍵を底として第２の乱数を指数とするべき乗数を、第２の公開鍵でべき乗剰余演算を行った結果について、第１の公開鍵を底として第１の乱数と第２の乱数との和を指数とするべき乗数を、第２の公開鍵でべき乗剰余演算を行った結果が、第１のべき乗剰余演算結果と第２のべき乗剰余演算結果とを乗じた結果と一致する性質である。
【００３８】
本実施形態例では、電子署名を行った際の上記第１のべき乗剰余演算結果と上記第２のべき乗剰余演算結果とを記憶しておき、再署名時にはこれらの値を用いることで、べき乗剰余演算処理を新たに行うことなく、記憶された第１のべき乗剰余演算結果と上記第２のべき乗剰余演算結果との積を計算することで、新たなべき乗剰余演算結果を得る。
次に、第１の演算結果（ｒｉ）とハッシュ関数（ｈ１）とを用いた以下式（８）により第２の演算結果（ｔｉ）を算出する（ステップＳ１０３）。
【００３９】
【数８】
2008258661.tif 000010
【００４０】
そして、第１の演算結果（ｒｉ）と第２の演算結果（ｔｉ）との組み合わせを、電子署名（σｉ（σｉ＝（ｒｉ、ｔｉ）））とする。
ユーザは、電子署名についての保証期間の入力を受け付ける保証期間入力部１７１に、保証期間を入力する。保証期間入力部１７１は、メッセージに対応付けて保証期間をメッセージ記憶部１２１に記憶させる。保証期間は、ここでは、保証日数を入力することとするが、期間を表す情報であれば、保証期限の日付などでも良い。再署名用情報登録部１６０は、入力された保証期間が、予め定められた期間より短いか否かの保証期間判定処理を行う（ステップＳ１０４）。再署名用情報登録部１６０は、保証期間が短いと判定すれば、乱数（ｋ1）と第１の演算結果（ｒｉ）とを再署名用情報として再署名用情報記憶部１２４に記憶させる（ステップＳ１０５）。
【００４１】
すなわち、再署名用情報登録部１６０は、電子署名の保証期間が短期間である電子署名処理に用いた乱数（ｋ1）と第１の演算結果（ｒｉ）とを優先的に再署名用情報記憶部１２４に記憶させる。これは、保証期間が短期間であれば、暗号関数の危殆化による再署名処理を行う確率は低いと考えることができ、また、保証期間が長い電子署名は攻撃可能性のある時間も長いため、保証期間が短い電子署名処置に用いた乱数（ｋ1）と第１の演算結果（ｒｉ）を用いることが望ましい。
【００４２】
このように、再署名用情報記憶部１２４には、保証期間が短期間である再署名用情報が優先して記憶される構成とすることで、再署名処理による電子署名を、より安全なものとすることができる。なお、再署名用情報登録部１６０は、このような保証期間判定処理は行わずに、全ての乱数（ｋ1）と第１の演算結果（ｒｉ）とを再署名用情報として再署名用情報記憶部１２４に記憶させることとしても良い。なお、ステップＳ１０５で再署名用情報を再署名用情報記憶部１２４に記憶させる際は、再利用フラグはＯＦＦとして記憶させる。
【００４３】
そして、ユーザは、配布先入力部１７２に、配布先情報を入力する。配布先情報は、生成した電子署名文書の配布先を特定する情報であり、例えば、メールアドレスである。そして、署名処理部１１０は、生成した電子署名（σｉ）に対応する識別情報を生成して、入力された配布先情報と対応づけて配布先記憶部１２２に記憶させる（ステップＳ１０６）。
【００４４】
そして、署名処理部１１０は、通信部１３０を介して、メッセージ（Ｍ）と、メッセージ（Ｍ）に対応して生成した電子署名（σｉ）との情報である電子署名文書（Ｍ、σｉ）を、配布先情報に基づいて検証装置２００に送信する。（ステップＳ１０７）。
検証装置２００の通信部２１０が、電子署名文書（Ｍ、σｉ）を受信すると、署名検証部２３０は、電子署名文書の検証処理を行う（ステップＳ１０８）。検証処理は、公開鍵（ｇ）と公開鍵（ｙ）と公開鍵（ｐ）とハッシュ関数（ｈ１）とを用いた以下式（９）によって行うことができる。
【００４５】
【数９】
2008258661.tif 000011
【００４６】
次に、ハッシュ関数（ｈ１）の危殆化が発生した場合の再署名処理について説明する。危殆化が発生すると、通信部１３０が、危殆化したハッシュ関数を用いて電子署名処理を行った電子署名の配布先である検証装置２００に危殆化通知情報を送信する（ステップＳ２０１）。また、危殆化通知情報には、署名者名、再署名の実施期間、再署名の必要な電子署名文書などの情報を含むこととしても良い。
【００４７】
検証装置２００は、危殆化通知情報を受信すると、通知された危殆化したハッシュ関数を用いて生成された電子署名文書（Ｍ、σｉ）を記憶部２２０から読み出し、電子署名装置１００に送信する（ステップＳ２０２）。
電子署名装置１００が、再署名対象である電子署名文書（Ｍ、σｉ）を受信すると、署名検証部１４０が、上記式（９）によって電子署名文書の検証処理を行う（ステップＳ２０３）。
【００４８】
上記式（９）の左辺と右辺とが一致すれば、再署名付与部１１２は、再署名用情報記憶部１２４に記憶された再署名用情報のうち、再利用フラグがＯＦＦである再署名用情報を読み出す（ステップＳ２０４、ステップＳ２０６）。また、この際、ステップＳ２０６で再署名付与部１１２が読み出す再署名用情報は、再署名対象である電子署名文書（Ｍ、σｉ）に用いられた再署名用情報以外の複数の再署名用情報を、ランダムに読み出す。ここで、読み出される再署名用情報は少なくとも２個以上であり、個数が増えるほど結託攻撃に強くなり、安全性は高くなる。この際、再署名付与部１１２は、読み出した再署名用情報に対応する再署名利用フラグをＯＮの状態にして再署名用情報記憶部１２４に記憶させる（ステップＳ２０５）。
そして、再署名付与部１１２は、以下式（１０）によって再署名用情報が含む乱数の組み合わせ処理を行う（ステップＳ２０７）。
【００４９】
【数１０】
2008258661.tif 000012
【００５０】
ここで、Ｓｉは、再署名用情報記憶部１２４に記憶された再署名用情報の部分集合であり、ｋｉ＿ｓｕｂｓｅｔは、再署名用情報記憶部１２４からランダムに選ばれた複数の再署名用情報が含む乱数であることを示す。
図８に、３人の検証者（検証者Ａ、検証者Ｂ、検証者Ｃ）に対して電子署名を配布し、１人の検証者（検証者Ａ）に対して再署名処理を行うときの各式の具体例を示す。図８の例では、検証者Ａ、検証者Ｂ、検証者Ｃに対して、それぞれｋ１、ｋ２、ｋ３の乱数が生成される。式（１０）は、図８の例では、ｋｒｅｓｉｇｎ＝ｋ２＋ｋ３として算出することができる。
そして、再署名付与部１１２は、以下式（１１）によって組み合わせ情報（ｒ´ｊ）を算出する。
【００５１】
【数１１】
2008258661.tif 000013
【００５２】
すなわち、図８に示すような場合では、準同型性により、ｒ２×ｒ３の結果がＦ（ｇｋ２＋ｋ３）と一致するため、ｒ２×ｒ３の計算を行えば良い。
ここで、式（７）により算出する第１の演算結果には、準同型性を有する関数Ｆを用いているため、複数の第１の演算結果を乗じた結果を、複数の乱数（ｋｉ）について公開鍵（ｇ）を底として乱数（ｋｉ）を底とする、べき乗数の剰余演算結果を乗じた結果と一致させることができる。すなわち、再署名付与部１１２は、準同型性を持った関数を用いた複数の第１の演算結果を乗じることで、再署名の際に新たにべき乗剰余演算を行うことなく、べき乗剰余演算を行ったと同様の演算結果を生成することができる。
そして、再署名付与部１１２は、上記組み合わせ情報（ｒ´ｊ）を用いて、以下式（１２）によって第２の演算結果（ｔｊ）を算出する（ステップＳ２０８）。
【００５３】
【数１２】
2008258661.tif 000014
【００５４】
例えば、図８に示す例では、以下式（１３）で第２の演算結果（ｔｒｅｓｉｇｎ）を算出する。
【００５５】
【数１３】
2008258661.tif 000015
【００５６】
そして、署名処理部１１０は、上記で生成された再署名（σ´ｊ＝（ｒ´ｊ、ｔ´ｊ））が付与された電子署名文書（Ｍ、σ´ｊ）を、検証装置２００に送信する（ステップＳ２０９）。検証装置２００は、電子署名文書（Ｍ、σ´ｊ）を受信すると、以下式（１４）にて電子署名文書（Ｍ、σ´ｊ）の検証処理を行う（ステップＳ２１０）。
【００５７】
【数１４】
2008258661.tif 000016
【００５８】
このように、本発明は、ハッシュ関数が危殆化した際に生じる署名の安全性低下の問題を解決するために、準同型性を有する一方向性関数を用い、署名に利用した乱数と、べき乗剰余演算結果を記憶しておき、再署名の必要があった場合、記憶していた乱数・べき乗剰余演算結果の組み合わせを用いて再度署名することにより、再署名時の計算の効率化を行う。
【００５９】
なお、本発明における処理部の機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより再署名を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータシステム」は、ホームページ提供環境（あるいは表示環境）を備えたＷＷＷシステムも含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。
【００６０】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【図面の簡単な説明】
【００６１】
【図１】本発明の一実施形態による再署名の動作例を示す図である。
【図２】本発明の一実施形態による電子署名装置の構成を示すブロック図である。
【図３】本発明の一実施形態による検証装置の構成を示すブロック図である。
【図４】本発明の一実施形態による再署名用情報記憶部１２４の構成を示す図である。
【図５】本発明の一実施形態による再署名の動作例を示すシーケンス図である。
【図６】本発明の一実施形態による再署名の動作例を示すシーケンス図である。
【図７】本発明の一実施形態による計算式を示す図である。
【図８】本発明の一実施形態による計算式を示す図である。
【図９】従来技術による再署名の動作例を示す図である。
【図１０】従来技術による再署名の計算式を示す図である。
【符号の説明】
【００６２】
１００  電子署名装置
１１０  署名処理部
１１１  署名付与部
１１２  再署名付与部
１２０  記憶部
１２１  メッセージ記憶部
１２２  配布先記憶部
１２３  鍵記憶部
１２４  再署名用情報記憶部
１３０  通信部
１４０  署名検証部
１５０  乱数生成部
１６０  再署名用情報登録部
１７０  入力部
１７１  保証期間入力部
１７２  配布先入力部
２００  検証装置
２１０  通信部
２２０  記憶部
２３０  署名検証部
【図１】
2008258661.tif 000017
【図２】
2008258661.tif 000018
【図３】
2008258661.tif 000019
【図４】
2008258661.tif 000020
【図５】
2008258661.tif 000021
【図６】
2008258661.tif 000022
【図７】
2008258661.tif 000023
【図８】
2008258661.tif 000024
【図９】
2008258661.tif 000025
【図１０】
2008258661.tif 000026