(57)【特許請求の範囲】
【請求項１】
署名者装置のｇ０生成部が、Ｚ＊ｐ（＝{１、・・・、ｐ−１}、ｐは素数）から１以外の値ｇ０をランダムに生成するステップと、
署名者装置の剰余べき乗演算部が、上記ｇ０を用いてｇをｇ＝ｇ０(p-1)/q mod ｐ（ｑは素数でｐ−１の約数）により算出するステップと、
署名者装置の乱数生成部が、Ｚｑ（＝{０、１、・・・、ｑ−１}）からランダムに２つの値ｓ，ｘを生成するステップと、
署名者装置の第１べき乗演算部が、ｈ＝ｇs mod ｐを算出するステップと、
署名者装置の第２べき乗演算部が、ｙ＝ｇx mod ｐを算出するステップと、
上記ｈと上記ｙとをマスタ検証鍵として、登録センタ装置に、その外部の装置からアクセス可能に保存するステップと、
署名者装置のセッション鍵生成部が、上記ｈ，ｙ，ｇ，ｓを用いてセッション検証鍵を生成するステップと、
上記セッション検証鍵を署名者装置の記憶部に保存するステップと、
上記ｓと上記ｘとをセッション署名鍵とし、署名者装置の記憶部に保存するステップと、
署名者装置の署名作成部が、メッセージｍに対して上記セッション署名鍵を用いて署名を作成するステップと、
署名者装置の通信部が、上記署名と上記セッション検証鍵と上記メッセージとを検証者装置に送信するステップと、
を実行し、
セッション更新時に、
署名者装置の鍵更新部が、ｈ＝ｇ´s´mod ｐ，ｙ＝ｇ´x´mod ｐを満たすｇ´，ｓ´，ｘ´を算出するステップと、
署名者装置の鍵更新部が、上記ｈ，ｙ，ｇ´，ｓ´を用いて新しいセッション検証鍵を生成するステップと、
上記ｓ´とｘ´とを新しいセッション署名鍵として署名者装置の記憶部に保存するステップと、
上記新しいセッション検証鍵を署名者装置の記憶部に保存するステップと、
を実行することを特徴とするフォワードセキュア電子署名方法。
【請求項２】
上記乱数ｓ，ｘは互いに異なり、
上記セッション検証鍵を生成するステップは、
署名者装置の乱数生成部が、乱数ｕを生成するステップと、
署名者装置の第３べき乗演算部が、ａ＝ｇuを計算するステップと、
署名者装置の第１ハッシュ関数演算部が、ａ，ｈ，ｙ，ｇのビット結合値に対しハッシュ関数Ｈによりハッシュ関数計算を行って、ハッシュ値ｅ＝Ｈ（ａ，ｈ，ｙ，ｇ）を求めるステップと、
署名者装置の第１剰余乗算・減算部が、上記ｕ，ｅ及びｓに対し、ｖ＝ｕ−ｅ・ｓ mod ｑを計算するステップと、
を具備し、
上記セッション検証鍵は上記ｖ，上記ｅ，上記ｇであり、
上記署名を作成するステップは、
署名者装置の乱数生成部が、乱数ｗを生成するステップと、
署名者装置の第４べき乗演算部が、ｂ＝ｇwを計算するステップと、
署名者装置の第２ハッシュ関数演算部が、ｂ，ｈ，ｙ，ｇ，ｍのビット結合値に対しハッシュ関数Ｈによりハッシュ関数計算をして、ハッシュ値ｃ＝Ｈ（ｂ，ｈ，ｙ，ｇ，ｍ）を求めるステップと、
署名者装置の第２剰余乗算・減算部が、上記ｗ，ｃ及びｘに対し、ｚ＝ｗ−ｃ・ｘ mod ｑを計算するステップと、
を具備し、
上記署名はｃとｚであり、
署名検証時に、
検証者装置の通信部が、上記メッセージと上記セッション検証鍵と上記署名とを受信するステップと、
検証者装置の第１検証部が、上記マスタ検証鍵を用い、ｈとｙが等しくないことを検証するステップと、
検証者装置の第２検証部が、ｈ，ｙ，ｇがそれぞれ１でないことを検証するステップと、
検証者装置の第５べき乗演算部が、ｇv を計算するステップと、
検証者装置の第６べき乗演算部が、ｈe を計算するステップと、
検証者装置の第１乗算部が、ｇv とｈe を乗算するステップと、
検証者装置の第３ハッシュ関数演算部が、ｇv ｈe ，ｈ，ｙ，ｇのビット結合値に対しハッシュ関数Ｈにより、Ｈ（ｇv ｈe ，ｈ，ｙ，ｇ）のハッシュ関数計算を行うステップと、
検証者装置の第１比較部が、上記第３ハッシュ関数演算部で算出されたハッシュ関数計算値とｅとが等しいことを検証するステップと、
検証者装置の第７べき乗演算部が、ｇz を計算するステップと、
検証者装置の第８べき乗演算部が、ｙc を計算するステップと、
検証者装置の第２乗算部が、ｇz とｙc を乗算するステップと、
検証者装置の第４ハッシュ関数演算部が、ｇzｙc ，ｈ，ｙ，ｇ，ｍのビット結合値に対しハッシュ関数Ｈにより、Ｈ（ｇzｙc ，ｈ，ｙ，ｇ，ｍ）のハッシュ関数計算を行うステップと、
検証者装置の第２比較部が、上記第４ハッシュ関数演算部で算出されたハッシュ関数計算値とｃとが等しいことを検証するステップと、
上記第１検証部がｈとｙが等しくないと判定し、上記第２検証部がｈ，ｙ，ｇがそれぞれ１でないと判定し、上記第１比較部が上記第３ハッシュ関数演算部で算出されたハッシュ関数計算値とｅとが等しいと判定し、第２比較部が上記第４ハッシュ関数演算部で算出されたハッシュ関数計算値とｃとが等しいと判定した場合に、検証者装置の検証結果出力部が、上記ｖ，上記ｅ，上記ｇがマスタ検証鍵のセッション検証鍵であり、上記ｃ，上記ｚが上記メッセージのセッション検証鍵による署名であると認める信号を出力するステップと、
を実行し、
上記ｈ＝ｇ´s´mod ｐ，ｙ＝ｇ´x´mod ｐを満たすｇ´，ｓ´，ｘ´を算出するステップは、
署名者装置の乱数生成部が、乱数ｒを生成するステップと、
署名者装置の第９べき乗演算部が、ｇ´＝ｇrを計算するステップと、
署名者装置の第１剰余乗算部が、ｓ´＝ｒ-1・ｓ mod ｑを計算するステップと、
署名者装置の第２剰余乗算部が、ｘ´＝ｒ-1・ｘ mod ｑを計算するステップと、
を具備し、
上記新しいセッション検証鍵を生成するステップは、
署名者装置の乱数生成部が、乱数ｕ´を生成するステップと、
署名者装置の第１０べき乗演算部が、ａ´＝ｇ´u´を計算するステップと、
署名者装置の第５ハッシュ関数演算部が、ａ´，ｈ，ｙ，ｇ´のビット結合値に対しハッシュ関数Ｈによりハッシュ関数計算を行って、ハッシュ値ｅ´＝Ｈ（ａ´，ｈ，ｙ，ｇ´）を求めるステップと、
署名者装置の第３剰余乗算・減算部が、上記ｕ´，ｅ´及びｓ´に対し、ｖ´＝ｕ´−ｅ´・ｓ´mod ｑを計算するステップと、
を具備し、
上記新しいセッション検証鍵は上記ｖ´，上記ｅ´，上記ｇ´である、
ことを特徴とする請求項１記載のフォワードセキュア電子署名方法。
【請求項３】
署名者装置のｇ生成部が、有限体Ｆｐ上で定義される楕円曲線Ｅ上の点であって単位元を除く点ｇをランダムに生成するステップと、
署名者装置の乱数生成部が、Ｚｑ（＝{０、１、・・・、ｑ−１）からランダムに２つの値ｓ，ｘを生成するステップと、
署名者装置の第１楕円倍数演算部が、上記楕円曲線Ｅ上での点ｇのｓ倍算値ｈ＝ｓ・ｇを算出するステップと、
署名者装置の第２楕円倍数演算部が、上記楕円曲線Ｅ上での点ｇのｘ倍算値ｙ＝ｘ・ｇを算出するステップと、
上記ｈと上記ｙとをマスタ検証鍵として、登録センタ装置に、その外部の装置からアクセス可能に保存するステップと、
署名者装置のセッション鍵生成部が、上記ｈ，ｙ，ｇ，ｓを用いてセッション検証鍵を生成するステップと、
上記セッション検証鍵を署名者装置の記憶部に保存するステップと、
上記ｓと上記ｘとをセッション署名鍵とし、署名者装置の記憶部に保存するステップと、      
署名者装置の署名作成部が、メッセージｍに対して上記セッション署名鍵を用いて署名を作成するステップと、
署名者装置の通信部が、上記署名と上記セッション検証鍵と上記メッセージとを検証者装置に送信するステップと、
を実行し、
セッション更新時に、
署名者装置の鍵更新部が、ｈ＝ｓ´・ｇ´（上記楕円曲線Ｅ上での点ｇ´のｓ´倍算），ｙ＝ｘ´・ｇ´（上記楕円曲線Ｅ上での点ｇ´のｘ´倍算）を満たすｇ´，ｓ´，ｘ´を算出するステップと、
署名者装置の鍵更新部が、上記ｈ，ｙ，ｇ´，ｓ´を用いて新しいセッション検証鍵を生成するステップと、
上記ｓ´とｘ´とを新しいセッション署名鍵として署名者装置の記憶部に保存するステップと、
上記新しいセッション検証鍵を署名者装置の記憶部に保存するステップと、
を実行することを特徴とするフォワードセキュア電子署名方法。
【請求項４】
上記乱数ｓ，ｘは互いに異なり、
上記セッション検証鍵を生成するステップは、
署名者装置の乱数生成部が、乱数ｕを生成するステップと、
署名者装置の第３楕円倍数演算部が、上記楕円曲線Ｅ上での点ｇのｕ倍算値ａ＝ｕ・ｇを計算するステップと、
署名者装置の第１ハッシュ関数演算部が、ａ，ｈ，ｙ，ｇのビット結合値に対しハッシュ関数Ｈによりハッシュ関数計算を行って、ハッシュ値ｅ＝Ｈ（ａ，ｈ，ｙ，ｇ）を求めるステップと、
署名者装置の第１剰余乗算・減算部が、上記ｕ，ｅ及びｓに対し、ｖ＝ｕ−ｅ・ｓmod ｑを計算するステップと、
を具備し、
上記セッション検証鍵は上記ｖ，上記ｅ，上記ｇであり、
上記署名を作成するステップは、
署名者装置の乱数生成部が、乱数ｗを生成するステップと、
署名者装置の第４楕円倍数演算部が、上記楕円曲線Ｅ上での点ｇのｗ倍算値ｂ＝ｗ・ｇを計算するステップと、
署名者装置の第２ハッシュ関数演算部が、ｂ，ｈ，ｙ，ｇ，ｍのビット結合値に対しハッシュ関数Ｈによりハッシュ関数計算をして、ハッシュ値ｃ＝Ｈ（ｂ，ｈ，ｙ，ｇ，ｍ）を求めるステップと、
署名者装置の第２剰余乗算・減算部が、上記ｗ，ｃ及びｘに対し、ｚ＝ｗ−ｃ・ｘmod ｑを計算するステップと、
を具備し、
上記署名はｃとｚであり、
署名検証時に、
検証者装置の通信部が、上記メッセージと上記セッション検証鍵と上記署名とを受信するステップと、
検証者装置の第１検証部が、上記マスタ検証鍵を用い、ｈとｙとが等しくないことを検証するステップと、
検証者装置の第２検証部が、ｈ，ｙ，ｇがそれぞれ０でないことを検証するステップと、
検証者装置の第３ハッシュ関数演算部が、ｖ・ｇ＋ｅ・ｈ，ｈ，ｙ，ｇのビット結合値に対しハッシュ関数Ｈにより、Ｈ（ｖ・ｇ＋ｅ・ｈ，ｈ，ｙ，ｇ）のハッシュ関数計算を行うステップと、
検証者装置の第１比較部が、上記第３ハッシュ関数演算部で算出されたハッシュ関数計算値とｅとが等しいことを検証するステップと、
検証者装置の第４ハッシュ関数演算部が、ｚ・ｇ＋ｃ・ｙ ，ｈ，ｙ，ｇ，ｍのビット結合値に対しハッシュ関数Ｈにより、Ｈ（ｚ・ｇ＋ｃ・ｙ，ｈ，ｙ，ｇ，ｍ）のハッシュ関数計算を行うステップと、
検証者装置の第２比較部が、上記第４ハッシュ関数演算部で算出されたハッシュ関数計算値とｃとが等しいことを検証するステップと、
上記第１検証部がｈとｙが等しくないと判定し、上記第２検証部がｈ，ｙ，ｇがそれぞれ１でないと判定し、上記第１比較部が上記第３ハッシュ関数演算部で算出されたハッシュ関数計算値とｅとが等しいと判定し、第２比較部が上記第４ハッシュ関数演算部で算出されたハッシュ関数計算値とｃとが等しいと判定した場合に、検証者装置の検証結果出力部が、上記ｖ，上記ｅ，上記ｇがマスタ検証鍵のセッション検証鍵であり、上記ｃ，上記ｚが上記メッセージのセッション検証鍵による署名であると認める信号を出力するステップと、
を実行し、
上記ｈ＝ｓ´・ｇ´（上記楕円曲線Ｅ上での点ｇ´のｓ´倍算），ｙ＝ｘ´・ｇ´（上記楕円曲線Ｅ上での点ｇ´のｘ´倍算）を満たすｇ´，ｓ´，ｘ´を算出するステップは、
署名者装置の乱数生成部が、乱数ｒを生成するステップと、
署名者装置の第５楕円倍数演算部が、上記楕円曲線Ｅ上での点ｇのｒ倍算値ｇ´＝ｒ・ｇを計算するステップと、
署名者装置の第１剰余乗算部が、ｓ´＝ｒ-1・ｓ mod ｑを計算するステップと、
署名者装置の第２剰余乗算部が、ｘ´＝ｒ-1・ｘ mod ｑを計算するステップと、
を具備し、
上記新しいセッション検証鍵を生成するステップは、
署名者装置の乱数生成部が、乱数ｕ´を生成するステップと、
署名者装置の第６楕円倍数演算部が、上記楕円曲線Ｅ上での点ｇ´のｕ´倍算値ａ´＝ｕ´・ｇ´を計算するステップと、
署名者装置の第５ハッシュ関数演算部が、ａ´，ｈ，ｙ，ｇ´に対しハッシュ関数計算を行って、ｅ´＝Ｈ（ａ´，ｈ，ｙ，ｇ´）を求めるステップと、
署名者装置の第３剰余乗算・減算部が、上記ｕ´，ｅ´及びｓ´に対し、ｖ´＝ｕ´−ｅ´・ｓ´mod ｑを計算するステップと、
を具備し、
上記新しいセッション検証鍵は上記ｖ´，上記ｅ´，上記ｇ´である、
ことを特徴とする請求項３記載のフォワードセキュア電子署名方法。
【請求項５】
Ｚ＊ｐ（＝{１、・・・、ｐ−１}、ｐは素数）から１以外の値ｇ０をランダムに生成するｇ０生成部と、
上記ｇ０を用いてｇをｇ＝ｇ０(p-1)/q mod ｐ（ｑは素数でｐ−１の約数）により算出する剰余べき乗演算部と、
Ｚｑ（＝{０、１、・・・、ｑ−１}）からランダムに２つの値ｓ，ｘを生成する乱数生成部と、
ｈ＝ｇs mod ｐを算出する第１べき乗演算部と、
ｙ＝ｇx mod ｐを算出する第２べき乗演算部と、
上記ｈ，ｙ，ｇ，ｓを用いてセッション検証鍵を生成するセッション鍵生成部と、
メッセージｍに対して上記セッション署名鍵を用いて署名を作成する署名作成部と、
上記署名と上記セッション検証鍵と上記メッセージとを検証者装置に送信する通信部と、
を実行し、
セッション更新時に、ｈ＝ｇ´s´mod ｐ，ｙ＝ｇ´x´mod ｐを満たすｇ´，ｓ´，ｘ´を算出し、上記ｈ，ｙ，ｇ´，ｓ´を用いて新しいセッション検証鍵を生成する鍵更新部と、
上記ｓと上記ｘとをセッション署名鍵として、上記ｓ´とｘ´とを新しいセッション署名鍵として、これらを上記セッション検証鍵、上記新しいセッション検証鍵と共に保存する記憶部と
を具備するフォワードセキュア電子署名の署名者装置。
【請求項６】
上記乱数ｓ，ｘは互いに異なり、
上記セッション検証鍵生成部は、
乱数ｕを生成する乱数生成部と、
ａ＝ｇuを計算する第３べき乗演算部と、
ａ，ｈ，ｙ，ｇのビット結合値に対しハッシュ関数Ｈによりハッシュ関数計算を行って、ハッシュ値ｅ＝Ｈ（ａ，ｈ，ｙ，ｇ）を求める第１ハッシュ関数演算部と、
上記ｕ，ｅ及びｓに対し、ｖ＝ｕ−ｅ・ｓ mod ｑを計算する第１剰余乗算・減算部と、
を具備し、
上記セッション検証鍵は上記ｖ，上記ｅ，上記ｇであり、
上記署名作成部は、
乱数ｗを生成する乱数生成部と、
ｂ＝ｇwを計算する第４べき乗演算部と、
ｂ，ｈ，ｙ，ｇ，ｍのビット結合値に対しハッシュ関数Ｈによりハッシュ関数計算をして、ハッシュ値ｃ＝Ｈ（ｂ，ｈ，ｙ，ｇ，ｍ）を求める第２ハッシュ関数演算部と、
上記ｗ，ｃ及びｘに対し、ｚ＝ｗ−ｃ・ｘ mod ｑを計算する第２剰余乗算・減算部と、
を具備し、
上記署名はｃとｚであり、
上記鍵更新部は、
乱数ｒと乱数ｕ´とを生成する乱数生成部と、
ｇ´＝ｇrを計算する第９べき乗演算部と、
ｓ´＝ｒ-1・ｓ mod ｑを計算する第１剰余乗算部と、
ｘ´＝ｒ-1・ｘ mod ｑを計算する第２剰余乗算部と、
ａ´＝ｇ´u´を計算する第１０べき乗演算部と、
ａ´，ｈ，ｙ，ｇ´のビット結合値に対しハッシュ関数Ｈによりハッシュ関数計算を行って、ハッシュ値ｅ´＝Ｈ（ａ´，ｈ，ｙ，ｇ´）を求める第５ハッシュ関数演算部と、
上記ｕ´，ｅ´及びｓ´に対し、ｖ´＝ｕ´−ｅ´・ｓ´mod ｑを計算する第３剰余乗算・減算部と、
を具備し、
上記新しいセッション検証鍵は上記ｖ´，上記ｅ´，上記ｇ´である、
ことを特徴とする請求項５記載のフォワードセキュア電子署名の署名者装置。
【請求項７】
メッセージとセッション検証鍵と署名とを受信する通信部と、
公開されているｈとｙとを用い、ｈとｙとが等しくないことを検証する第１検証部と、
ｈ，ｙ，ｇがそれぞれ１でないことを検証する第２検証部と、
ｇv を計算する第５べき乗演算部と、
ｈe を計算する第６べき乗演算部と、
ｇv とｈe を乗算する第１乗算部と、
ｇv ｈe ，ｈ，ｙ，ｇのビット結合値に対しハッシュ関数Ｈにより、Ｈ（ｇv ｈe ，ｈ，ｙ，ｇ）のハッシュ関数計算を行う第３ハッシュ関数演算部と、
上記第３ハッシュ関数演算部で算出されたハッシュ関数計算値とｅとが等しいことを検証するの第１比較部と、
ｇz を計算する第７べき乗演算部と、
ｙc を計算する第８べき乗演算部と、
ｇz とｙc を乗算する第２乗算部と、
ｇzｙc ，ｈ，ｙ，ｇ，ｍのビット結合値に対しハッシュ関数Ｈにより、Ｈ（ｇzｙc ，ｈ，ｙ，ｇ，ｍ）のハッシュ関数計算を行う第４ハッシュ関数演算部と、
上記第４ハッシュ関数演算部で算出されたハッシュ関数計算値とｃとが等しいことを検証する第２比較部と、
上記第１検証部がｈとｙが等しくないと判定し、上記第２検証部がｈ，ｙ，ｇがそれぞれ１でないと判定し、上記第１比較部が上記第３ハッシュ関数演算部で算出されたハッシュ関数計算値とｅとが等しいと判定し、第２比較部が上記第４ハッシュ関数演算部で算出されたハッシュ関数計算値とｃとが等しいと判定した場合に、上記ｖ，上記ｅ，上記ｇがマスタ検証鍵のセッション検証鍵であり、上記ｃ，上記ｚが上記メッセージのセッション検証鍵による署名であると認める信号を出力する検証結果出力部と、
を備えるフォワードセキュア電子署名の検証者装置。
【請求項８】
有限体Ｆｐ上で定義される楕円曲線Ｅ上の点であって単位元を除く点ｇをランダムに生成するｇ生成部と、
Ｚｑ（＝{０、１、・・・、ｑ−１}）からランダムに２つの値ｓ，ｘを生成する乱数生成部と、
上記楕円曲線Ｅ上での点ｇのｓ倍算値ｈ＝ｓ・ｇを算出する第１楕円倍数演算部と、
上記楕円曲線Ｅ上での点ｇのｘ倍算値ｙ＝ｘ・ｇを算出する第２楕円倍数演算部と、
上記ｈ，ｙ，ｇ，ｓを用いてセッション検証鍵を生成するセッション鍵生成部と、
メッセージｍに対して上記セッション署名鍵を用いて署名を作成する署名作成部と、
上記署名と上記セッション検証鍵と上記メッセージとを検証者装置に送信する通信部と、
を実行し、
セッション更新時に、ｈ＝ｓ´・ｇ´（上記楕円曲線Ｅ上での点ｇ´のｓ´倍算），ｙ＝ｘ´・ｇ´（上記楕円曲線Ｅ上での点ｇ´のｘ´倍算）を満たすｇ´，ｓ´，ｘ´を算出し、上記ｈ，ｙ，ｇ´，ｓ´を用いて新しいセッション検証鍵を生成する鍵更新部と、
上記ｓと上記ｘとをセッション署名鍵として、上記ｓ´とｘ´とを新しいセッション署名鍵として、これらを上記セッション検証鍵、上記新しいセッション検証鍵と共に保存する記憶部と
を具備するフォワードセキュア電子署名の署名者装置。
【請求項９】
上記乱数ｓ，ｘは互いに異なり、
上記セッション検証鍵生成部は、
乱数ｕを生成する乱数生成部と、
上記楕円曲線Ｅ上での点ｇのｕ倍算値ａ＝ｕ・ｇを計算する第３楕円倍数演算部と、
ａ，ｈ，ｙ，ｇのビット結合値に対しハッシュ関数Ｈによりハッシュ関数計算を行って、ハッシュ値ｅ＝Ｈ（ａ，ｈ，ｙ，ｇ）を求める第１ハッシュ関数演算部と、
上記ｕ，ｅ及びｓに対し、ｖ＝ｕ−ｅ・ｓ mod ｑを計算する第１剰余乗算・減算部と、
を具備し、
上記セッション検証鍵は上記ｖ，上記ｅ，上記ｇであり、
上記署名作成部は、
乱数ｗを生成する乱数生成部と、
上記楕円曲線Ｅ上での点ｇのｗ倍算値ｂ＝ｗ・ｇを計算する第４楕円倍数演算部と、
ｂ，ｈ，ｙ，ｇ，ｍのビット結合値に対しハッシュ関数Ｈによりハッシュ関数計算をして、ハッシュ値ｃ＝Ｈ（ｂ，ｈ，ｙ，ｇ，ｍ）を求める第２ハッシュ関数演算部と、
上記ｗ，ｃ及びｘに対し、ｚ＝ｗ−ｃ・ｘ mod ｑを計算する第２剰余乗算・減算部と、
を具備し、
上記署名はｃとｚであり、
上記鍵更新部は、
乱数ｒと乱数ｕ´とを生成する乱数生成部と、
上記楕円曲線Ｅ上での点ｇのｒ倍算値ｇ´＝ｒ・ｇを計算する第５楕円倍数演算部と、
ｓ´＝ｒ-1・ｓ mod ｑを計算する第１剰余乗算部と、
ｘ´＝ｒ-1・ｘ mod ｑを計算する第２剰余乗算部と、
上記楕円曲線Ｅ上での点ｇ´のｕ´倍算値ａ´＝ｕ´・ｇ´を計算する第６楕円倍数演算部と、
ａ´，ｈ，ｙ，ｇ´のビット結合値に対しハッシュ関数Ｈによりハッシュ関数計算を行って、ハッシュ値ｅ´＝Ｈ（ａ´，ｈ，ｙ，ｇ´）を求める第５ハッシュ関数演算部と、
上記ｕ´，ｅ´及びｓ´に対し、ｖ´＝ｕ´−ｅ´・ｓ´mod ｑを計算する第３剰余乗算・減算部と、
を具備し、
上記新しいセッション検証鍵は上記ｖ´，上記ｅ´，上記ｇ´である、
ことを特徴とする請求項８記載のフォワードセキュア電子署名の署名者装置。
【請求項１０】
メッセージとセッション検証鍵と署名とを受信する通信部と、
公開されているｈとｙとを用い、ｈとｙとが等しくないことを検証する第１検証部と、
ｈ，ｙ，ｇがそれぞれ０でないことを検証する第２検証部と、
ｖ・ｇ＋ｅ・ｈ，ｈ，ｙ，ｇのビット結合値に対しハッシュ関数Ｈにより、Ｈ（ｖ・ｇ＋ｅ・ｈ，ｈ，ｙ，ｇ）のハッシュ関数計算を行う第３ハッシュ関数演算部と、
上記第３ハッシュ関数演算部で算出されたハッシュ関数計算値とｅとが等しいことを検証するの第１比較部と、
ｚ・ｇ＋ｃ・ｙ ，ｈ，ｙ，ｇ，ｍのビット結合値に対しハッシュ関数Ｈにより、Ｈ（ｚ・ｇ＋ｃ・ｙ，ｈ，ｙ，ｇ，ｍ）のハッシュ関数計算を行う第４ハッシュ関数演算部と、
上記第４ハッシュ関数演算部で算出されたハッシュ関数計算値とｃとが等しいことを検証する第２比較部と、
上記第１検証部がｈとｙが等しくないと判定し、上記第２検証部がｈ，ｙ，ｇがそれぞれ１でないと判定し、上記第１比較部が上記第３ハッシュ関数演算部で算出されたハッシュ関数計算値とｅとが等しいと判定し、第２比較部が上記第４ハッシュ関数演算部で算出されたハッシュ関数計算値とｃとが等しいと判定した場合に、上記ｖ，上記ｅ，上記ｇがマスタ検証鍵のセッション検証鍵であり、上記ｃ，上記ｚが上記メッセージのセッション検証鍵による署名であると認める信号を出力する検証結果出力部と、
を備えるフォワードセキュア電子署名の検証者装置。
【請求項１１】
請求項５、６、８、９のいずれかに記載の署名者装置として、コンピュータを機能させるためのプログラム。
【請求項１２】
請求項７、１０のいずれかに記載の検証者装置として、コンピュータを機能させるためのプログラム。
【請求項１３】
請求項１１、１２のいずれかに記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、電子化された文書の稟議／決済、電子投票システム等で、電子的に署名／捺印を付与する電子署名方法、特にマスタ検証鍵を更新せずに、セッション署名鍵のみを更新する前方安全（Forward-Secure）署名方法、その装置及びそのプログラムと記録媒体に関する。
【０００２】
【従来の技術】
従来技術として多数の電子署名方法が知られている。
最近、Forward-Secure（前方安全）署名と呼ばれる新たな電子署名が注目を浴びている［文献１〜４］。この署名の特徴は、マスタ検証鍵を更新せずに、セッション署名鍵のみを更新することが出来、更に、仮にあるセッションの署名鍵を盗まれたとしてもそのセッション以前の署名鍵によって作られた署名を安全に保てるという特徴がある。
まず、誰もが考えつく単純な方法を説明し、次に最初のForward-Secure署名である文献［２］に示すものとその他の方法について簡単に述べる。
単純な構成法
（その１）  署名者は、（ｐｋ1 ，ｓｋ1 ），…，（ｐｋT ，ｓｋT ）と検証鍵と署名鍵の対をＴ個作成し、検証鍵ｐｋ1 ，…，ｐｋT を登録し、署名鍵（ｓｋ1 ，…，ｓｋT ）を秘密に保持する。署名者は最初の期間はｓｋ1 を署名鍵、ｐｋ1 をセッション検証鍵として署名をする。鍵の更新時には、署名鍵をｓｋi からｓｋi+1 に変更し、ｓｋi を破棄してしまう。
【０００３】
この方法の欠点は、最初に多数の検証鍵と署名鍵を持つ必要がある上に、署名鍵更新回数が限られている。
（その２）  署名者は、（ｐｋ1 ，ｓｋ1 ）を検証鍵と署名鍵の対として作成し、検証鍵ｐｋ1 を登録し、署名鍵ｓｋ1 を秘密に保持する。署名者は最初の期間はｓｋ1 を署名鍵、ｐｋ1 をセッション検証鍵として署名をする。鍵の更新時には、新たに（ｐｋi+1 ，ｓｋi+1 ）を作成し、直前のセッション検証鍵ｐｋi を用いて、ｐｋi+1 を承認する署名σi ＝sigski(ｐｋi+1 )を生成し、また署名鍵をｓｋi からｓｋi+1 に変更し、ｓｋi を破棄してしまう。
【０００４】
ｐｋi+1 を検証するには、以前の全ての検証鍵を使ってσ1 ，…，σi を検証してやる必要がある。このため更新が進むにつれ、セッション検証鍵を検証するのに時間も情報量もかかることがこの方法の欠点である。
Bellare-Minerの構成法とその他
文献［２］の中で、Bellare-Minerは次のようにForward-Secure署名を構成した。
大きな異なる素数ｐ，ｑからＮ＝ｐｑを作る。Ｚ*nから乱数ｓ1 ，…，ｓk を選び、１＜ｉ＜ｋに対して、Ｕi ＝ｓi＾２T+1 mod Ｎ（ここでＡ＾ＢはＡB を表わす）を生成する。（Ｕ1 ，…，Ｕk Ｎ）をマスタ検証鍵として登録し、（ｓ1 ，…，ｓk ）を署名鍵として保存し、ｐ，ｑを廃棄する。
【０００５】
署名は、Feige-Fiat-Shamir署名で行う。鍵の更新は、セッションｊでの署名鍵をＳＫj ＝｛ｓｋ1j，…，ｓｋkj｝とすると（ｓｋi1＝ｓi ），ＳＫj+1 ＝｛（ｓｋ1j）2 mod Ｎ，…，（ｓｋkj）2 mod Ｎ｝と更新する。
この方法は、上の２つの方法、特に（その１）と比べると優れているが、署名鍵更新回数が限られているという欠点がある。つまり鍵の更新をＴ回行うと、ｓi＾２T となり、Ｔ＋１回目ではマスタ鍵となってしまう。
その他にも、文献［１，３，４］等に示す方法が存在するが、署名鍵更新回数が限られていたり、署名更新回数に応じて計算量が増えるなどの欠点が存在する。文献［４］に示す方法は、更新回数に制限が無い一般的なForward-Secure署名の構成法を提案しているが、この方法は非効率で署名の更新回数に依存して計算量が変化する。
【０００６】
【発明が解決しようとする課題】
上記のように、従来の方法では署名鍵更新回数が限られていたり、署名更新回数に応じて計算量が増えるなどの欠点が存在する。この発明の目的は効率が、署名更新回数に依存せず、一度の署名も従来のFeige-Fiat-Shamir型署名の効率と同等であり、かつ署名鍵更新回数が限られないForward-Secure署名方法、その装置、そのプログラム及び記録媒体を提供することにある。
【０００７】
【課題を解決するための手段】
Ｇを離散対数問題に利用される群として、その群演算を乗法で表すとき、署名者装置は、Ｇの元ｇに対して、ｈ＝ｇs とｙ＝ｇx を満たすｓ，ｘを生成し、（ｈ，ｙ）をマスタ検証鍵として公開し、ｈ，ｙ，ｇ，ｓに基づきセッション検証鍵を生成し、（ｓ，ｘ）をセッション署名鍵とし、これらのセッション鍵を保存し、
メッセージｍに対して、セッション署名鍵（ｓ，ｘ）により署名を作成し、その署名とセッション検証鍵とメッセージを検証者装置に送信し、
セッション更新時には、ｈ＝ｇ′s′，ｙ＝ｇ′x′を満たすようなｇ′，ｓ′，ｘ′にｇ，ｓ，ｘを変更し、上記セッション検証鍵の生成と、同様にしてｈ，ｙ，ｇ′，ｓ′に基づき新しいセッション検証鍵を生成し、（ｓ′，ｘ′）を新しいセッション署名鍵として保存中のセッション鍵を更新する。
【０００８】
【発明の実施の形態】
以下、この発明の実施形態を図を参照して説明する。
図１にこの発明方法が適用されるシステムの構成例を示す。署名者装置１００と検証者装置２００は安全でない通信路３００を介して結合することができる。署名者装置１００は登録センタ装置４００に署名者装置の公開鍵を登録することができ、検証者装置２００は登録センタ装置４００から署名者装置１００の公開鍵を取得することができる。
実施例１
この発明の実施例は有限体上の乗法群の離散対数問題に安全性の根拠を置くものである。つまり離散対数問題に利用される群としてその群演算を乗法で表す場合である。
（１）鍵の登録
大きな素数ｐとｐ−１を割る大きな素数ｑが公開パラメータとして登録センタ装置４００に登録公開してある。署名者装置１００の機能構成例を図２に示し、その処理手順を図３に示す。
【０００９】
署名者装置１００がシステムに加入するとき、マスタ鍵生成部１０１内の乱数生成部１０２によりＺ*p（＝｛１，…，ｐ−１｝）から１以外の値ｇ0 をランダムに生成し（Ｓ１）、そのｇ0 に対し（ｐ−１）／ｑ乗を剰余べき乗演算部１０３で計算する（Ｓ２）。その演算結果をｇ＝ｇ0(p-1)/qmod ｐとする。
次に、乱数生成部１０４によりＺq(＝｛０，１，…，ｑ−１｝）からランダムに二つの値ｓ，ｘを生成する（Ｓ３）。剰余べき乗演算部１０５，１０６でそれぞれ、ｇのｓ乗、ｘ乗をそれぞれ演算してマスタ公開検証鍵ｈ＝ｇs mod ｐとｙ＝ｇx mod ｐを求める（Ｓ４）。これらマスタ公開検証鍵ｈ，ｙを登録センタ装置４００の公開検証鍵簿４００ａに登録する（Ｓ５）。公開検証鍵簿４００ａには署名者Ａごとのマスタ公開検証鍵ｈ，ｙが登録され、外部から誰れでもアクセス可能とされる。
（２）セッション署名鍵の作成
署名者装置１００は乱数生成部１０４により乱数ｕ∈Ｚq を生成し（Ｓ６）、セッション鍵生成部１１１におけるべき乗演算部１１２でｇのｕ乗してａ＝ｇu を計算する（Ｓ７）。更にハッシュ関数演算部１１３でａ，ｇ、マスタ検証鍵ｈ，ｙ、公開パラメータｐ，ｑが入力され、ｅ＝Ｈ（ａ，ｈ，ｙ，ｐ，ｑ，ｇ）を計算する（Ｓ８）。このハッシュ演算結果ｅ、上記乱数ｕ及びｓを用いて、剰余乗算・減算部１１４でｖ＝ｕ−ｅｓmod ｑを計算する（Ｓ９）。
【００１０】
（ｖ，ｅ，ｇ）をセッション検証鍵、（ｓ，ｘ）をそのセッション署名鍵とし記憶部１２１に保存する（Ｓ１０）。（ｓ，ｘ）は秘密情報である。
（３）署名の作成
以降では、署名者装置１００がメッセージｍに署名する場合について説明する。
メッセージｍは入力部１２２から入力され、必要に応じて一旦記憶部１２１に格納される。メッセージｍが入力され署名作成要求がなされたかを調べ（Ｓ１１）、要求されていれば、まず乱数生成部１０４から乱数ｗ∈Ｚ*qを生成し（Ｓ１２）、署名作成部１３１におけるべき乗演算部１３２でｇをｗ乗してｂ＝ｇw を計算する（Ｓ１３）。その計算結果ｂ、マスタ検証鍵ｈ，ｙ、上記ｇ、メッセージｍをハッシュ関数演算部１３３でハッシュ演算を施し、ｃ＝Ｈ（ｂ，ｈ，ｙ，ｐ，ｑ，ｇ，ｍ）を計算する（Ｓ１４）。この計算結果ｃ、上記乱数ｗ，ｃ及びセッション署名鍵ｘを剰余乗算・減算部１３４に入力してｚ＝ｗ−ｃｘmod ｑを計算する（Ｓ１５）。この計算結果ｃと上記ｚをｍに対する署名（ｃ，ｚ）として、ｍ，（ｃ，ｚ）とセッション検証鍵（ｖ，ｅ，ｇ）を検証者装置２００に通信部１４１より送信する（Ｓ１６）。
（４）署名の検査
検証者装置２００は、図４に示すように通信部２０１にｍ，（ｃ，ｚ），（ｖ，ｅ，ｇ）と共に検証要求が受信されると、必要に応じてこれら受信情報を記憶部２０２に一旦格納する。検証者装置２００は、署名者Ａ（署名者装置１００）のマスタ公開検証鍵ｈ，ｙを登録センタ装置４００から取得し、これらｈ，ｙがｈ≠ｙであることを検証部２０３で、またｈ，ｙ、及び受信したｇが１でないことを検証部２０４で検証する。これらの条件は鍵登録時にｇ0 を１以外の値から選んだこと、２つのｓ，ｘを選んだことに基づく。
【００１１】
更にセッション鍵検証部２０５のべき乗演算部２０６，２０７でそれぞれ受信したｇを受信したｖでべき乗し、またマスタ検証鍵ｈを受信したｅでべき乗し、これらべき乗結果を乗算部２０８で乗算する。この乗算結果とｈ，ｙ，ｐ，ｑ，ｇとをハッシュ関数演算部２０９に入力してハッシュ演算を施し、この演算結果Ｈ（ｇv ｈe ，ｈ，ｙ，ｐ，ｑ，ｇ）と受信したｅとが一致するかを比較部２１１で確認する。
同様に署名検証部２１３において、べき乗演算部２１４，２１５でｇz ，ｙc を演算し、これら結果を乗算部２１６で乗算し、この乗算結果と、ｈ，ｙ，ｐ，ｑ，ｇ，ｍに対し、ハッシュ関数演算部２１７でハッシュ演算を施し、この結果が受信したｃと一致するかを比較部２１８で確認する。
【００１２】
検証部２０３，２０４，２０５，２１３の全ての検証に合格すれば、検証結果出力部２１９から、受信した（ｖ，ｅ，ｇ）をマスタ検証鍵（ｈ，ｙ）に基づくセッション検証鍵であると認め、かつ（ｃ，ｚ）をメッセージｍのセッション検証鍵（ｖ，ｅ，ｇ）での署名と認め、合格（ＯＫ）を表わす信号を出力し、一つでも検証に合格しないものは、不正な署名として不合格（ＮＧ）を表わす信号を出力する。
なお、（ｖ，ｅ，ｇ）が正しければ、ｖ＝ｕ−ｅｓ，ｈ＝ｇs であるからｇv ｈe ＝ｇu-esｇes＝ｇu 、べき乗演算部１１２（図２）よりｇu ＝ａである。よって演算部２０９のハッシュ演算はＨ（ａ，ｈ，ｙ，ｐ，ｑ，ｇ）となり、演算部１１３の演算結果ｅと一致する。同様に（ｃ，ｚ）が正しければ、ｚ＝ｗ−ｃｘ，ｙ＝ｇx であるから、ｇz ｙc ＝ｇw-cxｇcx＝ｇw ＝ｂとなり、演算部２１７の演算はＨ（ｂ，ｈ，ｙ，ｐ，ｑ，ｇ，ｍ）となり、演算部１３３の演算結果ｃと一致する。
（５）署名鍵の更新
セッション署名鍵を更新する時になると（図３、Ｓ１７）、例えば、セッション署名鍵の生成後一定期間が過ぎた時あるいは所定回数使用した時などに署名者装置１００（図２参照）は乱数生成部１０４で乱数ｒ∈Ｚqを生成し（Ｓ１８）、鍵更新部１４２におけるべき乗演算部１４３でｇ´＝ｇr を演算し、剰余乗算部１４４，１４５でそれぞれ乱数ｒの逆数ｒ-1とセッション署名鍵ｓ，ｘとをそれぞれ剰余演算し、ｓ´＝ｒ-1ｓmod ｑ，ｘ´＝ｒ-1ｘmod ｑを求める（Ｓ１９）。これら（ｓ´，ｘ´）にセッション署名鍵を更新する。
【００１３】
新しいセッション検証鍵は以下のように作成する。乱数生成部１０４から乱数ｕ′∈Ｚ*qを生成し（Ｓ２０）、ａ′＝ｇ′u′べき乗演算部１４６で計算し（Ｓ２１）、ハッシュ関数演算部１４７を用いて、ｅ′＝Ｈ（ａ′，ｈ，ｙ，ｐ，ｑ，ｇ′）を計算し（Ｓ２２）、上記ｕ′，ｅ′及びｓ′を用いて、剰余乗算・減算部１４８でｖ′＝ｕ′−ｅ′ｓ′mod ｑを計算する（Ｓ２３）。
（ｖ′，ｅ′，ｇ′）を新しいセッション検証鍵、（ｓ′，ｘ′）を新しいセッション署名鍵として記憶部１２１に保存し、古いセッション署名鍵（ｓ，ｘ）は破棄してステップＳ１１に戻る（Ｓ２４）。ステップＳ１７で更新時になければステップＳ１１へ移る。よってその後のメッセージｍに対する署名は（ｓ′，ｘ′）、（ｖ′，ｅ′，ｇ′）を、署名作成部１３１でｓ，ｘ，ｖ，ｅ，ｇとして用いて署名ｃ，ｚの作成を行い、また検証者装置２００へセッション検証鍵を（ｖ，ｅ，ｇ）として送る。
【００１４】
以上のようにセッション鍵を更新するため、何回でも更新を行うことができる。ｇ及びその変更したｇ´＝ｇr は外部へ出力するがｇ´，ｇからｒを推定することは離散対数問題であって困難である。従って安全性は保持される。また仮にセッション署名鍵ｓ´，ｘ´が盗まれても、その前のセッション鍵をｓ＝ｒｓ´，ｘ＝ｒｘ´により求めるにはｒを知る必要があり、このｒを知ることは困難であるため、盗まれる前に行われた署名について偽造されるおそれはない。
またｙ＝ｈx/s mod p＝ｈx´/s´mod pでありｈ＝ｇs mod p，ｙ＝ｇx mod p，ｙ＝ｈx/s mod pの関係を知っている人のみがｘ´，ｓ´を作ることができ、ｈ＝ｇ´s´mod p，ｙ＝ｇ´x´mod p，ｙ＝ｈx´/s´mod pの関係を満たすようにｇ´，ｓ´，ｘ´を更新すればよい。
【００１５】
なお署名者装置１００において各部は制御部１４９により順次動作させられる。検証者装置２００においては制御部２３０により各部が動作させられる。
実施例２
この発明の実施例２は楕円曲線上の有理点が作る群上で構成できる離散対数問題を安全性の根拠とする場合である。
（１）鍵の登録
有限体Ｆp 上で定義される楕円曲線ＥのＦp-有理点の作る群をＥ（Ｆp）とし、その群Ｅ（Ｆp）の位数を割る大きな素数ｑを位数に持つ部分群をＧと置く（Ｇ⊂Ｅ（Ｆp）かつｑ｜＃Ｅ（Ｆp）である）。上記は公開パラメータとして登録センタ装置４００に登録公開してある。図５に署名者装置１００の機能構成例を示す。
【００１６】
署名者装置１００がシステムに加入するときマスタ鍵生成部１５０内の乱数生成部１５１でＧ−｛０｝（｛０｝は単位元を表す）から値ｇをランダムに生成する。乱数生成部１５２により、Ｚq(＝｛０，１，…，ｑ−１｝)からランダムに二つの値ｓ，ｘを生成し、楕円倍数演算部１５３，１５４でｈ＝ｓ・ｇとｙ＝ｘ・ｇを計算してマスタ検証鍵を求める。ただし、ｓ・ｇ，ｘ・ｇは楕円曲線上の点ｇのｓ倍算、ｘ倍算をそれぞれ表わしている。さらにｇ，ｈ∈Ｇ上の加法演算をｇ＋ｈで表わす。
これらマスタ検証鍵ｈ，ｙを登録センタ装置４００の公開検証鍵簿４００ａに登録する。
（２）セッション署名鍵の作成
署名者装置１００は、乱数生成部１５２により乱数ｕ∈Ｚq を生成し、セッション鍵生成部１５６内の楕円倍数演算部１５７でｇをｕ倍算してａ＝ｕ・ｇを計算し、その計算結果ａ、マスタ検証鍵ｈ，ｙ，ｇ，Ｇをハッシュ関数演算部１５８に入力して、ｅ＝Ｈ（ａ，ｈ，ｙ，Ｇ，ｇ）を計算し、上記ｕ，ｅ及びｓを剰余乗算・減算部１５９に入力してｖ＝ｕ−ｅｓ mod ｑを計算する。
【００１７】
（ｖ，ｅ，ｇ）をセッション検証鍵、（ｓ，ｘ）をそのセッション署名鍵として記憶部１６１に保存する。
（３）署名の作成
以降では、署名者装置１００がメッセージｍに署名する場合について説明する。
メッセージｍは入力部１６２から入力され、必要に応じて一旦記憶部１６１に格納される。乱数生成部１５２から、乱数ｗ∈Ｚq を生成し署名作成部１６３内の楕円倍数演算部１６４にｗ，ｇを入力してｂ＝ｗ・ｇを計算し、このｂとｈ，ｙ，Ｇ，ｇ，ｍをハッシュ関数演算部１６５に入力して、ｃ＝Ｈ（ｂ，ｈ，ｙ，Ｇ，ｇ，ｍ）を計算する。この計算結果ｃ、上記ｗ及びｘを剰余乗算・減算部１６６に入力してｚ＝ｗ−ｃｘ mod ｑを計算し、その計算結果ｚとｃを署名（ｃ，ｚ）として、セッション検証鍵（ｖ，ｅ，ｇ）と共に検証者装置２００と通信部１６７により送信する。
（４）署名の検査
検証者装置２００は、図６に示すように通信部２４０にｍ，（ｃ，Ｚ）（ｖ，ｅ，ｇ）が受信されると必要に応じて、これらを一旦記憶部２４１に格納する。署名者装置１００のマスタ公開検証鍵ｈ，ｙを登録センタ装置４００から取得し、これらがｈ≠ｙであることを検証部２４２で検証し、またｈ，ｙ，ｇが何れも０でないことを検証部２４３で検証する。更にセッション鍵検証部２４４内のハッシュ関数演算部２５３でＨ（ｖ・ｇ＋ｅ・ｈ，ｈ，ｙ，Ｇ，ｇ）を演算し、その演算結果が受信したｅと一致するかを比較部２５６で確認し、署名検証部２５７内のハッシュ関数演算部２５８でＨ（ｚ・ｇ＋ｃ・ｈ，ｈ，ｙ，Ｇ，ｇ，ｍ）を演算し、その結果がｃと一致するかを比較部２５６で確認する。検証部２４２，２４３，２４４，２５７の各検証結果が検証結果出力部２６１に入力され、これらの検証結果が全て条件を満していれば（ｖ，ｅ，ｇ）を検証鍵（ｈ，ｙ）のセッション検証鍵と認め、かつ（ｃ，ｚ）をメッセージｍのセッション検証鍵（ｖ，ｅ，ｇ）での署名と認めることを表わす合格情報ＯＫを出力し、一つでも条件を満さない場合は不合格情報ＮＧを出力する。
（５）署名鍵の更新
セッション鍵を更新する時になると署名者装置１００は乱数生成部１５２から乱数ｒ∈Ｚq を生成し、鍵更新部１７５内の楕円倍数演算部１７６でｇ′＝ｒ・ｇを演算し、更に剰余乗算部１７７，１７８でそれぞれｓ′＝ｒ-1ｓmod ｑ，ｘ′＝ｒ-1ｘ mod ｑを計算してこれら（ｓ′，ｘ′）を新しいセッション署名鍵として更新する。乱数生成部１５２から乱数ｕ′∈Ｚq を生成し、楕円倍数演算部１７９でａ′＝ｕ′・ｇ′を計算し、更にハッシュ関数演算部１８１で、ｅ′＝Ｈ（ａ′，ｈ，ｙ，Ｇ，ｇ′）を計算し、上記ｕ′，ｅ′及びｓ′を用いて、剰余乗算・減算部１８２でｖ′＝ｕ′−ｅ′ｓ′mod ｑを計算する。（ｖ′，ｅ′，ｇ′）を新しいセッション検証鍵として（ｓ′，ｘ′）を新しいセッション署名鍵として記憶部１６１に保存し、古いセッション署名鍵（ｓ，ｘ）は破棄する。これら新しいセッション鍵（ｓ′，ｘ′），（ｖ′，ｅ′，ｇ′）を用いてメッセージｍに対する署名を作成するには、署名作成部１６３で（ｓ′，ｘ′）を（ｓ，ｘ）とし、（ｖ′，ｅ′，ｇ′）を（ｖ，ｅ，ｇ）として作成処理すればよい。
【００１８】
以上のようにしてセッション鍵を何回でも更新することができる。外部へ漏れるのはｇ，ｇ′であり、ｇ′＝ｒ・ｇであるから楕円離散対数問題に基づき、ｒを推定することは困難である。よって安全性が保持される。また仮りにセッション署名鍵が盗まれても、ｒを推定できないためそれより以前のセッション署名鍵を推定することができず、盗まれる前になされた署名の安全性は保持される。
またこの場合もｇ，ｇ′からｒを推定することは困難であり、ｙ＝ｘ・ｓ‐1・ｈ＝ｘ′・ｓ′‐1・ｈとなりｈ＝ｓ・ｇ，ｙ＝ｘ・ｇなる関係を知っている人のみがセッション鍵を更新することができる。
【００１９】
署名者装置１００において、各部は制御部１７０により順次動作させられる。検証者装置２００においては、各部は制御部２６３により順次動作させられる。
実施例１及び２において、マスタ検証鍵ｈ，ｙを生成するための乱数ｓ，ｘを最初のセッション署名鍵として使用したが最初のセッション署名鍵から鍵更新部１４２，１６５で生成してもよい。図２中の鍵更新部１４２中のａ′，ｅ′，ｖ′を演算する演算部１４６，１４７，１４８はセッション鍵生成部１１１中の演算部１１２，１１３，１１４とそれぞれ同一の演算式を実行するものであるから、鍵更新時に生成したｕ′，ｇ′，ｓ′，ｘ′をそれぞれｕ，ｇ，ｓ，ｘとして演算部１１２，１１３，１１４によりａ′，ｅ′，ｖ′を演算し、つまり演算部１４６，１４７，１４８を省略してもよい。このことは実施例２中の図５に示した署名者装置についても云えることであり、演算部１６９〜１７１，１７２を省略することもできる。このような点から例えば図３に示した処理手順において、ステップＳ１９からステップＳ６に移って、ｇ′，ｓ′，ｘ′をｇ，ｓ，ｘとして用いて新しいａ′，ｅ′，ｖ′を生成するようにしてもよい。
【００２０】
図２、図５に示した例において、べき乗算部、剰余乗算部、ハッシュ関数演算部、剰余乗算・減算部、楕円倍数演算部などを各１つずつ設け、これらを制御部１４９又は１７０の制御のもとに生成したいデータ元として必要とする各種データを入力して、各種データの生成に兼用するようにしてもよい。これらのことは図４、図６にそれぞれ示した検証者装置２００についても同様に云えることである。
上述の説明から明らかなように、ｈ＝ｇs，ｙ＝ｇxを満たす又はｈ＝ｓ・ｇ，ｙ＝ｘ・ｇを満たすｓ，ｘを生成し、（ｈ，ｙ）をマスタ公開鍵とし、セッション署名鍵は（ｓ，ｘ）それ自体、これらは前述のような関係で更新したものを用い、セッション検証鍵はｈ，ｙ，ｇ，ｓから作成したものを用いればよく、そのセッション鍵の更新は、ｈ＝ｇ′s′，ｙ＝ｇ′x′又はｈ＝ｓ′・ｇ′，ｙ＝ｘ′・ｇ′を満たすようなｇ′，ｓ′，ｘ′に変更すればよい。またセッション検証鍵は署名（ｃ，ｚ）の作成方法と同様な方法を、ｘの代わりにｓを用いてｈ，ｙ，ｇ，ｓに対して適用しているといえる。
【００２１】
実施例１及びこの各署名者装置１００、利用者装置２００はそれぞれコンピュータに機能させることもできる。その場合は、例えば図２に示した署名者装置１００としてコンピュータを機能させるためのプログラムをコンピュータに、ＣＤ−ＲＯＭ、可撓性磁気ディスクなどの記録媒体からインストールし、又は通信回線を介してダウンロードして、そのプログラムを実行させればよい。
署名作成法としては実施例１及び２に示した例に限らず、他の手法を用いてもよく、それに応じて、セッション検証鍵の生成法も変更される。
【００２２】
【発明の効果】
以上述べたようにこの発明によれば離散対数問題を利用するため、安全でかつセッション鍵を無限に更新することができ、しかも文献［２］に示す従来のもっとも効率的なForward-Secure電子署名方法と比較すると、Bellare-Miner法はマスタ検証鍵として（Ｕ1 ，…，Ｕk ，Ｎ）を持つ必要があるが、この発明では（ｈ，ｙ）だけであるから実施例１では計算量で同じ、情報量で２／（ｋ＋１）である。実施例２では楕円曲線上の離散対数問題を利用するので、ｈ，ｙのパラメータをさらに小さく出来、署名計算時間も短いから計算量で１／４、情報量で２／（ｋ＋１）以下である。
【図面の簡単な説明】
【図１】この発明方法が適用されるシステム構成の簡単な例を示す図。
【図２】この発明の実施例１における署名者装置１００の機能構成例を示す図。
【図３】図２に示した装置の処理手順の例を示す流れ図。
【図４】実施例１における検証者装置２００の機能構成例を示す図。
【図５】実施例２における署名者装置１００の機能構成例を示す図。
【図６】実施例２における検証者装置２００の機能構成例を示す図。
参考文献
[1] M.Abdalla and L.Reyzin. A new forward-secure digital signature scheme. In T.Okamoto,editor,Advances in Cryptology-ASIACRYPT2000,volume 1976 of Lecture Notes in Computer Science,pages 116-129. Springer-Verlag,2000.
[2] M.Bellare and S.Miner. A forward-secure digital signature scheme. In M.Wiener,editor,Advances in Cryptoloty-CRYPTO'99,volume 1666 of Lecture Notes in Computer Science,pages 431-448. Springer-Verlag,19999.
[3] H.Krawczyk. Simple forward-secure signatures from any signature scheme. In 7th ACM conference on Computer and Communications security,2000.
[4] T.Malkin,D.Micciancio,and S.Miner. Efficient generic forward-secure signatures with an unbounded number of time periods. In Advances in Cryptology-EUROCRYPT'02,Lecture Notes in Computer Science. Springer-Verlag,2002.
【図１】
0003939586.tif 000002
【図２】
0003939586.tif 000003
【図３】
0003939586.tif 000004
【図４】
0003939586.tif 000005
【図５】
0003939586.tif 000006
【図６】
0003939586.tif 000007