"Leakage-Resilient方式に基づくLR署名鍵とLR検証鍵とを生成する鍵生成アルゴリズムと、前記LR署名鍵を更新する鍵更新アルゴリズムと、入力されるメッセージと前記LR署名鍵とに基づいてLR署名を生成する署名生成アルゴリズムとが記憶されている生成アルゴリズム記憶部と、前記鍵生成アルゴリズムによって生成された前記LR署名鍵が記憶される鍵記憶部と、前記鍵生成アルゴリズムに基づいて、複数の期間毎に対応付けられた前記LR署名鍵と前記LR検証鍵との組み合わせを生成し、生成した複数のLR署名鍵を前記鍵記憶部に記憶させ、生成した複数のLR検証鍵を出力する鍵生成部と、期間更新要求が入力されると、前記鍵記憶部に記憶されている、前記複数の期間毎に対応付けられた前記LR署名鍵のうち、最も早い期間に対応付けられた前記LR署名鍵を削除し、削除されていない前記LR署名鍵を前記鍵更新アルゴリズムにより更新する期間更新部と、入力されるメッセージと、記前鍵記憶部に記憶されている、前記複数の期間毎に対応付けられた前記LR署名鍵のうち、最も早い期間に対応付けられた前記LR署名鍵とに基づいて生成された前記LR署名を、前記メッセージに対するFSLR署名として出力する署名生成部と、を有する電子署名装置と、前記Leakage-Resilient方式に基づくLR署名を検証する検証アルゴリズムが記憶されている検証アルゴリズム記憶部と、前記LR署名を生成した前記LR署名鍵に対応する前記LR検証鍵に基づいて、前記FSLR署名を検証する検証部と、を有する検証装置と、を備えることを特徴とする電子署名システム。鍵更新要求が入力されると、前記鍵記憶部に記憶されている複数の前記LR署名鍵を、前記鍵更新アルゴリズムにより更新する鍵更新部と、を備えることを特徴とする請求項1に記載の電子署名システム。Leakage-Resilient方式に基づくLR署名鍵とLR検証鍵とを生成する鍵生成アルゴリズムと、前記LR署名鍵を更新する鍵更新アルゴリズムと、入力されるメッセージと前記LR署名鍵とに基づいてLR署名を生成する署名生成アルゴリズムとが記憶されている生成アルゴリズム記憶部と、複数の期間毎に、当該期間を識別する期間情報を対応付けた同レベルの複数の葉ノードを有する二分木の各ノードに、前記鍵生成アルゴリズムにより生成したLR署名鍵とLR検証鍵とを割り当て、前記二分木における葉ノード以外のノード毎に、親ノードに割り当てられたLR署名鍵と、当該親ノードに対する双方の子ノードに割り当てられたLR検証鍵を結合した情報とに基づいて前記署名生成アルゴリズムによりLR署名を生成し、前記葉ノードに割り当てられた前記LR署名鍵と、当該葉ノードに対応付けられた前記期間情報とに基づいて前記署名生成アルゴリズムによりLR署名を生成し、生成した複数の前記LR署名と、前記葉ノードに割り当てられたLR署名鍵及びLR検証鍵と、前記親ノードに対して左の子ノードに割り当てられたLR検証鍵と、当該親ノードに対して右の子ノードに割り当てられたLR署名鍵及びLR検証鍵とに基づいてFSLR署名鍵を生成し、前記二分木における根ノードに割り当てた前記LR検証鍵を、当該FSLR署名鍵に対応するFSLR検証鍵として出力する鍵生成部と、期間更新要求が入力されると、前記二分木において最も左の葉ノードを削除し、当該葉ノード以外の各ノードに割り当てられた前記LR署名鍵と前記LR検証鍵と、当該LR署名鍵に基づいて生成された前記LR署名とに基づいて前記FSLR署名鍵を生成する期間更新部と、前記期間更新要求が入力されると、前記二分木における各ノードに割り当てられた前記LR署名鍵を前記鍵更新アルゴリズムにより更新し、更新したLR署名鍵が含まれる各ノードに割り当てられた前記LR署名鍵と前記LR検証鍵と、当該LR署名鍵に基づいて生成された前記LR署名とに基づいて前記FSLR署名鍵を生成する鍵更新部と、入力されるメッセージと前記葉ノードに割り当てた前記LR署名鍵とに基づいて前記署名生成アルゴリズムにより生成したLR署名と、前記ノード毎のLR署名鍵に基づいて生成された前記LR署名と、前記LR検証鍵とを、前記メッセージに対するFSLR署名として出力する署名生成部と、を有する電子署名装置と、前記Leakage-Resilient方式に基づくLR署名を検証する検証アルゴリズムが記憶されている検証アルゴリズム記憶部と、前記FSLR署名に含まれる全ての前記LR署名について検証が成功した場合に、検証成功と判定する検証部と、を有する検証装置と、を備えることを特徴とする電子署名システム。前記電子署名装置の前記鍵更新部は、鍵更新要求が入力されると、前記二分木における各ノードに割り当てられた前記LR署名鍵を、前記鍵更新アルゴリズムにより更新し、更新した当該LR署名鍵に基づいて前記FSLR署名鍵を生成することを特徴とする請求項3に記載の電子署名システム。Leakage-Resilient方式に基づくLR署名鍵とLR検証鍵とを生成する鍵生成アルゴリズムと、前記LR署名鍵を更新する鍵更新アルゴリズムと、入力されるメッセージと前記LR署名鍵とに基づいてLR署名を生成する署名生成アルゴリズムとが記憶されている生成アルゴリズム記憶部と、前記鍵生成アルゴリズムによって生成された前記LR署名鍵が記憶される鍵記憶部と、を有する電子署名装置が、前記鍵生成アルゴリズムに基づいて、複数の期間毎に対応付けられた前記LR署名鍵と前記LR検証鍵との組み合わせを生成し、生成した複数のLR署名鍵を前記鍵記憶部に記憶させ、生成した複数のLR検証鍵を出力するステップと、期間更新要求が入力されると、前記鍵記憶部に記憶されている、前記複数の期間毎に対応付けられた前記LR署名鍵のうち、最も早い期間に対応付けられた前記LR署名鍵を削除し、削除されていない前記LR署名鍵を前記鍵更新アルゴリズムにより更新するステップと、入力されるメッセージと、記前鍵記憶部に記憶されている、前記複数の期間毎に対応付けられた前記LR署名鍵のうち、最も早い期間に対応付けられた前記LR署名鍵とに基づいて生成された前記LR署名を、前記メッセージに対するFSLR署名として出力するステップと、前記Leakage-Resilient方式に基づくLR署名を検証する検証アルゴリズムが記憶されている検証アルゴリズム記憶部を有する検証装置が、前記LR署名を生成した前記LR署名鍵に対応する前記LR検証鍵に基づいて、前記FSLR署名を検証するステップと、を備えることを特徴とする電子署名方法。Leakage-Resilient方式に基づくLR署名鍵とLR検証鍵とを生成する鍵生成アルゴリズムと、前記LR署名鍵を更新する鍵更新アルゴリズムと、入力されるメッセージと前記LR署名鍵とに基づいてLR署名を生成する署名生成アルゴリズムとが記憶されている生成アルゴリズム記憶部を有する電子署名装置が、複数の期間毎に、当該期間を識別する期間情報を対応付けた同レベルの複数の葉ノードを有する二分木の各ノードに、前記鍵生成アルゴリズムにより生成したLR署名鍵とLR検証鍵とを割り当て、前記二分木における葉ノード以外のノード毎に、親ノードに割り当てられたLR署名鍵と、当該親ノードに対する双方の子ノードに割り当てられたLR検証鍵を結合した情報とに基づいて前記署名生成アルゴリズムによりLR署名を生成し、前記葉ノードに割り当てられた前記LR署名鍵と、当該葉ノードに対応付けられた前記期間情報とに基づいて前記署名生成アルゴリズムによりLR署名を生成し、生成した複数の前記LR署名と、前記葉ノードに割り当てられたLR署名鍵及びLR検証鍵と、前記親ノードに対して左の子ノードに割り当てられたLR検証鍵と、当該親ノードに対して右の子ノードに割り当てられたLR署名鍵及びLR検証鍵とに基づいてFSLR署名鍵を生成し、前記二分木における根ノードに割り当てた前記LR検証鍵を、当該FSLR署名鍵に対応するFSLR検証鍵として出力するステップと、期間更新要求が入力されると、前記二分木において最も左の葉ノードを削除し、当該葉ノード以外の各ノードに割り当てられた前記LR署名鍵と前記LR検証鍵と、当該LR署名鍵に基づいて生成された前記LR署名とに基づいて前記FSLR署名鍵を生成するステップと、前記期間更新要求が入力されると、前記二分木における各ノードに割り当てられた前記LR署名鍵を前記鍵更新アルゴリズムにより更新し、更新したLR署名鍵が含まれる各ノードに割り当てられた前記LR署名鍵と前記LR検証鍵と、当該LR署名鍵に基づいて生成された前記LR署名とに基づいて前記FSLR署名鍵を生成するステップと、入力されるメッセージと前記葉ノードに割り当てた前記LR署名鍵とに基づいて前記署名生成アルゴリズムにより生成したLR署名と、前記ノード毎のLR署名鍵に基づいて生成された前記LR署名と、前記LR検証鍵とを、前記メッセージに対するFSLR署名として出力するステップと、前記Leakage-Resilient方式に基づくLR署名を検証する検証アルゴリズムが記憶されている検証アルゴリズム記憶部を有する検証装置が、前記FSLR署名に含まれる全ての前記LR署名について検証が成功した場合に、検証成功と判定するステップと、を備えることを特徴とする電子署名方法。しかしながら、サイドチャネル攻撃は日々その精度が向上していると考えられる。その為、LR方式において、現時点における最良のサイドチャネル攻撃を用いた場合、署名方式が許容できる量の情報漏えいしか発生することが無かったとしても、その状況が将来にわたって保証されるわけではない。許容できる量の情報漏えいを超えて情報が漏えいしてしまった場合、LR方式によっては署名鍵情報全てを漏えいする可能性がある。一方、FS方式は、このようなサイドチャネル攻撃を想定したものではない。そこで、署名鍵全体や内部情報の漏えいが両方共起こりうる状況を想定したとしても、過去に生成した署名の信頼性を保証することのできる署名方式による署名を行うことが望ましい。本発明は、このような状況に鑑みてなされたもので、FS方式およびLR方式両方の性質を持つ署名方式を提供する。上述した課題を解決するために、本発明は、Leakage-Resilient方式に基づくLR署名鍵とLR検証鍵とを生成する鍵生成アルゴリズムと、LR署名鍵を更新する鍵更新アルゴリズムと、入力されるメッセージとLR署名鍵とに基づいてLR署名を生成する署名生成アルゴリズムとが記憶されている生成アルゴリズム記憶部と、鍵生成アルゴリズムによって生成されたLR署名鍵が記憶される鍵記憶部と、鍵生成アルゴリズムに基づいて、複数の期間毎に対応付けられたLR署名鍵とLR検証鍵との組み合わせを生成し、生成した複数のLR署名鍵を鍵記憶部に記憶させ、生成した複数のLR検証鍵を出力する鍵生成部と、期間更新要求が入力されると、鍵記憶部に記憶されている、複数の期間毎に対応付けられたLR署名鍵のうち、最も早い期間に対応付けられたLR署名鍵を削除し、削除されていないLR署名鍵を鍵更新アルゴリズムにより更新する期間更新部と、入力されるメッセージと、記前鍵記憶部に記憶されている、複数の期間毎に対応付けられたLR署名鍵のうち、最も早い期間に対応付けられたLR署名鍵とに基づいて生成されたLR署名を、メッセージに対するFSLR署名として出力する署名生成部と、を有する電子署名装置と、Leakage-Resilient方式に基づくLR署名を検証する検証アルゴリズムが記憶されている検証アルゴリズム記憶部と、LR署名を生成したLR署名鍵に対応するLR検証鍵に基づいて、FSLR署名を検証する検証部と、を有する検証装置と、を備えることを特徴とする電子署名システムである。また、本発明は、鍵更新要求が入力されると、鍵記憶部に記憶されている複数のLR署名鍵を、鍵更新アルゴリズムにより更新する鍵更新部と、を備えることを特徴とする。また、本発明は、Leakage-Resilient方式に基づくLR署名鍵とLR検証鍵とを生成する鍵生成アルゴリズムと、LR署名鍵を更新する鍵更新アルゴリズムと、入力されるメッセージとLR署名鍵とに基づいてLR署名を生成する署名生成アルゴリズムとが記憶されている生成アルゴリズム記憶部と、複数の期間毎に、期間を識別する期間情報を対応付けた同レベルの複数の葉ノードを有する二分木の各ノードに、鍵生成アルゴリズムにより生成したLR署名鍵とLR検証鍵とを割り当て、二分木における葉ノード以外のノード毎に、親ノードに割り当てられたLR署名鍵と、親ノードに対する双方の子ノードに割り当てられたLR検証鍵を結合した情報とに基づいて署名生成アルゴリズムによりLR署名を生成し、葉ノードに割り当てられたLR署名鍵と、葉ノードに対応付けられた期間情報とに基づいて署名生成アルゴリズムによりLR署名を生成し、生成した複数のLR署名と、葉ノードに割り当てられたLR署名鍵及びLR検証鍵と、親ノードに対して左の子ノードに割り当てられたLR検証鍵と、親ノードに対して右の子ノードに割り当てられたLR署名鍵及びLR検証鍵とに基づいてFSLR署名鍵を生成し、二分木における根ノードに割り当てたLR検証鍵を、FSLR署名鍵に対応するFSLR検証鍵として出力する鍵生成部と、期間更新要求が入力されると、二分木において最も左の葉ノードを削除し、葉ノード以外の各ノードに割り当てられたLR署名鍵とLR検証鍵と、LR署名鍵に基づいて生成されたLR署名とに基づいてFSLR署名鍵を生成する期間更新部と、期間更新要求が入力されると、二分木における各ノードに割り当てられたLR署名鍵を鍵更新アルゴリズムにより更新し、更新したLR署名鍵が含まれる各ノードに割り当てられたLR署名鍵とLR検証鍵と、LR署名鍵に基づいて生成されたLR署名とに基づいてFSLR署名鍵を生成する鍵更新部と、入力されるメッセージと葉ノードに割り当てたLR署名鍵とに基づいて署名生成アルゴリズムにより生成したLR署名と、ノード毎のLR署名鍵に基づいて生成されたLR署名と、LR検証鍵とを、メッセージに対するFSLR署名として出力する署名生成部と、を有する電子署名装置と、Leakage-Resilient方式に基づくLR署名を検証する検証アルゴリズムが記憶されている検証アルゴリズム記憶部と、FSLR署名に含まれる全てのLR署名について検証が成功した場合に、検証成功と判定する検証部と、を有する検証装置と、を備えることを特徴とする電子署名システムである。また、本発明は、電子署名装置の鍵更新部は、鍵更新要求が入力されると、二分木における各ノードに割り当てられたLR署名鍵を、鍵更新アルゴリズムにより更新し、更新したLR署名鍵に基づいてFSLR署名鍵を生成することを特徴とする。また、本発明は、Leakage-Resilient方式に基づくLR署名鍵とLR検証鍵とを生成する鍵生成アルゴリズムと、LR署名鍵を更新する鍵更新アルゴリズムと、入力されるメッセージとLR署名鍵とに基づいてLR署名を生成する署名生成アルゴリズムとが記憶されている生成アルゴリズム記憶部と、鍵生成アルゴリズムによって生成されたLR署名鍵が記憶される鍵記憶部と、を有する電子署名装置が、鍵生成アルゴリズムに基づいて、複数の期間毎に対応付けられたLR署名鍵とLR検証鍵との組み合わせを生成し、生成した複数のLR署名鍵を鍵記憶部に記憶させ、生成した複数のLR検証鍵を出力するステップと、期間更新要求が入力されると、鍵記憶部に記憶されている、複数の期間毎に対応付けられたLR署名鍵のうち、最も早い期間に対応付けられたLR署名鍵を削除し、削除されていないLR署名鍵を鍵更新アルゴリズムにより更新するステップと、入力されるメッセージと、記前鍵記憶部に記憶されている、複数の期間毎に対応付けられたLR署名鍵のうち、最も早い期間に対応付けられたLR署名鍵とに基づいて生成されたLR署名を、メッセージに対するFSLR署名として出力するステップと、Leakage-Resilient方式に基づくLR署名を検証する検証アルゴリズムが記憶されている検証アルゴリズム記憶部を有する検証装置が、LR署名を生成したLR署名鍵に対応するLR検証鍵に基づいて、FSLR署名を検証するステップと、を備えることを特徴とする電子署名方法である。また、本発明は、Leakage-Resilient方式に基づくLR署名鍵とLR検証鍵とを生成する鍵生成アルゴリズムと、LR署名鍵を更新する鍵更新アルゴリズムと、入力されるメッセージとLR署名鍵とに基づいてLR署名を生成する署名生成アルゴリズムとが記憶されている生成アルゴリズム記憶部を有する電子署名装置が、複数の期間毎に、期間を識別する期間情報を対応付けた同レベルの複数の葉ノードを有する二分木の各ノードに、鍵生成アルゴリズムにより生成したLR署名鍵とLR検証鍵とを割り当て、二分木における葉ノード以外のノード毎に、親ノードに割り当てられたLR署名鍵と、親ノードに対する双方の子ノードに割り当てられたLR検証鍵を結合した情報とに基づいて署名生成アルゴリズムによりLR署名を生成し、葉ノードに割り当てられたLR署名鍵と、葉ノードに対応付けられた期間情報とに基づいて署名生成アルゴリズムによりLR署名を生成し、生成した複数のLR署名と、葉ノードに割り当てられたLR署名鍵及びLR検証鍵と、親ノードに対して左の子ノードに割り当てられたLR検証鍵と、親ノードに対して右の子ノードに割り当てられたLR署名鍵及びLR検証鍵とに基づいてFSLR署名鍵を生成し、二分木における根ノードに割り当てたLR検証鍵を、FSLR署名鍵に対応するFSLR検証鍵として出力するステップと、期間更新要求が入力されると、二分木において最も左の葉ノードを削除し、葉ノード以外の各ノードに割り当てられたLR署名鍵とLR検証鍵と、LR署名鍵に基づいて生成されたLR署名とに基づいてFSLR署名鍵を生成するステップと、期間更新要求が入力されると、二分木における各ノードに割り当てられたLR署名鍵を鍵更新アルゴリズムにより更新し、更新したLR署名鍵が含まれる各ノードに割り当てられたLR署名鍵とLR検証鍵と、LR署名鍵に基づいて生成されたLR署名とに基づいてFSLR署名鍵を生成するステップと、入力されるメッセージと葉ノードに割り当てたLR署名鍵とに基づいて署名生成アルゴリズムにより生成したLR署名と、ノード毎のLR署名鍵に基づいて生成されたLR署名と、LR検証鍵とを、メッセージに対するFSLR署名として出力するステップと、Leakage-Resilient方式に基づくLR署名を検証する検証アルゴリズムが記憶されている検証アルゴリズム記憶部を有する検証装置が、FSLR署名に含まれる全てのLR署名について検証が成功した場合に、検証成功と判定するステップと、を備えることを特徴とする電子署名方法である。以上説明したように、本発明によれば、電子署名装置が、LR方式の鍵生成アルゴリズムによりLR署名鍵とLR検証鍵とを生成し、生成したLR署名鍵を、一方向性を持つように期間毎に更新し、検証装置は、対応するLR検証鍵により検証処理を行うようにしたので、FS方式およびLR方式両方の性質を持つ署名方式を提供することができる。以下、本発明の一実施形態について、図面を参照して説明する。<第1の実施形態>図1は、本発明の第1の実施形態による電子署名システム1の構成を示すブロック図である。電子署名システム1は、電子署名装置10と、検証装置20とを備えており、Forward-Secure方式以下、FS方式とLeakage-Resilient方式以下、LR方式との両方の性質を持つ署名方式を提供する。まず、FS方式について説明する。デジタル署名方式において、もっとも大きな脅威の一つは署名鍵の漏えいである。署名鍵が漏えいしてしまうと、署名方式のライフサイクル全体において、署名の偽造が容易にできてしまう。そこで、FS方式では、このような脅威に対し、署名方式のライフサイクルをピリオドと呼ばれる期間時間間隔に分割し、検証鍵を固定としたまま、署名鍵をピリオド毎に更新する。これにより、現在のピリオドの署名鍵が漏えいしたとしても、過去のピリオドの署名鍵で生成した署名については、偽造を困難にすることを可能としている。上述の非特許文献1には、BellareらによるFS方式が記載されている。ここでは、二分木を用いた構成が示されており、署名鍵は、一般的な署名方式の鍵生成アルゴリズムで生成された署名鍵、検証鍵、および署名生成アルゴリズムで生成された署名から構成されている。署名鍵の構成要素の中には、ピリオドを更新しても長期にわたり保持している必要のあるものが存在する。また、署名鍵の構成要素のうち、検証鍵および署名はたとえ全て漏えいしたとしても署名方式の安全性には影響しない。一方、署名鍵の構成要素のうち、署名鍵の情報が部分的に漏えいすることは安全性に影響があるため、ランダマイズすることによる更新が必要である。次に、LR方式について説明する。既存のデジタル署名に対する安全性のモデルでは、署名方式において利用されている署名鍵や内部の乱数情報、または署名生成時の内部状態についての漏えいに関しては定式化されていない。しかし、実世界においては署名方式を実装したハードウェアに対してサイドチャネル攻撃を行う事により、それらのさまざまな情報を得ることが起こり得る。そのため、既存の安全性のモデルにおいて証明されたとしてもサイドチャネル攻撃が考えられる状況おいて安全性が満たされているとは言えない。そこで、LR方式では、既存のデジタル署名のモデルにおいて考慮されていなかったサイドチャネル攻撃などによるさまざまな情報の取得を、偽造者に許可する形でセキュリティモデルを定義している。各署名方式により様々なセキュリティモデルの定義が存在する。上述の非特許文献2には、BoyleらによるLR方式が示されている。このようなFS方式とLR方式とは、上述のように異なる課題、目的を持って研究されているものであるが、本実施形態では、署名鍵を構成する要素を、すべてBoyleらによるLR方式の鍵生成アルゴリズムで生成し、ピリオド毎に更新することで、LR方式とFS方式との双方の方式の性質をもつ署名方式を構成する。以下の説明においては、このような電子署名の方式をFSLR方式という。FSLR方式では、LR方式と同様に、サイドチャネル攻撃などによる署名方式の内部情報の漏えいについて考慮する。さらに、ある時点において署名方式の署名鍵の情報がすべて漏えいしてしまう事を想定し、FS方式の性質も具備するものとする。LR方式の性質を持つためには、上述のように鍵更新をすることによる署名鍵のランダマイズが必要である。FS方式の性質を持つためには,ピリオドの概念が必要であり、ピリオド変更時に鍵を更新するが、その時の更新が一方向性を持つ必要がある。上述のようなFS方式とLR方式とを組み合わせることにより、FS方式の署名鍵をランダマイズし、FSLR方式を実現することが可能である。以下、FSLR方式に基づいて生成する署名鍵をFSLR署名鍵SKt、itは期間ピリオド、iはピリオド内での鍵更新回数といい、検証鍵をFSLR検証鍵VKといい、FSLR署名鍵に基づいて生成された署名をFSLR署名Σという。また、LR方式の署名鍵をLR署名鍵skといい、検証鍵をLR検証鍵vkといい、LR署名鍵に基づいて生成された署名をLR署名σという。図2は、本実施形態によるFSLR方式の概要を示す図である。FSLR方式では、電子署名装置10が、FSLR署名鍵SK0、0とFSLR検証鍵VKとを生成し、FSLR検証鍵VKを公開する。そして、電子署名装置10は、任意のタイミングでFSLR署名鍵SK0、0のピリオド更新を行い、FSLR署名鍵SKSK1、0を生成する。この時点で、FSLR署名鍵SK0、0は無効化され、FSLR署名鍵SKSK1、0が有効になる。このように、ピリオド毎にFSLR署名鍵SKt、iの更新を行い、FSLR署名Σを生成する際には、その時点で有効なFSLR署名鍵SKt、iを用いてFSLR署名Σを生成する。FSLR検証鍵VKは、全てのピリオドにおいて同一の鍵を用いることができる。また、ピリオド内においても、FSLR署名鍵SKt、iを更新し、FSLR署名鍵SKt、i1を生成することができる。この時点で、FSLR署名鍵SKt、iは無効化され、FSLR署名鍵SKSKt、i1が有効になる。これにより、例えばピリオドtにおいてFSLR署名鍵SKSKt、nが漏えいした場合でも、ピリオドt-1以前のFSLR署名Σを偽造することが困難であるようにすることができる。すなわち、FS方式の電子署名と、LR方式の電子署名との双方の特徴を持つFSLR方式の電子署名を行うことができる。図1に戻り、電子署名装置10は、入力部11と、出力部12と、生成アルゴリズム記憶部13と、鍵生成部14と、鍵記憶部15と、期間更新部16と、鍵更新部17と、署名生成部18とを備えたコンピュータ装置である。電子署名装置10には、例えば、いわゆるPCPersonalComputerや、ICIntegratedCircuitカードなどが適用できる。入力部11は、情報の入力を受け付ける。例えば、電子署名装置10がPCであれば、キーボードやマウス、ICカードリーダ等の入力デバイスであり、電子署名装置10がICカードであれば、外部のICカードリーダと通信する通信部である。入力部11には、ユーザにより、任意のタイミングで期間更新要求や鍵更新要求が入力される。ここで、任意のタイミングとは、例えば期間、電子署名装置10による署名の生成回数等によって、FSLR方式の管理者等によって予め定められたタイミングでも良い。出力部12は、電子署名装置10によって生成される、FSLR検証鍵やFSLR署名等の各種情報を出力する。出力部12は、例えば、生成した情報をICカード等に書き込むICカードリータ等のデバイスである。生成アルゴリズム記憶部13には、上述したようなLR方式に基づくLR署名鍵とLR検証鍵とを生成する鍵生成アルゴリズムL-KGと、LR署名鍵を更新する鍵更新アルゴリズムL-Kupdと、入力されるメッセージとLR署名鍵とに基づいてLR署名を生成する署名生成アルゴリズムL-Sigとが記憶されている。このような鍵生成アルゴリズムL-KGと、鍵更新アルゴリズムL-Kupdと、署名生成アルゴリズムL-Sigと、後述する検証アルゴリズムL-Vfyとは、上述の文献2に記載されたアルゴリズムを用いる。図3は、これらのアルゴリズムと文献2に記載されたアルゴリズムとの対応関係を示す図である。本実施形態における鍵生成アルゴリズムL-KGと、鍵更新アルゴリズムL-Kupdと、署名生成アルゴリズムL-Sigと、検証アルゴリズムL-Vfyとは、非特許文献2におけるKeyGenと、Refreshと、Signと、Verifyとに対応する。鍵生成アルゴリズムL-KGは、セキュリティパラメタkを入力とし、初期署名鍵sk0、検証鍵vkを出力するsk0、vk←L-KG1k。ここで、本実施形態において、例えばアルゴリズムFがxを入力とし、内部に乱数rを用いた確率的アルゴリズムによりyを出力する場合、y←Fxと表記する。アルゴリズムFがxおよび乱数情報rを入力とし、確定的アルゴリズムによりyを出力する場合、y:=Fx、rと表記する。x=yと表記するときは、条件式としてxとyとが等しいことを示す。鍵更新アルゴリズムL-Kupdは、署名鍵skiを入力とし、更新後の署名鍵ski1を出力するski1←L-Kupdski。署名生成アルゴリズムL-Sigは、署名鍵ski、メッセージMを入力とし、署名σを出力するσ←L-Sigski、M。鍵生成部14は、生成アルゴリズム記憶部13に記憶されている鍵生成アルゴリズムL-KGを読み出し、読み出した鍵生成アルゴリズムL-KGに基づいて、複数の期間毎に対応付けられたLR署名鍵とLR検証鍵との組み合わせを生成し、生成した複数のLR署名鍵であるFSLR署名鍵を鍵記憶部15に記憶させ、生成した複数のLR検証鍵であるFSLR検証鍵を出力する。例えば、ピリオドの総数をTとすると、図4に示すように、複数のLR検証鍵vk0~vkT-1を生成し、FSLR検証鍵であるVKとする。また、複数のLR署名鍵sk0、0~skT-1、0を生成し、ピリオド0のFSLR署名鍵であるSK0、0とする。具体的には、鍵生成部14は、以下手順によりFSLR署名鍵SK0、0とFSLR検証鍵VKとを生成する。1.s∈{0、、T-1}に対して、sks、0、vks、0←L-KG1kを計算する。2.SK0、0:=sk0、0、sk1、0、sk2、0、、skT-1、0とする。3.VK:=vk0、vk1、、vkT-1とする。4.FSLR署名鍵SK0、0、FSLR検証鍵VKを出力する。ここで、FSLR署名鍵SK0、0は鍵記憶部15に記憶させる。鍵記憶部15には、鍵生成部14によって鍵生成アルゴリズムを用いて生成されたFSLR署名鍵SK0、0が記憶される。期間更新部16は、期間更新要求が入力されると、鍵記憶部15に記憶されている、複数の期間毎に対応付けられたLR署名鍵skのうち、最も早い期間に対応付けられたLR署名鍵を削除し、削除されていないLR署名鍵skを、生成アルゴリズム記憶部13に記憶されている鍵更新アルゴリズムL-Kupdにより更新する。例えば、図5に示すように、ピリオド0からピリオド1への期間更新要求が入力されると、鍵記憶部15に記憶されているSK0、0に含まれる複数のskのうち、sk0、0を削除し、他のsksk1、0、sk2、0、、skT-1、0を鍵更新アルゴリズムL-Kupdにより更新する。具体的には、期間更新部16は、以下手順によりピリオドを更新したFSLR署名鍵を生成する。ここでは、期間更新前のピリオドをtとし、期間更新後のピリオドをt1とする。1.SKt、i:=skt、i、skt1、i、、skT-1、iとおく。2.skt、iを削除する。3.s∈{t1、、T-1}に対して、sks、0←L-Kupdsks、iを計算する。4.SKt1、0:=skt1、0、、skT-1、0とおく。5.ピリオドt1、SKt1、0を出力する。鍵更新部17は、鍵更新要求が入力されると、生成アルゴリズム記憶部13に記憶されている鍵更新アルゴリズムL-Kupdを読み出し、鍵記憶部15に記憶されている複数のLR署名鍵を、読み出した鍵更新アルゴリズムL-Kupdにより更新する。例えば、図6に示すように、鍵記憶部15に記憶されているSKt、iに含まれる複数のskskt、i、、skT-1、iを鍵更新アルゴリズムL-Kupdにより更新する。具体的には、鍵更新部17は、以下手順により更新したFSLR署名鍵を生成する。1.SKt、i:=skt、i、skt1、i、、skT-1、iとおく。2.s∈{t、、T-1}に対して、sks、i1←L-Kupdsks、iを計算する。3.SKt、i1:=skt、i1、、skT-1、i1を出力する。このように、期間更新はピリオドの更新を伴い、鍵の更新も行うアルゴリズムであり、鍵更新はピリオドの更新を伴わずに、鍵の更新を行うアルゴリズムである。署名生成部18は、入力されるメッセージと、鍵記憶部15に記憶されている、複数の期間毎に対応付けられたLR署名鍵のうち、最も早い期間に対応付けられたLR署名鍵とに基づいて生成されたLR署名を、メッセージに対するFSLR署名として出力する。具体的には、生成アルゴリズム記憶部13に記憶されている署名生成アルゴリズムL-Sigを読み出し、図7に示すように、現在のピリオドtに対応するskt、iを用いて、署名アルゴリズムL-SIGによりメッセージMのLR署名を生成する。具体的には、署名生成部18は、以下手順によりFSLR署名Σを出力する。1.σ←L-SIGskt、i、M2.t、Σ:=σを出力する。検証装置20は、電子署名装置10により生成されたFSLR署名を検証するコンピュータ装置である。検証装置20は、入力部21と、出力部22と、検証アルゴリズム記憶部23と、検証部24とを備えている。入力部21は、情報の入力を受け付ける。電子署名装置10と同様に、例えば検証装置20がPCであれば、キーボードやマウス、ICカードリーダ等の入力デバイスであり、検証装置20がICカードであれば、外部のICカードリーダと通信する通信部である。入力部11には、検証の対象となるピリオドt、FSLR検証鍵VK、メッセージM、FSLR署名Σ等の情報が入力される。出力部22は、検証装置20による検証結果を出力する。例えば、出力部12は、検証結果を送信する通信部や、検証結果を表示するディスプレイである。検証アルゴリズム記憶部23には、上述したようなLR方式に基づくLR署名を検証する検証アルゴリズムL-Vfyが記憶されている。検証アルゴリズムL-Vfyは、検証鍵vk、メッセージM、署名σを入力とし、1または0の処理結果bを出力するb←L-Vfyvk、M、σ。次に、本実施形態による電子署名システム1の動作例を説明する。図8は、電子署名装置10によるFSLR鍵生成処理の動作例を示すフローチャートである。電子署名装置10の鍵生成部14は、定められた複数の期間毎に、LR署名鍵とLR検証鍵とを生成するステップS1。生成した複数のLR署名鍵は、FSLR鍵として鍵記憶部15に記憶させる。また、生成した複数のLR検証鍵は、FSLR検証鍵として出力し、公開するステップS3。また、電子署名装置10にメッセージMが入力されると、電子署名装置10の署名生成部18は、生成アルゴリズム記憶部13に記憶されている署名生成アルゴリズムL-Sigを読み出し、現在のピリオドに対応するLR署名鍵skと、メッセージMとに基づいて、FSLR署名Σを生成して出力する。図9は、検証装置20によるFSLR検証処理の動作例を示すフローチャートである。検証装置20の入力部21は、メッセージMとFSLR署名Σとの入力を受け付けるステップS11。検証部24が、検証アルゴリズム記憶部23に記憶されている検証アルゴリズムを読み出し、読み出した検証アルゴリズムによりメッセージMに対するFSLR署名Σの検証を行うステップS12。検証部24が、FSLR署名Σが生成されたピリオドに対応するLR検証鍵によるLR署名σについて検証成功したと判定すればステップS11:YES、検証成功の検証結果を出力するステップS13。検証部24が、検証失敗したと判定すればステップS12:NO、検証失敗の検証結果を出力するステップS14。以上説明したように、本実施形態によれば、LR方式のアルゴリズムを用いて、ピリオド毎に一方向性のある鍵の更新を行うようにした。これにより、FS方式およびLR方式両方の性質を持つ署名方式が提供できる。<第2の実施形態>次に、本発明の第2の実施形態について説明する。本実施形態における電子署名システム1の構成は、第1の実施形態において図1に示した電子署名システム1の構成と同様である。以下、第1の実施形態と異なる処理等について説明する。本実施形態では、BellareらによるFS方式で用いられた二分木を利用したピリオドごとの鍵の更新を用い、署名鍵を構成する要素を、すべてBoyleらによるLR方式の鍵生成アルゴリズムにより生成する。本実施形態における電子署名装置10の鍵生成部14は、生成アルゴリズム記憶部13に記憶されている鍵生成アルゴリズムL-KGと署名生成アルゴリズムL-Sigとを読み出し、読み出したアルゴリズムを用いて、FSLR署名鍵とFSLR検証鍵とを生成する。まず、鍵生成部14は、複数のピリオド毎に、そのピリオドを識別する期間情報を対応付けた同レベルの複数の葉ノードを有する二分木を生成し、鍵記憶部15に記憶させる。図10は、鍵生成部14が生成する二分木の例を示す図である。ここでは、8つのピリオドを示す葉ノードのそれぞれに、000~111の期間情報をノード番号として対応付ける。ノード番号は二進法によるビット列であるとする。根ノードのノード番号はεとする。根ノードεの左の子ノードを0とし、右の子ノードを1としている。さらに、ノード0を親ノードとする左の子ノードを00とし、右の子ノードを01としている。このように、親ノードの左の子ノードには、親ノードのノード番号の末尾に0を付したノード番号を対応付け、親ノードの右の子ノードには、親ノードのノード番号の末尾に1を付したノード番号を対応付けている。この二分木において、以下の表記法を利用する。各ノードのノード番号をωとしたとき、そのビット列表現はω=ω1ω2ωjとする。根ノードはεで表現し、そのビット列表現は空文字とする。深さはdで表す。ノードω=ω1ω2ωjに対して、子ノードをω0=ω1ω2ωj0、ω1=ω1ω2ωj1と表す。ノードω0=ω1ω2ωj0、およびω1=ω1ω2ωj1に対して、親ノードをω=ω1ω2ωjと表す。ノードt=t1t2tdに対し、j∈{1、、d-1}について、t|j=t1t2tjと表し、t|0=εと表す。さらに、t|j0=t1t2tj0、t|j1=t1t2tj1、と表す。二分木において、j=1、、d1に対し、葉ノードtと根ノードとのパス上の深さjにおける兄弟ノードを以下式1のように定義する。ノードω∈{0、1}≦j、j∈{1、、d}に対して、DFωを以下式2のように定義する。このような表記法に沿った、深さd=4の二分木、およびsiblingとDFの例を図11に示す。また、鍵生成部14は、図12に示すように、二分木の各ノードに、生成アルゴリズム記憶部13から読み出した鍵生成アルゴリズムにより生成したLR署名鍵skとLR検証鍵vkとを割り当てる。さらに、図13に示すように、根ノードに割り当てられたLR署名鍵skεと、親ノードに対する双方の子ノードに割り当てられたLR検証鍵を結合した情報vk0||vk1とに基づいて、生成アルゴリズム記憶部13から読み出した署名生成アルゴリズムによりLR署名σεを生成し、鍵記憶部15に記憶させる。鍵生成部14は、図14に示すように、二分木における葉ノード以外のノード毎に、このようなLR署名の生成処理を行う。さらに、鍵生成部14は、図15に示すように、葉ノードに割り当てられたLR署名鍵例えば、sk000と、その葉ノードに対応付けられた期間情報例えば、ノード番号000とに基づいて、生成アルゴリズム記憶部13から読み出した署名生成アルゴリズムによりLR署名例えば、σ000を生成する。そして、図16に破線に囲まれて示すような、生成した複数のLR署名σε、σ0、σ00、σ000、σ001と、葉ノードに割り当てられたLR署名鍵sk000、sk001及びLR検証鍵vk000、vk001と、親ノードに対して左の子ノードに割り当てられたLR検証鍵vk0、vk00と、その親ノードに対して右の子ノードに割り当てられたLR署名鍵sk1、sk01及びLR検証鍵vk1、vk01とを要素として、FSLR署名鍵SK0、0を生成する。例えば、これらの情報を配列に格納することにより、FSLR署名鍵SK0、0を生成する。また、鍵生成部14は、二分木における根ノードεに割り当てたLR検証鍵vkεを、FSLR署名鍵SK0、0に対応するFSLR検証鍵VKとして出力する。このように、FSLR鍵を生成する鍵生成アルゴリズムKgは、セキュリティパラメタkと、ピリオドの総数Tを入力とし、初期ピリオドt、FSLR署名鍵SK0、0、FSLR検証鍵VKを出力するt、sk0、0、vk←Kg1k、T。t:=0とする。これにより、ピリオドtのFSLR署名鍵は、二分木の葉ノードω=tから根ノードεまでのパス上に存在するノード、およびその兄弟ノードに対応させた、L-Kg1kにより生成した鍵で構成される。ピリオドtにおいて、深さjにおけるノード番号ω=t|jの内部ノードに対応させる、署名鍵の更新をi回実施した鍵ペアを、skt|d、i、vkt|j=skt、i、vktと表記する。具体的には、鍵生成部14は、以下手順によりFSLR署名鍵SK0、0とFSLR検証鍵VKとを生成する。1、Tを多項式オーダーの数とし、t:=0logTとする。2、skε、vkε←L-Kg1kを計算する。3、j∈{0、、d-1}に対して、以下を実行する。a、sktj0、0、vkt|j0←L-Kg1kb、skt|j1、0、vk←L-Kg1kc、σ←L-Sig、0、vkvkd、sk、0を削除する。4、σ←L-Sig、0、tを計算する。5、以下式3によりピリオドt、FSLR署名鍵SK0、0、FSLR検証鍵VKを出力する。鍵記憶部15には、鍵生成部14によって生成された二分木が記憶される。期間更新部16は、期間更新要求が入力されると、鍵記憶部15に記憶された二分木において最も左の葉ノードを削除し、その葉ノード以外の各ノードに割り当てられたLR署名鍵とLR検証鍵と、そのLR署名鍵に基づいて生成されたLR署名とに基づいて、ピリオド更新したFSLR署名鍵を生成する。図17に示した図において、破線に囲まれた情報が、ピリオド更新後のピリオド2ノード番号001におけるFSLR署名鍵である。また、図18に示した図において、破線に囲まれた情報が、ピリオド更新後のピリオド3ノード番号010におけるFSLR署名鍵である。すなわち、期間更新部16は、カレントピリオドt、カレントピリオドのFSLR署名鍵SKt、iを入力とし、更新後のピリオドt1、更新後のFSLR署名鍵SKt1、iを出力する。具体的には、期間更新部16は、以下手順によりピリオドを更新したFSLR署名鍵を生成する。1、DFtの深さをj ́とする。2、j∈{0、、j ́-1}に対して、a、ω:=siblingとする。b、ω=⊥のとき、sk、0:=⊥とする。c、ω≠のとき、sk、i1←L-Updskω、iを計算し、sk、0:=sk、i1とする。3、j∈{j ́、、d-1}に対して、以下を実行する。a、、0、vk←L-Kgb、、0、vk←L-Kgc、σ←L-Sig、0、vk||vkd、sk、0を削除する。4、σ←L-Sig、0、t1を計算する。5、以下式4によりピリオドおよびFSLR署名鍵を出力する。鍵更新部17は、期間更新要求が入力されると、二分木における各ノードに割り当てられたLR署名鍵を鍵更新アルゴリズムにより更新し、更新したLR署名鍵が含まれる各ノードに割り当てられたLR署名鍵とLR検証鍵と、そのLR署名鍵に基づいて生成されたLR署名とに基づいて、更新したFSLR署名鍵を生成する。また、鍵更新部17は、鍵更新要求が入力されると、同様に、二分木における各ノードに割り当てられたLR署名鍵を、鍵更新アルゴリズムにより更新し、更新したLR署名鍵に基づいてFSLR署名鍵を生成する。図19は、ピリオド3ノード番号010において行う鍵更新の例を示す図である。すなわち、鍵更新部17は、カレントピリオドのFSLR署名鍵SKt、iを入力とし、更新後のFSLR署名鍵SKt、i1を出力する。具体的には、鍵更新部17は、以下手順により更新したFSLR署名鍵を生成する。1、j∈{0、、d-1}に対して、a、ω:=siblingとする。b、ω=⊥のとき、sk、i1:=⊥とする。c、ω≠のとき、sk、i1←L-Upd、iを計算する。2、以下式5によりFSLR署名鍵SKt、i1を出力する。署名生成部18は、入力されるメッセージと葉ノードに割り当てたLR署名鍵とに基づいて、署名生成アルゴリズムにより生成したLR署名と、ノード毎のLR署名鍵に基づいて生成されたLR署名と、LR検証鍵とを、メッセージに対するFSLR署名Σとして出力する。図20は、ピリオド3ノード番号010において行う署名生成の例を示す図である。すなわち、署名生成部18は、カレントピリオドt、カレントピリオドの署名鍵SKt、i、メッセージMを入力とし、カレントピリオドt、FSLR署名Σを出力する。具体的には、署名生成部18は、以下手順によりFSLR署名Σを出力する。1、ピリオドおよび署名鍵を以下式6のように表記する。2、σ←L-Sig、i、Mを計算する。3、以下式7により、更新後のピリオドおよびFSLR署名を出力する。本実施形態における検証装置20の検証部24は、FSLR署名に含まれる全てのLR署名について検証が成功した場合に、検証成功と判定する。署名が生成されたピリオドt、FSLR検証鍵VK、メッセージM、FSLR署名Σを入力とし、1または0を出力する。具体的には、検証部24は、以下手順により検証結果を出力する。1、ピリオドおよび署名を以下式8のように表記する。2、j∈{0、、d-1}に対して、L-Vfy、vk||vk、σを出力する。3、L-Vfy、M、σを出力する。4、L-Vfy、t、σを出力する。5、2~4の全てにおいて1を出力していれば処理結果b=1とし、そうでなければb=0とする。6、処理結果bを出力する。次に、本実施形態による電子署名システム1の動作例を説明する。図21は、電子署名装置10によるFSLR鍵生成処理の動作例を示すフローチャートである。電子署名装置10の鍵生成部14は、上述したような二分木を示す情報例えば配列を生成して鍵記憶部15に記憶させる。また、二分木におけるノード毎に、LR署名鍵skと、LR検証鍵vkとを生成し、各ノードに対応付けて鍵記憶部15に記憶させるステップS21。そして、親ノードのLR署名鍵skと、双方の子ノードのLR検証鍵vkとに基づいてLR署名σを生成するステップS22。そして、葉ノードに割り当てられたLR署名鍵skと、はノードに対応付けられた期間情報とに基づいて、LR署名σを生成するステップS23。鍵生成部14は、生成したLR署名鍵sk、LR検証鍵vk、LR署名σに基づいてFSLR署名鍵SK0、0とFSLR検証鍵VKとを出力するステップS24。図22は、検証装置20によるFSLR検証処理の動作例を示すフローチャートである。検証装置20の入力部21は、メッセージMとFSLR署名Σとの入力を受け付けるステップS31。検証部24が、検証アルゴリズム記憶部23に記憶されている検証アルゴリズムを読み出し、読み出した検証アルゴリズムによりメッセージMに対するFSLR署名Σの検証を行うステップS32。検証部24が、FSLR署名Σに含まれる全てのLR署名σについて検証成功したと判定すればステップS32:YES、検証成功の検証結果を出力するステップS33。検証部24が、FSLR署名Σに含まれるLR署名σのうちいずれかについて検証失敗したと判定すればステップS32:NO、検証失敗の検証結果を出力するステップS34。なお、本実施形態においては、初期の鍵生成段階にて二分木の各ノードに対応する要素を生成しておくようにしても良いが、鍵の要素のうち、全ての要素ではなく、そのピリオドにおいて必要となる要素のみを生成し、鍵記憶部15に記憶させておくこともできる。ここでは、必要でなくなった要素を削除することもできる。例えば上述の例において、ピリオド000の時点では、図16において破線に囲まれて示した要素のみを記憶させておくことができる。すなわち、第1の実施形態においては、初期時点において、期間Tに含まれる全ての期間に対応する複数のLR署名鍵sk0、0~skT-1、0を予め生成しておく必要があるが、第2の実施形態によれば、そのピリオドにおける要素のみを、鍵更新の度に更新して鍵記憶部15に記憶させることができる。これにより、鍵記憶部15に記憶させておく情報の量を、第1の実施形態に比べて低減させることができる。これにより、電子署名装置10におけるメモリ消費量や、鍵漏えいのリスクを低減させることが可能となる。なお、本発明における処理部の機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより電子署名処理を行ってもよい。なお、ここでいうコンピュータシステムとは、OSや周辺機器等のハードウェアを含むものとする。また、コンピュータシステムは、ホームページ提供環境あるいは表示環境を備えたWWWシステムも含むものとする。また、コンピュータ読み取り可能な記録媒体とは、フレキシブルディスク、光磁気ディスク、ROM、CD-ROM等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらにコンピュータ読み取り可能な記録媒体とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリRAMのように、一定時間プログラムを保持しているものも含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する伝送媒体は、インターネット等のネットワーク通信網や電話回線等の通信回線通信線のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル差分プログラムであっても良い。"