(57)【特許請求の範囲】
【請求項１】
Ｌｅａｋａｇｅ−Ｒｅｓｉｌｉｅｎｔ方式に基づくＬＲ署名鍵とＬＲ検証鍵とを生成する鍵生成アルゴリズムと、前記ＬＲ署名鍵を更新する鍵更新アルゴリズムと、入力されるメッセージと前記ＬＲ署名鍵とに基づいてＬＲ署名を生成する署名生成アルゴリズムとが記憶されている生成アルゴリズム記憶部と、
前記鍵生成アルゴリズムによって生成された前記ＬＲ署名鍵が記憶される鍵記憶部と、
前記鍵生成アルゴリズムに基づいて、複数の期間毎に対応付けられた前記ＬＲ署名鍵と前記ＬＲ検証鍵との組み合わせを生成し、生成した複数のＬＲ署名鍵を前記鍵記憶部に記憶させ、生成した複数のＬＲ検証鍵を出力する鍵生成部と、
期間更新要求が入力されると、前記鍵記憶部に記憶されている、前記複数の期間毎に対応付けられた前記ＬＲ署名鍵のうち、最も早い期間に対応付けられた前記ＬＲ署名鍵を削除し、削除されていない前記ＬＲ署名鍵を前記鍵更新アルゴリズムにより更新する期間更新部と、
入力されるメッセージと、前記鍵記憶部に記憶されている、前記複数の期間毎に対応付けられた前記ＬＲ署名鍵のうち、最も早い期間に対応付けられた前記ＬＲ署名鍵とに基づいて生成された前記ＬＲ署名を、前記メッセージに対するＦＳＬＲ署名として出力する署名生成部と、
を有する電子署名装置と、
前記Ｌｅａｋａｇｅ−Ｒｅｓｉｌｉｅｎｔ方式に基づくＬＲ署名を検証する検証アルゴリズムが記憶されている検証アルゴリズム記憶部と、
前記ＬＲ署名を生成した前記ＬＲ署名鍵に対応する前記ＬＲ検証鍵に基づいて、前記ＦＳＬＲ署名を検証する検証部と、
を有する検証装置と、
を備えることを特徴とする電子署名システム。
【請求項２】
鍵更新要求が入力されると、前記鍵記憶部に記憶されている複数の前記ＬＲ署名鍵を、前記鍵更新アルゴリズムにより更新する鍵更新部と、
を備えることを特徴とする請求項１に記載の電子署名システム。
【請求項３】
Ｌｅａｋａｇｅ−Ｒｅｓｉｌｉｅｎｔ方式に基づくＬＲ署名鍵とＬＲ検証鍵とを生成する鍵生成アルゴリズムと、前記ＬＲ署名鍵を更新する鍵更新アルゴリズムと、入力されるメッセージと前記ＬＲ署名鍵とに基づいてＬＲ署名を生成する署名生成アルゴリズムとが記憶されている生成アルゴリズム記憶部と、
複数の期間毎に、当該期間を識別する期間情報を対応付けた同レベルの複数の葉ノードを有する二分木の各ノードに、前記鍵生成アルゴリズムにより生成したＬＲ署名鍵とＬＲ検証鍵とを割り当て、前記二分木における葉ノード以外のノード毎に、親ノードに割り当てられたＬＲ署名鍵と、当該親ノードに対する双方の子ノードに割り当てられたＬＲ検証鍵を結合した情報とに基づいて前記署名生成アルゴリズムによりＬＲ署名を生成し、前記葉ノードに割り当てられた前記ＬＲ署名鍵と、当該葉ノードに対応付けられた前記期間情報とに基づいて前記署名生成アルゴリズムによりＬＲ署名を生成し、生成した複数の前記ＬＲ署名と、前記葉ノードに割り当てられたＬＲ署名鍵及びＬＲ検証鍵と、前記親ノードに対して左の子ノードに割り当てられたＬＲ検証鍵と、当該親ノードに対して右の子ノードに割り当てられたＬＲ署名鍵及びＬＲ検証鍵とを要素として含むＦＳＬＲ署名鍵を生成し、前記二分木における根ノードに割り当てた前記ＬＲ検証鍵を、当該ＦＳＬＲ署名鍵に対応するＦＳＬＲ検証鍵として出力する鍵生成部と、
期間更新要求が入力されると、前記二分木において最も左の葉ノードを削除し、当該葉ノード以外の各ノードに割り当てられた前記ＬＲ署名鍵と前記ＬＲ検証鍵と、当該ＬＲ署名鍵に基づいて生成された前記ＬＲ署名とに基づいて前記ＦＳＬＲ署名鍵を更新する期間更新部と、
前記期間更新要求が入力されると、前記二分木における各ノードに割り当てられた前記ＬＲ署名鍵を前記鍵更新アルゴリズムにより更新し、更新したＬＲ署名鍵が含まれる各ノードに割り当てられた前記ＬＲ署名鍵と前記ＬＲ検証鍵と、当該ＬＲ署名鍵に基づいて生成された前記ＬＲ署名とに基づいて前記ＦＳＬＲ署名鍵を更新する鍵更新部と、
入力されるメッセージと前記ＦＳＬＲ署名鍵が要素として含む前記葉ノードに割り当てた前記ＬＲ署名鍵とに基づいて前記署名生成アルゴリズムにより生成したＬＲ署名と、前記ＦＳＬＲ署名鍵が要素として含む前記ＬＲ署名であって、前記ノード毎のＬＲ署名鍵に基づいて生成された前記ＬＲ署名と、前記ＦＳＬＲ署名鍵が要素として含む前記ＬＲ検証鍵とを、前記メッセージに対するＦＳＬＲ署名として出力する署名生成部と、
を有する電子署名装置と、
前記Ｌｅａｋａｇｅ−Ｒｅｓｉｌｉｅｎｔ方式に基づくＬＲ署名を検証する検証アルゴリズムが記憶されている検証アルゴリズム記憶部と、
前記ＦＳＬＲ署名に含まれる全ての前記ＬＲ署名について検証が成功した場合に、検証成功と判定する検証部と、
を有する検証装置と、
を備えることを特徴とする電子署名システム。
【請求項４】
前記電子署名装置の前記鍵更新部は、鍵更新要求が入力されると、前記二分木における各ノードに割り当てられた前記ＬＲ署名鍵を、前記鍵更新アルゴリズムにより更新し、更新した当該ＬＲ署名鍵に基づいて前記ＦＳＬＲ署名鍵を生成する
ことを特徴とする請求項３に記載の電子署名システム。
【請求項５】
Ｌｅａｋａｇｅ−Ｒｅｓｉｌｉｅｎｔ方式に基づくＬＲ署名鍵とＬＲ検証鍵とを生成する鍵生成アルゴリズムと、前記ＬＲ署名鍵を更新する鍵更新アルゴリズムと、入力されるメッセージと前記ＬＲ署名鍵とに基づいてＬＲ署名を生成する署名生成アルゴリズムとが記憶されている生成アルゴリズム記憶部と、前記鍵生成アルゴリズムによって生成された前記ＬＲ署名鍵が記憶される鍵記憶部と、を有する電子署名装置が、
前記鍵生成アルゴリズムに基づいて、複数の期間毎に対応付けられた前記ＬＲ署名鍵と前記ＬＲ検証鍵との組み合わせを生成し、生成した複数のＬＲ署名鍵を前記鍵記憶部に記憶させ、生成した複数のＬＲ検証鍵を出力するステップと、
期間更新要求が入力されると、前記鍵記憶部に記憶されている、前記複数の期間毎に対応付けられた前記ＬＲ署名鍵のうち、最も早い期間に対応付けられた前記ＬＲ署名鍵を削除し、削除されていない前記ＬＲ署名鍵を前記鍵更新アルゴリズムにより更新するステップと、
入力されるメッセージと、前記鍵記憶部に記憶されている、前記複数の期間毎に対応付けられた前記ＬＲ署名鍵のうち、最も早い期間に対応付けられた前記ＬＲ署名鍵とに基づいて生成された前記ＬＲ署名を、前記メッセージに対するＦＳＬＲ署名として出力するステップと、
前記Ｌｅａｋａｇｅ−Ｒｅｓｉｌｉｅｎｔ方式に基づくＬＲ署名を検証する検証アルゴリズムが記憶されている検証アルゴリズム記憶部を有する検証装置が、
前記ＬＲ署名を生成した前記ＬＲ署名鍵に対応する前記ＬＲ検証鍵に基づいて、前記ＦＳＬＲ署名を検証するステップと、
を備えることを特徴とする電子署名方法。
【請求項６】
Ｌｅａｋａｇｅ−Ｒｅｓｉｌｉｅｎｔ方式に基づくＬＲ署名鍵とＬＲ検証鍵とを生成する鍵生成アルゴリズムと、前記ＬＲ署名鍵を更新する鍵更新アルゴリズムと、入力されるメッセージと前記ＬＲ署名鍵とに基づいてＬＲ署名を生成する署名生成アルゴリズムとが記憶されている生成アルゴリズム記憶部を有する電子署名装置が、
複数の期間毎に、当該期間を識別する期間情報を対応付けた同レベルの複数の葉ノードを有する二分木の各ノードに、前記鍵生成アルゴリズムにより生成したＬＲ署名鍵とＬＲ検証鍵とを割り当て、前記二分木における葉ノード以外のノード毎に、親ノードに割り当てられたＬＲ署名鍵と、当該親ノードに対する双方の子ノードに割り当てられたＬＲ検証鍵を結合した情報とに基づいて前記署名生成アルゴリズムによりＬＲ署名を生成し、前記葉ノードに割り当てられた前記ＬＲ署名鍵と、当該葉ノードに対応付けられた前記期間情報とに基づいて前記署名生成アルゴリズムによりＬＲ署名を生成し、生成した複数の前記ＬＲ署名と、前記葉ノードに割り当てられたＬＲ署名鍵及びＬＲ検証鍵と、前記親ノードに対して左の子ノードに割り当てられたＬＲ検証鍵と、当該親ノードに対して右の子ノードに割り当てられたＬＲ署名鍵及びＬＲ検証鍵とを要素として含むＦＳＬＲ署名鍵を生成し、前記二分木における根ノードに割り当てた前記ＬＲ検証鍵を、当該ＦＳＬＲ署名鍵に対応するＦＳＬＲ検証鍵として出力するステップと、
期間更新要求が入力されると、前記二分木において最も左の葉ノードを削除し、当該葉ノード以外の各ノードに割り当てられた前記ＬＲ署名鍵と前記ＬＲ検証鍵と、当該ＬＲ署名鍵に基づいて生成された前記ＬＲ署名とに基づいて前記ＦＳＬＲ署名鍵を更新するステップと、
前記期間更新要求が入力されると、前記二分木における各ノードに割り当てられた前記ＬＲ署名鍵を前記鍵更新アルゴリズムにより更新し、更新したＬＲ署名鍵が含まれる各ノードに割り当てられた前記ＬＲ署名鍵と前記ＬＲ検証鍵と、当該ＬＲ署名鍵に基づいて生成された前記ＬＲ署名とに基づいて前記ＦＳＬＲ署名鍵を更新するステップと、
入力されるメッセージと前記ＦＳＬＲ署名鍵が要素として含む前記葉ノードに割り当てた前記ＬＲ署名鍵とに基づいて前記署名生成アルゴリズムにより生成したＬＲ署名と、前記ＦＳＬＲ署名鍵が要素として含む前記ＬＲ署名であって、前記ノード毎のＬＲ署名鍵に基づいて生成された前記ＬＲ署名と、前記ＦＳＬＲ署名鍵が要素として含む前記ＬＲ検証鍵とを、前記メッセージに対するＦＳＬＲ署名として出力するステップと、
前記Ｌｅａｋａｇｅ−Ｒｅｓｉｌｉｅｎｔ方式に基づくＬＲ署名を検証する検証アルゴリズムが記憶されている検証アルゴリズム記憶部を有する検証装置が、
前記ＦＳＬＲ署名に含まれる全ての前記ＬＲ署名について検証が成功した場合に、検証成功と判定するステップと、
を備えることを特徴とする電子署名方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子署名の技術に関する。
【背景技術】
【０００２】
デジタル署名では、署名鍵や、署名方式が内部で利用する乱数情報などの内部情報が漏えいすることにより、署名方式の安全性を損なうことが考えられる。そこで、Ｆｏｒｗａｒｄ−Ｓｅｃｕｒｅ方式（以下、ＦＳ方式）とよばれる署名方式が提案されている。ＦＳ方式では、署名に用いる署名鍵をある時間間隔、期間(以下、ピリオドともいう)で更新しながら、署名の生成を行う（例えば、非特許文献１参照）。これにより、あるピリオドに対応した署名鍵が漏えいしたとしても、過去に生成した署名の信頼性には影響しないようにすることができる。
あるいは、Ｌｅａｋａｇｅ−Ｒｅｓｉｌｉｅｎｔ方式（以下、ＬＲ方式）とよばれる署名方式が提案されている。ＬＲ方式では、サイドチャネル攻撃による署名方式の内部情報の漏えいに備え、署名方式の各アルゴリズムの処理中に利用する情報が、ある制限された範囲内であれば漏えいしたとしても署名方式の安全性を確保できるよう設計されている（例えば、非特許文献２参照）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ｍｉｈｉｒ  Ｂｅｌｌａｒｅ、Ｓａｒａ  Ｋ．Ｍｉｎｅｒ、“Ａ  Ｆｏｒｗａｒｄ−Ｓｅｃｕｒｅ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅ．”ＣＲＹＰＴＯ’９９、ＬＮＣＳ  １６６６、ｐｐ．４３１−４４８、１９９９．
【非特許文献２】Ｅｌｅｔｔｅ Ｂｏｙｌｅ、Ｇｉｌ Ｓｅｇｅｖ、Ｄａｎｉｅｌ  Ｗｉｃｈｓ、“Ｆｕｌｌｙ Ｌｅａｋａｇｅ−Ｒｅｓｉｌｉｅｎｔ  Ｓｉｇｎａｔｕｒｅｓ”、インターネットＵＲＬ:http://eprint.iacr.org/2010/488.pdf
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、サイドチャネル攻撃は日々その精度が向上していると考えられる。その為、ＬＲ方式において、現時点における最良のサイドチャネル攻撃を用いた場合、署名方式が許容できる量の情報漏えいしか発生することが無かったとしても、その状況が将来にわたって保証されるわけではない。許容できる量の情報漏えいを超えて情報が漏えいしてしまった場合、ＬＲ方式によっては署名鍵情報全てを漏えいする可能性がある。一方、ＦＳ方式は、このようなサイドチャネル攻撃を想定したものではない。
そこで、署名鍵全体や内部情報の漏えいが両方共起こりうる状況を想定したとしても、過去に生成した署名の信頼性を保証することのできる署名方式による署名を行うことが望ましい。
【０００５】
本発明は、このような状況に鑑みてなされたもので、ＦＳ方式およびＬＲ方式両方の性質を持つ署名方式を提供する。
【課題を解決するための手段】
【０００６】
上述した課題を解決するために、本発明は、Ｌｅａｋａｇｅ−Ｒｅｓｉｌｉｅｎｔ方式に基づくＬＲ署名鍵とＬＲ検証鍵とを生成する鍵生成アルゴリズムと、ＬＲ署名鍵を更新する鍵更新アルゴリズムと、入力されるメッセージとＬＲ署名鍵とに基づいてＬＲ署名を生成する署名生成アルゴリズムとが記憶されている生成アルゴリズム記憶部と、鍵生成アルゴリズムによって生成されたＬＲ署名鍵が記憶される鍵記憶部と、鍵生成アルゴリズムに基づいて、複数の期間毎に対応付けられたＬＲ署名鍵とＬＲ検証鍵との組み合わせを生成し、生成した複数のＬＲ署名鍵を鍵記憶部に記憶させ、生成した複数のＬＲ検証鍵を出力する鍵生成部と、期間更新要求が入力されると、鍵記憶部に記憶されている、複数の期間毎に対応付けられたＬＲ署名鍵のうち、最も早い期間に対応付けられたＬＲ署名鍵を削除し、削除されていないＬＲ署名鍵を鍵更新アルゴリズムにより更新する期間更新部と、入力されるメッセージと、記前鍵記憶部に記憶されている、複数の期間毎に対応付けられたＬＲ署名鍵のうち、最も早い期間に対応付けられたＬＲ署名鍵とに基づいて生成されたＬＲ署名を、メッセージに対するＦＳＬＲ署名として出力する署名生成部と、を有する電子署名装置と、Ｌｅａｋａｇｅ−Ｒｅｓｉｌｉｅｎｔ方式に基づくＬＲ署名を検証する検証アルゴリズムが記憶されている検証アルゴリズム記憶部と、ＬＲ署名を生成したＬＲ署名鍵に対応するＬＲ検証鍵に基づいて、ＦＳＬＲ署名を検証する検証部と、を有する検証装置と、を備えることを特徴とする電子署名システムである。
【０００７】
また、本発明は、鍵更新要求が入力されると、鍵記憶部に記憶されている複数のＬＲ署名鍵を、鍵更新アルゴリズムにより更新する鍵更新部と、を備えることを特徴とする。
【０００８】
また、本発明は、Ｌｅａｋａｇｅ−Ｒｅｓｉｌｉｅｎｔ方式に基づくＬＲ署名鍵とＬＲ検証鍵とを生成する鍵生成アルゴリズムと、ＬＲ署名鍵を更新する鍵更新アルゴリズムと、入力されるメッセージとＬＲ署名鍵とに基づいてＬＲ署名を生成する署名生成アルゴリズムとが記憶されている生成アルゴリズム記憶部と、複数の期間毎に、期間を識別する期間情報を対応付けた同レベルの複数の葉ノードを有する二分木の各ノードに、鍵生成アルゴリズムにより生成したＬＲ署名鍵とＬＲ検証鍵とを割り当て、二分木における葉ノード以外のノード毎に、親ノードに割り当てられたＬＲ署名鍵と、親ノードに対する双方の子ノードに割り当てられたＬＲ検証鍵を結合した情報とに基づいて署名生成アルゴリズムによりＬＲ署名を生成し、葉ノードに割り当てられたＬＲ署名鍵と、葉ノードに対応付けられた期間情報とに基づいて署名生成アルゴリズムによりＬＲ署名を生成し、生成した複数のＬＲ署名と、葉ノードに割り当てられたＬＲ署名鍵及びＬＲ検証鍵と、親ノードに対して左の子ノードに割り当てられたＬＲ検証鍵と、親ノードに対して右の子ノードに割り当てられたＬＲ署名鍵及びＬＲ検証鍵とを要素として含むＦＳＬＲ署名鍵を生成し、二分木における根ノードに割り当てたＬＲ検証鍵を、ＦＳＬＲ署名鍵に対応するＦＳＬＲ検証鍵として出力する鍵生成部と、期間更新要求が入力されると、二分木において最も左の葉ノードを削除し、葉ノード以外の各ノードに割り当てられたＬＲ署名鍵とＬＲ検証鍵と、ＬＲ署名鍵に基づいて生成されたＬＲ署名とに基づいてＦＳＬＲ署名鍵を更新する期間更新部と、期間更新要求が入力されると、二分木における各ノードに割り当てられたＬＲ署名鍵を鍵更新アルゴリズムにより更新し、更新したＬＲ署名鍵が含まれる各ノードに割り当てられたＬＲ署名鍵とＬＲ検証鍵と、ＬＲ署名鍵に基づいて生成されたＬＲ署名とに基づいてＦＳＬＲ署名鍵を更新する鍵更新部と、入力されるメッセージとＦＳＬＲ署名鍵が要素として含む葉ノードに割り当てたＬＲ署名鍵とに基づいて署名生成アルゴリズムにより生成したＬＲ署名と、ＦＳＬＲ署名鍵が要素として含むＬＲ署名であって、ノード毎のＬＲ署名鍵に基づいて生成されたＬＲ署名と、ＦＳＬＲ署名鍵が要素として含むＬＲ検証鍵とを、メッセージに対するＦＳＬＲ署名として出力する署名生成部と、を有する電子署名装置と、Ｌｅａｋａｇｅ−Ｒｅｓｉｌｉｅｎｔ方式に基づくＬＲ署名を検証する検証アルゴリズムが記憶されている検証アルゴリズム記憶部と、ＦＳＬＲ署名に含まれる全てのＬＲ署名について検証が成功した場合に、検証成功と判定する検証部と、を有する検証装置と、を備えることを特徴とする電子署名システムである。
【０００９】
また、本発明は、電子署名装置の鍵更新部は、鍵更新要求が入力されると、二分木における各ノードに割り当てられたＬＲ署名鍵を、鍵更新アルゴリズムにより更新し、更新したＬＲ署名鍵に基づいてＦＳＬＲ署名鍵を生成することを特徴とする。
【００１０】
また、本発明は、Ｌｅａｋａｇｅ−Ｒｅｓｉｌｉｅｎｔ方式に基づくＬＲ署名鍵とＬＲ検証鍵とを生成する鍵生成アルゴリズムと、ＬＲ署名鍵を更新する鍵更新アルゴリズムと、入力されるメッセージとＬＲ署名鍵とに基づいてＬＲ署名を生成する署名生成アルゴリズムとが記憶されている生成アルゴリズム記憶部と、鍵生成アルゴリズムによって生成されたＬＲ署名鍵が記憶される鍵記憶部と、を有する電子署名装置が、鍵生成アルゴリズムに基づいて、複数の期間毎に対応付けられたＬＲ署名鍵とＬＲ検証鍵との組み合わせを生成し、生成した複数のＬＲ署名鍵を鍵記憶部に記憶させ、生成した複数のＬＲ検証鍵を出力するステップと、期間更新要求が入力されると、鍵記憶部に記憶されている、複数の期間毎に対応付けられたＬＲ署名鍵のうち、最も早い期間に対応付けられたＬＲ署名鍵を削除し、削除されていないＬＲ署名鍵を鍵更新アルゴリズムにより更新するステップと、入力されるメッセージと、記前鍵記憶部に記憶されている、複数の期間毎に対応付けられたＬＲ署名鍵のうち、最も早い期間に対応付けられたＬＲ署名鍵とに基づいて生成されたＬＲ署名を、メッセージに対するＦＳＬＲ署名として出力するステップと、Ｌｅａｋａｇｅ−Ｒｅｓｉｌｉｅｎｔ方式に基づくＬＲ署名を検証する検証アルゴリズムが記憶されている検証アルゴリズム記憶部を有する検証装置が、ＬＲ署名を生成したＬＲ署名鍵に対応するＬＲ検証鍵に基づいて、ＦＳＬＲ署名を検証するステップと、を備えることを特徴とする電子署名方法である。
【００１１】
また、本発明は、Ｌｅａｋａｇｅ−Ｒｅｓｉｌｉｅｎｔ方式に基づくＬＲ署名鍵とＬＲ検証鍵とを生成する鍵生成アルゴリズムと、ＬＲ署名鍵を更新する鍵更新アルゴリズムと、入力されるメッセージとＬＲ署名鍵とに基づいてＬＲ署名を生成する署名生成アルゴリズムとが記憶されている生成アルゴリズム記憶部を有する電子署名装置が、複数の期間毎に、期間を識別する期間情報を対応付けた同レベルの複数の葉ノードを有する二分木の各ノードに、鍵生成アルゴリズムにより生成したＬＲ署名鍵とＬＲ検証鍵とを割り当て、二分木における葉ノード以外のノード毎に、親ノードに割り当てられたＬＲ署名鍵と、親ノードに対する双方の子ノードに割り当てられたＬＲ検証鍵を結合した情報とに基づいて署名生成アルゴリズムによりＬＲ署名を生成し、葉ノードに割り当てられたＬＲ署名鍵と、葉ノードに対応付けられた期間情報とに基づいて署名生成アルゴリズムによりＬＲ署名を生成し、生成した複数のＬＲ署名と、葉ノードに割り当てられたＬＲ署名鍵及びＬＲ検証鍵と、親ノードに対して左の子ノードに割り当てられたＬＲ検証鍵と、親ノードに対して右の子ノードに割り当てられたＬＲ署名鍵及びＬＲ検証鍵とを要素として含むＦＳＬＲ署名鍵を生成し、二分木における根ノードに割り当てたＬＲ検証鍵を、ＦＳＬＲ署名鍵に対応するＦＳＬＲ検証鍵として出力するステップと、期間更新要求が入力されると、二分木において最も左の葉ノードを削除し、葉ノード以外の各ノードに割り当てられたＬＲ署名鍵とＬＲ検証鍵と、ＬＲ署名鍵に基づいて生成されたＬＲ署名とに基づいてＦＳＬＲ署名鍵を更新するステップと、期間更新要求が入力されると、二分木における各ノードに割り当てられたＬＲ署名鍵を鍵更新アルゴリズムにより更新し、更新したＬＲ署名鍵が含まれる各ノードに割り当てられたＬＲ署名鍵とＬＲ検証鍵と、ＬＲ署名鍵に基づいて生成されたＬＲ署名とに基づいてＦＳＬＲ署名鍵を更新するステップと、入力されるメッセージとＦＳＬＲ署名鍵が要素として含む葉ノードに割り当てたＬＲ署名鍵とに基づいて署名生成アルゴリズムにより生成したＬＲ署名と、ＦＳＬＲ署名鍵が要素として含むＬＲ署名であって、ノード毎のＬＲ署名鍵に基づいて生成されたＬＲ署名と、ＦＳＬＲ署名鍵が要素として含むＬＲ検証鍵とを、メッセージに対するＦＳＬＲ署名として出力するステップと、Ｌｅａｋａｇｅ−Ｒｅｓｉｌｉｅｎｔ方式に基づくＬＲ署名を検証する検証アルゴリズムが記憶されている検証アルゴリズム記憶部を有する検証装置が、ＦＳＬＲ署名に含まれる全てのＬＲ署名について検証が成功した場合に、検証成功と判定するステップと、を備えることを特徴とする電子署名方法である。
【発明の効果】
【００１２】
以上説明したように、本発明によれば、電子署名装置が、ＬＲ方式の鍵生成アルゴリズムによりＬＲ署名鍵とＬＲ検証鍵とを生成し、生成したＬＲ署名鍵を、一方向性を持つように期間毎に更新し、検証装置は、対応するＬＲ検証鍵により検証処理を行うようにしたので、ＦＳ方式およびＬＲ方式両方の性質を持つ署名方式を提供することができる。
【図面の簡単な説明】
【００１３】
【図１】本発明の一実施形態による電子署名システムの構成例を示すブロック図である。
【図２】本発明の一実施形態によるＦＳＬＲ方式の概要を示す図である。
【図３】本発明の一実施形態により利用するアルゴリズムの例を示す図である。
【図４】本発明の第１の実施形態によるＬＲ署名鍵とＬＲ検証鍵との生成例を示す図である。
【図５】本発明の第１の実施形態によるＦＳＬＲ署名鍵の期間更新の例を示す図である。
【図６】本発明の第１の実施形態によるＦＳＬＲ署名鍵の鍵更新の例を示す図である。
【図７】本発明の第１の実施形態によるＦＳＬＲ署名の例を示す図である。
【図８】本発明の第１の実施形態による電子署名装置のＦＳＬＲ鍵生成処理の動作例を示すフローチャートである。
【図９】本発明の第１の実施形態による検証装置のＦＳＬＲ検証処理の動作例を示すフローチャートである。
【図１０】本発明の第２の実施形態による二分木の例を示す図である。
【図１１】本発明の第２の実施形態による二分木の表記法の例を示す図である。
【図１２】本発明の第２の実施形態によるＬＲ署名鍵とＬＲ検証鍵との生成例を示す図である。
【図１３】本発明の第２の実施形態によるＬＲ署名の生成例を示す図である。
【図１４】本発明の第２の実施形態によるＬＲ署名の生成例を示す図である。
【図１５】本発明の第２の実施形態によるＬＲ署名の生成例を示す図である。
【図１６】本発明の第２の実施形態によるＦＳＬＲ署名鍵の例を示す図である。
【図１７】本発明の第２の実施形態によるＦＳＬＲ署名鍵の期間更新の例を示す図である。
【図１８】本発明の第２の実施形態によるＦＳＬＲ署名鍵の期間更新の例を示す図である。
【図１９】本発明の第２の実施形態によるＦＳＬＲ署名鍵の鍵更新の例を示す図である。
【図２０】本発明の第２の実施形態によるＦＳＬＲ署名の例を示す図である。
【図２１】本発明の第２の実施形態による電子署名装置のＦＳＬＲ鍵生成処理の動作例を示すフローチャートである。
【図２２】本発明の第２の実施形態による検証装置のＦＳＬＲ検証処理の動作例を示すフローチャートである。
【発明を実施するための形態】
【００１４】
以下、本発明の一実施形態について、図面を参照して説明する。
＜第１の実施形態＞
図１は、本発明の第１の実施形態による電子署名システム１の構成を示すブロック図である。電子署名システム１は、電子署名装置１０と、検証装置２０とを備えており、Ｆｏｒｗａｒｄ−Ｓｅｃｕｒｅ方式（以下、ＦＳ方式）とＬｅａｋａｇｅ−Ｒｅｓｉｌｉｅｎｔ方式（以下、ＬＲ方式）との両方の性質を持つ署名方式を提供する。
【００１５】
まず、ＦＳ方式について説明する。デジタル署名方式において、 もっとも大きな脅威の一つは署名鍵の漏えいである。署名鍵が漏えいしてしまうと、署名方式のライフサイクル全体において、署名の偽造が容易にできてしまう。そこで、ＦＳ方式では、このような脅威に対し、署名方式のライフサイクルを「ピリオド」と呼ばれる期間（時間間隔）に分割し、検証鍵を固定としたまま、署名鍵をピリオド毎に更新する。これにより、現在のピリオドの署名鍵が漏えいしたとしても、過去のピリオドの署名鍵で生成した署名については、偽造を困難にすることを可能としている。上述の非特許文献１には、ＢｅｌｌａｒｅらによるＦＳ方式が記載されている。ここでは、二分木を用いた構成が示されており、署名鍵は、一般的な署名方式の鍵生成アルゴリズムで生成された署名鍵、検証鍵、および署名生成アルゴリズムで生成された署名から構成されている。署名鍵の構成要素の中には、ピリオドを更新しても長期にわたり保持している必要のあるものが存在する。また、署名鍵の構成要素のうち、検証鍵および署名はたとえ全て漏えいしたとしても署名方式の安全性には影響しない。一方、署名鍵の構成要素のうち、署名鍵の情報が部分的に漏えいすることは安全性に影響があるため、ランダマイズすることによる更新が必要である。
【００１６】
次に、ＬＲ方式について説明する。既存のデジタル署名に対する安全性のモデルでは、署名方式において利用されている署名鍵や内部の乱数情報、または署名生成時の内部状態についての漏えいに関しては定式化されていない。しかし、実世界においては署名方式を実装したハードウェアに対してサイドチャネル攻撃を行う事により、それらのさまざまな情報を得ることが起こり得る。そのため、既存の安全性のモデルにおいて証明されたとしてもサイドチャネル攻撃が考えられる状況おいて安全性が満たされているとは言えない。そこで、ＬＲ方式では、既存のデジタル署名のモデルにおいて考慮されていなかったサイドチャネル攻撃などによるさまざまな情報の取得を、偽造者に許可する形でセキュリティモデルを定義している。各署名方式により様々なセキュリティモデルの定義が存在する。上述の非特許文献２には、ＢｏｙｌｅらによるＬＲ方式が示されている。
【００１７】
このようなＦＳ方式とＬＲ方式とは、上述のように異なる課題、目的を持って研究されているものであるが、本実施形態では、署名鍵を構成する要素を、すべてＢｏｙｌｅらによるＬＲ方式の鍵生成アルゴリズムで生成し、ピリオド毎に更新することで、ＬＲ方式とＦＳ方式との双方の方式の性質をもつ署名方式を構成する。以下の説明においては、このような電子署名の方式をＦＳＬＲ方式という。ＦＳＬＲ方式では、ＬＲ方式と同様に、サイドチャネル攻撃などによる署名方式の内部情報の漏えいについて考慮する。さらに、ある時点において署名方式の署名鍵の情報がすべて漏えいしてしまう事を想定し、ＦＳ方式の性質も具備するものとする。ＬＲ方式の性質を持つためには、上述のように鍵更新をすることによる署名鍵のランダマイズが必要である。ＦＳ方式の性質を持つためには，ピリオドの概念が必要であり、ピリオド変更時に鍵を更新するが、その時の更新が一方向性を持つ必要がある。上述のようなＦＳ方式とＬＲ方式とを組み合わせることにより、ＦＳ方式の署名鍵をランダマイズし、ＦＳＬＲ方式を実現することが可能である。以下、ＦＳＬＲ方式に基づいて生成する署名鍵をＦＳＬＲ署名鍵（ＳＫｔ、ｉ）（ｔは期間（ピリオド）、ｉはピリオド内での鍵更新回数）といい、検証鍵をＦＳＬＲ検証鍵（ＶＫ）といい、ＦＳＬＲ署名鍵に基づいて生成された署名をＦＳＬＲ署名（Σ）という。また、ＬＲ方式の署名鍵をＬＲ署名鍵（ｓｋ）といい、検証鍵をＬＲ検証鍵（ｖｋ）といい、ＬＲ署名鍵に基づいて生成された署名をＬＲ署名（σ）という。
【００１８】
図２は、本実施形態によるＦＳＬＲ方式の概要を示す図である。ＦＳＬＲ方式では、電子署名装置１０が、ＦＳＬＲ署名鍵（ＳＫ０、０）とＦＳＬＲ検証鍵（ＶＫ）とを生成し、ＦＳＬＲ検証鍵（ＶＫ）を公開する。そして、電子署名装置１０は、任意のタイミングでＦＳＬＲ署名鍵（ＳＫ０、０）のピリオド更新を行い、ＦＳＬＲ署名鍵ＳＫ（ＳＫ１、０）を生成する。この時点で、ＦＳＬＲ署名鍵（ＳＫ０、０）は無効化され、ＦＳＬＲ署名鍵ＳＫ（ＳＫ１、０）が有効になる。このように、ピリオド毎にＦＳＬＲ署名鍵（ＳＫｔ、ｉ）の更新を行い、ＦＳＬＲ署名（Σ）を生成する際には、その時点で有効なＦＳＬＲ署名鍵（ＳＫｔ、ｉ）を用いてＦＳＬＲ署名（Σ）を生成する。ＦＳＬＲ検証鍵（ＶＫ）は、全てのピリオドにおいて同一の鍵を用いることができる。また、ピリオド内においても、ＦＳＬＲ署名鍵（ＳＫｔ、ｉ）を更新し、ＦＳＬＲ署名鍵（ＳＫｔ、ｉ＋１）を生成することができる。この時点で、ＦＳＬＲ署名鍵（ＳＫｔ、ｉ）は無効化され、ＦＳＬＲ署名鍵ＳＫ（ＳＫｔ、ｉ＋１）が有効になる。これにより、例えばピリオドｔにおいてＦＳＬＲ署名鍵ＳＫ（ＳＫｔ、ｎ）が漏えいした場合でも、ピリオドｔ−１以前のＦＳＬＲ署名（Σ）を偽造することが困難であるようにすることができる。すなわち、ＦＳ方式の電子署名と、ＬＲ方式の電子署名との双方の特徴を持つＦＳＬＲ方式の電子署名を行うことができる。
【００１９】
図１に戻り、電子署名装置１０は、入力部１１と、出力部１２と、生成アルゴリズム記憶部１３と、鍵生成部１４と、鍵記憶部１５と、期間更新部１６と、鍵更新部１７と、署名生成部１８とを備えたコンピュータ装置である。電子署名装置１０には、例えば、いわゆるＰＣ（Personal Computer）や、ＩＣ（Integrated Circuit）カードなどが適用できる。
【００２０】
入力部１１は、情報の入力を受け付ける。例えば、電子署名装置１０がＰＣであれば、キーボードやマウス、ＩＣカードリーダ等の入力デバイスであり、電子署名装置１０がＩＣカードであれば、外部のＩＣカードリーダと通信する通信部である。入力部１１には、ユーザにより、任意のタイミングで期間更新要求や鍵更新要求が入力される。ここで、任意のタイミングとは、例えば期間、電子署名装置１０による署名の生成回数等によって、ＦＳＬＲ方式の管理者等によって予め定められたタイミングでも良い。
【００２１】
出力部１２は、電子署名装置１０によって生成される、ＦＳＬＲ検証鍵やＦＳＬＲ署名等の各種情報を出力する。出力部１２は、例えば、生成した情報をＩＣカード等に書き込むＩＣカードリータ等のデバイスである。
【００２２】
生成アルゴリズム記憶部１３には、上述したようなＬＲ方式に基づくＬＲ署名鍵とＬＲ検証鍵とを生成する鍵生成アルゴリズム（Ｌ−ＫＧ）と、ＬＲ署名鍵を更新する鍵更新アルゴリズム（Ｌ−Ｋｕｐｄ）と、入力されるメッセージとＬＲ署名鍵とに基づいてＬＲ署名を生成する署名生成アルゴリズム（Ｌ−Ｓｉｇ）とが記憶されている。このような鍵生成アルゴリズム（Ｌ−ＫＧ）と、鍵更新アルゴリズム（Ｌ−Ｋｕｐｄ）と、署名生成アルゴリズム（Ｌ−Ｓｉｇ）と、後述する検証アルゴリズム（Ｌ−Ｖｆｙ）とは、上述の文献２に記載されたアルゴリズムを用いる。図３は、これらのアルゴリズムと文献２に記載されたアルゴリズムとの対応関係を示す図である。本実施形態における鍵生成アルゴリズム（Ｌ−ＫＧ）と、鍵更新アルゴリズム（Ｌ−Ｋｕｐｄ）と、署名生成アルゴリズム（Ｌ−Ｓｉｇ）と、検証アルゴリズム（Ｌ−Ｖｆｙ）とは、非特許文献２におけるＫｅｙＧｅｎと、Ｒｅｆｒｅｓｈと、Ｓｉｇｎと、Ｖｅｒｉｆｙとに対応する。
【００２３】
鍵生成アルゴリズム（Ｌ−ＫＧ）は、セキュリティパラメタｋを入力とし、初期署名鍵ｓｋ０、検証鍵ｖｋを出力する（（ｓｋ０、ｖｋ）←Ｌ−ＫＧ（１ｋ））。ここで、本実施形態において、例えばアルゴリズムＦがｘを入力とし、内部に乱数（ｒ）を用いた確率的アルゴリズムによりｙを出力する場合、ｙ←Ｆ（ｘ）と表記する。アルゴリズムＦがｘおよび乱数情報ｒを入力とし、確定的アルゴリズムによりｙを出力する場合、ｙ：＝Ｆ（ｘ、ｒ）と表記する。ｘ＝ｙと表記するときは、条件式としてｘとｙとが等しいことを示す。
鍵更新アルゴリズム（Ｌ−Ｋｕｐｄ）は、署名鍵ｓｋｉを入力とし、更新後の署名鍵（ｓｋｉ＋１）を出力する（ｓｋｉ＋１←Ｌ−Ｋｕｐｄ（ｓｋｉ））。
署名生成アルゴリズム（Ｌ−Ｓｉｇ）は、署名鍵ｓｋｉ、メッセージＭを入力とし、署名σを出力する（σ←Ｌ−Ｓｉｇ（ｓｋｉ、Ｍ））。
【００２４】
鍵生成部１４は、生成アルゴリズム記憶部１３に記憶されている鍵生成アルゴリズム（Ｌ−ＫＧ）を読み出し、読み出した鍵生成アルゴリズム（Ｌ−ＫＧ）に基づいて、複数の期間毎に対応付けられたＬＲ署名鍵とＬＲ検証鍵との組み合わせを生成し、生成した複数のＬＲ署名鍵であるＦＳＬＲ署名鍵を鍵記憶部１５に記憶させ、生成した複数のＬＲ検証鍵であるＦＳＬＲ検証鍵を出力する。例えば、ピリオドの総数をＴとすると、図４に示すように、複数のＬＲ検証鍵ｖｋ０〜ｖｋＴ−１を生成し、ＦＳＬＲ検証鍵であるＶＫとする。また、複数のＬＲ署名鍵ｓｋ０、０〜ｓｋＴ−１、０を生成し、ピリオド０のＦＳＬＲ署名鍵であるＳＫ０、０とする。
【００２５】
具体的には、鍵生成部１４は、以下手順によりＦＳＬＲ署名鍵（ＳＫ０、０）とＦＳＬＲ検証鍵ＶＫとを生成する。
１．ｓ∈｛０、・・・、Ｔ−１｝に対して、（ｓｋｓ、０、ｖｋｓ、０）←Ｌ−ＫＧ（１ｋ）を計算する。
２．ＳＫ０、０：＝（ｓｋ０、０、ｓｋ１、０、ｓｋ２、０、・・・、ｓｋＴ−１、０）とする。
３．ＶＫ：＝（ｖｋ０、ｖｋ１、・・・、ｖｋＴ−１）とする。
４．ＦＳＬＲ署名鍵（ＳＫ０、０）、ＦＳＬＲ検証鍵（ＶＫ）を出力する。ここで、ＦＳＬＲ署名鍵（ＳＫ０、０）は鍵記憶部１５に記憶させる。
【００２６】
鍵記憶部１５には、鍵生成部１４によって鍵生成アルゴリズムを用いて生成されたＦＳＬＲ署名鍵（ＳＫ０、０）が記憶される。
期間更新部１６は、期間更新要求が入力されると、鍵記憶部１５に記憶されている、複数の期間毎に対応付けられたＬＲ署名鍵（ｓｋ）のうち、最も早い期間に対応付けられたＬＲ署名鍵を削除し、削除されていないＬＲ署名鍵（ｓｋ）を、生成アルゴリズム記憶部１３に記憶されている鍵更新アルゴリズム（Ｌ−Ｋｕｐｄ）により更新する。例えば、図５に示すように、ピリオド０からピリオド１への期間更新要求が入力されると、鍵記憶部１５に記憶されているＳＫ０、０に含まれる複数のｓｋのうち、ｓｋ０、０を削除し、他のｓｋ（ｓｋ１、０、ｓｋ２、０、・・・、ｓｋＴ−１、０）を鍵更新アルゴリズム（Ｌ−Ｋｕｐｄ）により更新する。
【００２７】
具体的には、期間更新部１６は、以下手順によりピリオドを更新したＦＳＬＲ署名鍵を生成する。ここでは、期間更新前のピリオドをｔとし、期間更新後のピリオドをｔ＋１とする。
１．ＳＫｔ、ｉ：＝（ｓｋｔ、ｉ、ｓｋｔ＋１、ｉ、・・・、ｓｋＴ−１、ｉ）とおく。
２．ｓｋｔ、ｉを削除する。
３．ｓ∈｛ｔ＋１、・・・、Ｔ−１｝に対して、ｓｋｓ、０←Ｌ−Ｋｕｐｄ（ｓｋｓ、ｉ）を計算する。
４．ＳＫｔ＋１、０：＝（ｓｋｔ＋１、０、・・・、ｓｋＴ−１、０）とおく。
５．ピリオドｔ＋１、ＳＫｔ＋１、０を出力する。
【００２８】
鍵更新部１７は、鍵更新要求が入力されると、生成アルゴリズム記憶部１３に記憶されている鍵更新アルゴリズム（Ｌ−Ｋｕｐｄ）を読み出し、鍵記憶部１５に記憶されている複数のＬＲ署名鍵を、読み出した鍵更新アルゴリズム（Ｌ−Ｋｕｐｄ）により更新する。例えば、図６に示すように、鍵記憶部１５に記憶されているＳＫｔ、ｉに含まれる複数のｓｋ（ｓｋｔ、ｉ、・・・、ｓｋＴ−１、ｉ）を鍵更新アルゴリズム（Ｌ−Ｋｕｐｄ）により更新する。
【００２９】
具体的には、鍵更新部１７は、以下手順により更新したＦＳＬＲ署名鍵を生成する。
１．ＳＫｔ、ｉ：＝（ｓｋｔ、ｉ、ｓｋｔ＋１、ｉ、・・・、ｓｋＴ−１、ｉ）とおく。
２．ｓ∈｛ｔ、・・・、Ｔ−１｝に対して、ｓｋｓ、ｉ＋１←Ｌ−Ｋｕｐｄ（ｓｋｓ、ｉ）を計算する。
３．ＳＫｔ、ｉ＋１：＝（ｓｋｔ、ｉ＋１、・・・、ｓｋＴ−１、ｉ＋１）を出力する。
このように、期間更新はピリオドの更新を伴い、鍵の更新も行うアルゴリズムであり、鍵更新はピリオドの更新を伴わずに、鍵の更新を行うアルゴリズムである。
【００３０】
署名生成部１８は、入力されるメッセージと、鍵記憶部１５に記憶されている、複数の期間毎に対応付けられたＬＲ署名鍵のうち、最も早い期間に対応付けられたＬＲ署名鍵とに基づいて生成されたＬＲ署名を、メッセージに対するＦＳＬＲ署名として出力する。具体的には、生成アルゴリズム記憶部１３に記憶されている署名生成アルゴリズム（Ｌ−Ｓｉｇ）を読み出し、図７に示すように、現在のピリオドｔに対応するｓｋｔ、ｉを用いて、署名アルゴリズム（Ｌ−ＳＩＧ）によりメッセージＭのＬＲ署名を生成する。
【００３１】
具体的には、署名生成部１８は、以下手順によりＦＳＬＲ署名Σを出力する。
１．σ←Ｌ−ＳＩＧ（ｓｋｔ、ｉ、Ｍ）
２．（ｔ、Σ：＝σ）を出力する。
【００３２】
検証装置２０は、電子署名装置１０により生成されたＦＳＬＲ署名を検証するコンピュータ装置である。検証装置２０は、入力部２１と、出力部２２と、検証アルゴリズム記憶部２３と、検証部２４とを備えている。
【００３３】
入力部２１は、情報の入力を受け付ける。電子署名装置１０と同様に、例えば検証装置２０がＰＣであれば、キーボードやマウス、ＩＣカードリーダ等の入力デバイスであり、検証装置２０がＩＣカードであれば、外部のＩＣカードリーダと通信する通信部である。入力部１１には、検証の対象となるピリオドｔ、ＦＳＬＲ検証鍵ＶＫ、メッセージＭ、ＦＳＬＲ署名Σ等の情報が入力される。
出力部２２は、検証装置２０による検証結果を出力する。例えば、出力部１２は、検証結果を送信する通信部や、検証結果を表示するディスプレイである。
【００３４】
検証アルゴリズム記憶部２３には、上述したようなＬＲ方式に基づくＬＲ署名を検証する検証アルゴリズム（Ｌ−Ｖｆｙ）が記憶されている。検証アルゴリズム（Ｌ−Ｖｆｙ）は、検証鍵ｖｋ、メッセージＭ、署名σを入力とし、１(ｖａｌｉｄ)または０(ｉｎｖａｌｉｄ)の処理結果ｂを出力する（ｂ←Ｌ−Ｖｆｙ（ｖｋ、Ｍ、σ））。
【００３５】
次に、本実施形態による電子署名システム１の動作例を説明する。図８は、電子署名装置１０によるＦＳＬＲ鍵生成処理の動作例を示すフローチャートである。
電子署名装置１０の鍵生成部１４は、定められた複数の期間毎に、ＬＲ署名鍵とＬＲ検証鍵とを生成する（ステップＳ１）。生成した複数のＬＲ署名鍵は、ＦＳＬＲ鍵として鍵記憶部１５に記憶させる。また、生成した複数のＬＲ検証鍵は、ＦＳＬＲ検証鍵として出力し、公開する（ステップＳ３）。また、電子署名装置１０にメッセージＭが入力されると、電子署名装置１０の署名生成部１８は、生成アルゴリズム記憶部１３に記憶されている署名生成アルゴリズム（Ｌ−Ｓｉｇ）を読み出し、現在のピリオドに対応するＬＲ署名鍵ｓｋと、メッセージＭとに基づいて、ＦＳＬＲ署名（Σ）を生成して出力する。
【００３６】
図９は、検証装置２０によるＦＳＬＲ検証処理の動作例を示すフローチャートである。検証装置２０の入力部２１は、メッセージ（Ｍ）とＦＳＬＲ署名（Σ）との入力を受け付ける（ステップＳ１１）。検証部２４が、検証アルゴリズム記憶部２３に記憶されている検証アルゴリズムを読み出し、読み出した検証アルゴリズムによりメッセージ（Ｍ）に対するＦＳＬＲ署名（Σ）の検証を行う（ステップＳ１２）。検証部２４が、ＦＳＬＲ署名（Σ）が生成されたピリオドに対応するＬＲ検証鍵によるＬＲ署名（σ）について検証成功したと判定すれば（ステップＳ１１：ＹＥＳ）、検証成功の検証結果を出力する（ステップＳ１３）。検証部２４が、検証失敗したと判定すれば（ステップＳ１２：ＮＯ）、検証失敗の検証結果を出力する（ステップＳ１４）。
【００３７】
以上説明したように、本実施形態によれば、ＬＲ方式のアルゴリズムを用いて、ピリオド毎に一方向性のある鍵の更新を行うようにした。これにより、ＦＳ方式およびＬＲ方式両方の性質を持つ署名方式が提供できる。
【００３８】
＜第２の実施形態＞
次に、本発明の第２の実施形態について説明する。本実施形態における電子署名システム１の構成は、第１の実施形態において図１に示した電子署名システム１の構成と同様である。以下、第１の実施形態と異なる処理等について説明する。本実施形態では、ＢｅｌｌａｒｅらによるＦＳ方式で用いられた二分木を利用したピリオドごとの鍵の更新を用い、署名鍵を構成する要素を、すべてＢｏｙｌｅらによるＬＲ方式の鍵生成アルゴリズムにより生成する。
【００３９】
本実施形態における電子署名装置１０の鍵生成部１４は、生成アルゴリズム記憶部１３に記憶されている鍵生成アルゴリズム（Ｌ−ＫＧ）と署名生成アルゴリズム（Ｌ−Ｓｉｇ）とを読み出し、読み出したアルゴリズムを用いて、ＦＳＬＲ署名鍵とＦＳＬＲ検証鍵とを生成する。まず、鍵生成部１４は、複数のピリオド毎に、そのピリオドを識別する期間情報を対応付けた同レベルの複数の葉ノードを有する二分木を生成し、鍵記憶部１５に記憶させる。図１０は、鍵生成部１４が生成する二分木の例を示す図である。ここでは、８つのピリオドを示す葉ノードのそれぞれに、「０００」〜「１１１」の期間情報をノード番号として対応付ける。ノード番号は二進法によるビット列であるとする。根ノードのノード番号はεとする。根ノードεの左の子ノードを「０」とし、右の子ノードを「１」としている。さらに、ノード「０」を親ノードとする左の子ノードを「００」とし、右の子ノードを「０１」としている。このように、親ノードの左の子ノードには、親ノードのノード番号の末尾に０を付したノード番号を対応付け、親ノードの右の子ノードには、親ノードのノード番号の末尾に１を付したノード番号を対応付けている。
【００４０】
この二分木において、以下の表記法を利用する。 各ノードのノード番号をωとしたとき、そのビット列表現はω＝ω１ω２・・・ωｊとする。根ノードはεで表現し、そのビット列表現は空文字とする。深さはｄで表す。ノードω＝ω１ω２・・・ωｊに対して、子ノードをω０＝ω１ω２・・・ωｊ０、ω１＝ω１ω２・・・ωｊ１と表す。ノードω０＝ω１ω２・・・ωｊ０、およびω１＝ω１ω２・・・ωｊ１に対して、親ノードをω＝ω１ω２・・・ωｊと表す。ノードｔ＝ｔ１ｔ２・・・ｔｄに対し、ｊ∈｛１、・・・、ｄ−１｝について、ｔ｜ｊ＝ｔ１ｔ２・・・ｔｊと表し、ｔ｜０＝εと表す。さらに、ｔ｜ｊ０＝ｔ１ｔ２・・・ｔｊ０、ｔ｜ｊ１＝ｔ１ｔ２・・・ｔｊ１、と表す。二分木において、ｊ＝１、・・・、ｄ＋１に対し、葉ノードｔと根ノードとのパス上の深さｊにおける兄弟ノード (ｓｉｂｌｉｎｇ)を以下式（１）のように定義する。
【００４１】
【数１】
0005707271.tif 000002
【００４２】
ノードω∈｛０、１｝≦ｊ、ｊ∈｛１、・・・、ｄ｝に対して、ＤＦ（ω）を以下式（２）のように定義する。
【００４３】
【数２】
0005707271.tif 000003
【００４４】
このような表記法に沿った、深さｄ＝４の二分木、およびｓｉｂｌｉｎｇとＤＦの例を図１１に示す。
また、鍵生成部１４は、図１２に示すように、二分木の各ノードに、生成アルゴリズム記憶部１３から読み出した鍵生成アルゴリズムにより生成したＬＲ署名鍵（ｓｋ）とＬＲ検証鍵（ｖｋ）とを割り当てる。さらに、図１３に示すように、根ノードに割り当てられたＬＲ署名鍵（ｓｋε）と、親ノードに対する双方の子ノードに割り当てられたＬＲ検証鍵を結合した情報（ｖｋ０｜｜ｖｋ１）とに基づいて、生成アルゴリズム記憶部１３から読み出した署名生成アルゴリズムによりＬＲ署名（σε）を生成し、鍵記憶部１５に記憶させる。鍵生成部１４は、図１４に示すように、二分木における葉ノード以外のノード毎に、このようなＬＲ署名の生成処理を行う。
【００４５】
さらに、鍵生成部１４は、図１５に示すように、葉ノードに割り当てられたＬＲ署名鍵（例えば、ｓｋ０００）と、その葉ノードに対応付けられた期間情報（例えば、ノード番号「０００」）とに基づいて、生成アルゴリズム記憶部１３から読み出した署名生成アルゴリズムによりＬＲ署名（例えば、σ０００）を生成する。そして、図１６に破線に囲まれて示すような、生成した複数のＬＲ署名（σε、σ０、σ００、σ０００、σ００１）と、葉ノードに割り当てられたＬＲ署名鍵（ｓｋ０００、ｓｋ００１）及びＬＲ検証鍵（ｖｋ０００、ｖｋ００１）と、親ノードに対して左の子ノードに割り当てられたＬＲ検証鍵（ｖｋ０、ｖｋ００）と、その親ノードに対して右の子ノードに割り当てられたＬＲ署名鍵（ｓｋ１、ｓｋ０１）及びＬＲ検証鍵（ｖｋ１、ｖｋ０１）とを要素として、ＦＳＬＲ署名鍵（ＳＫ０、０）を生成する。例えば、これらの情報を配列に格納することにより、ＦＳＬＲ署名鍵（ＳＫ０、０）を生成する。また、鍵生成部１４は、二分木における根ノード（ε）に割り当てたＬＲ検証鍵（ｖｋε）を、ＦＳＬＲ署名鍵（ＳＫ０、０）に対応するＦＳＬＲ検証鍵（ＶＫ）として出力する。
【００４６】
このように、ＦＳＬＲ鍵を生成する鍵生成アルゴリズム（Ｋｇ）は、セキュリティパラメタｋと、ピリオドの総数Ｔを入力とし、初期ピリオドｔ、ＦＳＬＲ署名鍵ＳＫ０、０、ＦＳＬＲ検証鍵ＶＫを出力する（（ｔ、ｓｋ０、０、ｖｋ）←Ｋｇ（１ｋ、Ｔ））。ｔ：＝０とする。これにより、ピリオドｔのＦＳＬＲ署名鍵は、二分木の葉ノードω＝ｔ から根ノードεまでのパス上に存在するノード、 およびその兄弟ノードに対応させた、Ｌ−Ｋｇ（１ｋ）により生成した鍵で構成される。ピリオドｔにおいて、深さｊにおけるノード番号ω＝ｔ｜ｊの内部ノードに対応させる、署名鍵の更新をｉ回実施した鍵ペアを、（ｓｋ（ｔ｜ｄ）、ｉ、ｖｋ（ｔ｜ｊ））＝（ｓｋｔ、ｉ、ｖｋｔ）と表記する。
【００４７】
具体的には、鍵生成部１４は、以下手順によりＦＳＬＲ署名鍵（ＳＫ０、０）とＦＳＬＲ検証鍵ＶＫとを生成する。
１、Ｔを多項式オーダーの数とし、ｔ：＝０ｌｏｇ（Ｔ）とする。
２、（ｓｋε、ｖｋε）←Ｌ−Ｋｇ（１ｋ）を計算する。
３、ｊ∈｛０、・・・、ｄ−１｝に対して、以下を実行する。
ａ、（ｓｋ（ｔ|ｊ０）、０、ｖｋ（ｔ｜ｊ０））←Ｌ−Ｋｇ（１ｋ）
ｂ、（ｓｋ（ｔ｜ｊ１）、０、ｖｋ(ｔ｜ｊ１)）←Ｌ−Ｋｇ（１ｋ）
ｃ、σ(ｔ｜ｊ)←Ｌ−Ｓｉｇ(ｓｋ(ｔ｜ｊ)、０、ｖｋ(ｔ｜ｊ０)||ｖｋ(ｔ｜ｊ１))
ｄ、ｓｋ(ｔ｜ｊ)、０を削除する。
４、σ(ｔ)←Ｌ−Ｓｉｇ(ｓｋ(ｔ)、０、ｔ)を計算する。
５、以下式（３）によりピリオドｔ、ＦＳＬＲ署名鍵（ＳＫ０、０）、ＦＳＬＲ検証鍵（ＶＫ）を出力する。
【００４８】
【数３】
0005707271.tif 000004
【００４９】
鍵記憶部１５には、鍵生成部１４によって生成された二分木が記憶される。
期間更新部１６は、期間更新要求が入力されると、鍵記憶部１５に記憶された二分木において最も左の葉ノードを削除し、その葉ノード以外の各ノードに割り当てられたＬＲ署名鍵とＬＲ検証鍵と、そのＬＲ署名鍵に基づいて生成されたＬＲ署名とに基づいて、ピリオド更新したＦＳＬＲ署名鍵を生成する。図１７に示した図において、破線に囲まれた情報が、ピリオド更新後のピリオド２（ノード番号「００１」）におけるＦＳＬＲ署名鍵である。また、図１８に示した図において、破線に囲まれた情報が、ピリオド更新後のピリオド３（ノード番号「０１０」）におけるＦＳＬＲ署名鍵である。
すなわち、期間更新部１６は、カレントピリオドｔ、カレントピリオドのＦＳＬＲ署名鍵ＳＫｔ、ｉを入力とし、更新後のピリオドｔ＋１、更新後のＦＳＬＲ署名鍵ＳＫｔ＋１、ｉを出力する。
【００５０】
具体的には、期間更新部１６は、以下手順によりピリオドを更新したＦＳＬＲ署名鍵を生成する。
１、ＤＦ（ｔ）の深さをｊ´とする。
２、ｊ∈｛０、・・・、ｊ´−１｝に対して、
ａ、ω：＝ｓｉｂｌｉｎｇ(ｊ、ｔ＋１)とする。
ｂ、ω＝⊥のとき、ｓｋ(ｔ＋１|ｊ１)、０：＝⊥とする。
ｃ、ω≠のとき、ｓｋ(ω)、ｉ＋１←Ｌ−Ｕｐｄ（ｓｋ（ω）、ｉ）を計算し、ｓｋ(ｔ＋１ｊ｜１)、０：＝ｓｋ(ω)、ｉ＋１とする。
３、ｊ∈｛ｊ´、・・・、ｄ−１｝に対して、以下を実行する。
ａ、(ｓｋ(ｔ＋１|ｊ０)、０、ｖｋ(ｔ＋１｜ｊ０))←Ｌ−Ｋｇ(１ｋ)
ｂ、(ｓｋ(ｔ＋１｜ｊ１)、０、ｖｋ(ｔ＋１｜ｊ１))←Ｌ−Ｋｇ(１ｋ)
ｃ、σ(ｔ＋１｜ｊ)←Ｌ−Ｓｉｇ(ｓｋ(ｔ＋１｜ｊ１)、０、ｖｋ(ｔ＋１｜ｊ０)｜｜ｖｋ(ｔ＋１｜ｊ１))
ｄ、ｓｋ(ｔ＋１|ｊ)、０を削除する。
４、σ(ｔ＋１)←Ｌ−Ｓｉｇ(ｓｋ(ｔ＋１)、０、ｔ＋１)を計算する。
５、以下式（４）によりピリオドおよびＦＳＬＲ署名鍵(ｔ＋１、ＳＫｔ＋１、０)を出力する。
【００５１】
【数４】
0005707271.tif 000005
【００５２】
鍵更新部１７は、期間更新要求が入力されると、二分木における各ノードに割り当てられたＬＲ署名鍵を鍵更新アルゴリズムにより更新し、更新したＬＲ署名鍵が含まれる各ノードに割り当てられたＬＲ署名鍵とＬＲ検証鍵と、そのＬＲ署名鍵に基づいて生成されたＬＲ署名とに基づいて、更新したＦＳＬＲ署名鍵を生成する。また、鍵更新部１７は、鍵更新要求が入力されると、同様に、二分木における各ノードに割り当てられたＬＲ署名鍵を、鍵更新アルゴリズムにより更新し、更新したＬＲ署名鍵に基づいてＦＳＬＲ署名鍵を生成する。図１９は、ピリオド３（ノード番号「０１０」）において行う鍵更新の例を示す図である。
【００５３】
すなわち、鍵更新部１７は、カレントピリオドのＦＳＬＲ署名鍵ＳＫｔ、ｉを入力とし、更新後のＦＳＬＲ署名鍵ＳＫｔ、ｉ＋１を出力する。具体的には、鍵更新部１７は、以下手順により更新したＦＳＬＲ署名鍵を生成する。
１、ｊ∈｛０、・・・、ｄ−１｝に対して、
ａ、ω：＝ｓｉｂｌｉｎｇ(ｊ、ｔ)とする。
ｂ、ω＝⊥のとき、ｓｋ(ｔ｜ｊ１)、ｉ＋１：＝⊥とする。
ｃ、ω≠のとき、ｓｋ(ｔ|ｊ１)、ｉ＋１←Ｌ−Ｕｐｄ(ｓｋ(ω)、ｉ)を計算する。
２、以下式（５）によりＦＳＬＲ署名鍵ＳＫｔ、ｉ＋１を出力する。
【００５４】
【数５】
0005707271.tif 000006
【００５５】
署名生成部１８は、入力されるメッセージと葉ノードに割り当てたＬＲ署名鍵とに基づいて、署名生成アルゴリズムにより生成したＬＲ署名と、ノード毎のＬＲ署名鍵に基づいて生成されたＬＲ署名と、ＬＲ検証鍵とを、メッセージに対するＦＳＬＲ署名（Σ）として出力する。図２０は、ピリオド３（ノード番号「０１０」）において行う署名生成の例を示す図である。
すなわち、署名生成部１８は、カレントピリオドｔ、カレントピリオドの署名鍵ＳＫｔ、ｉ、メッセージＭを入力とし、カレントピリオドｔ、ＦＳＬＲ署名Σを出力する。具体的には、署名生成部１８は、以下手順によりＦＳＬＲ署名Σを出力する。
１、ピリオドおよび署名鍵(ｔ、ＳＫｔ、ｉ) を以下式（６）のように表記する。
【００５６】
【数６】
0005707271.tif 000007
【００５７】
２、σ←Ｌ−Ｓｉｇ(ｓｋ(ｔ)、ｉ、Ｍ)を計算する。
３、以下式（７）により、更新後のピリオドおよびＦＳＬＲ署名(ｔ、Σ)を出力する。
【００５８】
【数７】
0005707271.tif 000008
【００５９】
本実施形態における検証装置２０の検証部２４は、ＦＳＬＲ署名に含まれる全てのＬＲ署名について検証が成功した場合に、検証成功と判定する。署名が生成されたピリオドｔ、ＦＳＬＲ検証鍵ＶＫ、メッセージＭ、ＦＳＬＲ署名Σを入力とし、１(ｖａｌｉｄ)または０(ｉｎｖａｌｉｄ)を出力する。具体的には、検証部２４は、以下手順により検証結果を出力する。
１、ピリオドおよび署名(ｔ、Σ)を以下式（８）のように表記する。
【００６０】
【数８】
0005707271.tif 000009
【００６１】
２、ｊ∈｛０、・・・、ｄ−１｝に対して、Ｌ−Ｖｆｙ(ｖｋ(ｔ｜ｊ)、ｖｋ(ｔ｜ｊ０)｜｜ｖｋ(ｔ｜ｊ１)、σ(ｔ｜ｊ))を出力する。
３、Ｌ−Ｖｆｙ(ｖｋ(ｔ)、Ｍ、σ)を出力する。
４、Ｌ−Ｖｆｙ(ｖｋ(ｔ)、ｔ、σ(ｔ))を出力する。
５、２〜４の全てにおいて１を出力していれば処理結果ｂ＝１とし、そうでなければｂ＝０とする。
６、処理結果ｂを出力する。
【００６２】
次に、本実施形態による電子署名システム１の動作例を説明する。図２１は、電子署名装置１０によるＦＳＬＲ鍵生成処理の動作例を示すフローチャートである。
電子署名装置１０の鍵生成部１４は、上述したような二分木を示す情報（例えば配列）を生成して鍵記憶部１５に記憶させる。また、二分木におけるノード毎に、ＬＲ署名鍵（ｓｋ）と、ＬＲ検証鍵（ｖｋ）とを生成し、各ノードに対応付けて鍵記憶部１５に記憶させる（ステップＳ２１）。そして、親ノードのＬＲ署名鍵（ｓｋ）と、双方の子ノードのＬＲ検証鍵（ｖｋ）とに基づいてＬＲ署名（σ）を生成する（ステップＳ２２）。そして、葉ノードに割り当てられたＬＲ署名鍵（ｓｋ）と、はノードに対応付けられた期間情報とに基づいて、ＬＲ署名（σ）を生成する（ステップＳ２３）。鍵生成部１４は、生成したＬＲ署名鍵（ｓｋ）、ＬＲ検証鍵（ｖｋ）、ＬＲ署名（σ）に基づいてＦＳＬＲ署名鍵（ＳＫ０、０）とＦＳＬＲ検証鍵（ＶＫ）とを出力する（ステップＳ２４）。
【００６３】
図２２は、検証装置２０によるＦＳＬＲ検証処理の動作例を示すフローチャートである。検証装置２０の入力部２１は、メッセージ（Ｍ）とＦＳＬＲ署名（Σ）との入力を受け付ける（ステップＳ３１）。検証部２４が、検証アルゴリズム記憶部２３に記憶されている検証アルゴリズムを読み出し、読み出した検証アルゴリズムによりメッセージ（Ｍ）に対するＦＳＬＲ署名（Σ）の検証を行う（ステップＳ３２）。検証部２４が、ＦＳＬＲ署名（Σ）に含まれる全てのＬＲ署名（σ）について検証成功したと判定すれば（ステップＳ３２：ＹＥＳ）、検証成功の検証結果を出力する（ステップＳ３３）。検証部２４が、ＦＳＬＲ署名（Σ）に含まれるＬＲ署名（σ）のうちいずれかについて検証失敗したと判定すれば（ステップＳ３２：ＮＯ）、検証失敗の検証結果を出力する（ステップＳ３４）。
【００６４】
なお、本実施形態においては、初期の鍵生成段階にて二分木の各ノードに対応する要素を生成しておくようにしても良いが、鍵の要素のうち、全ての要素ではなく、そのピリオドにおいて必要となる要素のみを生成し、鍵記憶部１５に記憶させておくこともできる。ここでは、必要でなくなった要素を削除することもできる。例えば上述の例において、ピリオド「０００」の時点では、図１６において破線に囲まれて示した要素のみを記憶させておくことができる。すなわち、第１の実施形態においては、初期時点において、期間Ｔに含まれる全ての期間に対応する複数のＬＲ署名鍵ｓｋ０、０〜ｓｋＴ−１、０を予め生成しておく必要があるが、第２の実施形態によれば、そのピリオドにおける要素のみを、鍵更新の度に更新して鍵記憶部１５に記憶させることができる。これにより、鍵記憶部１５に記憶させておく情報の量を、第１の実施形態に比べて低減させることができる。これにより、電子署名装置１０におけるメモリ消費量や、鍵漏えいのリスクを低減させることが可能となる。
【００６５】
なお、本発明における処理部の機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより電子署名処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータシステム」は、ホームページ提供環境（あるいは表示環境）を備えたＷＷＷシステムも含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。
【００６６】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【符号の説明】
【００６７】
１  電子署名システム
１０  電子署名装置
１１  入力部
１２  出力部
１３  生成アルゴリズム記憶部
１４  鍵生成部
１５  鍵記憶部
１６  期間更新部
１７  鍵更新部
１８  署名生成部
２０  検証装置
２１  入力部
２２  出力部
２３  検証アルゴリズム記憶部
２４  検証部
【図１】
0005707271.tif 000010
【図２】
0005707271.tif 000011
【図３】
0005707271.tif 000012
【図４】
0005707271.tif 000013
【図５】
0005707271.tif 000014
【図６】
0005707271.tif 000015
【図７】
0005707271.tif 000016
【図８】
0005707271.tif 000017
【図９】
0005707271.tif 000018
【図１０】
0005707271.tif 000019
【図１１】
0005707271.tif 000020
【図１２】
0005707271.tif 000021
【図１３】
0005707271.tif 000022
【図１４】
0005707271.tif 000023
【図１５】
0005707271.tif 000024
【図１６】
0005707271.tif 000025
【図１７】
0005707271.tif 000026
【図１８】
0005707271.tif 000027
【図１９】
0005707271.tif 000028
【図２０】
0005707271.tif 000029
【図２１】
0005707271.tif 000030
【図２２】
0005707271.tif 000031