説明

電子署名システム、電子署名方法

【課題】Forward−Secure方式とLeakage−Resilient方式との性質を持つ署名方式を提供する。
【解決手段】電子署名装置が、LR方式の鍵生成アルゴリズムによりLR署名鍵とLR検証鍵とを生成し、生成したLR署名鍵を、一方向性を持つように期間毎に更新し、検証装置は、対応するLR検証鍵により検証処理を行う。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、電子署名の技術に関する。
【背景技術】
【0002】
デジタル署名では、署名鍵や、署名方式が内部で利用する乱数情報などの内部情報が漏えいすることにより、署名方式の安全性を損なうことが考えられる。そこで、Forward−Secure方式(以下、FS方式)とよばれる署名方式が提案されている。FS方式では、署名に用いる署名鍵をある時間間隔、期間(以下、ピリオドともいう)で更新しながら、署名の生成を行う(例えば、非特許文献1参照)。これにより、あるピリオドに対応した署名鍵が漏えいしたとしても、過去に生成した署名の信頼性には影響しないようにすることができる。
あるいは、Leakage−Resilient方式(以下、LR方式)とよばれる署名方式が提案されている。LR方式では、サイドチャネル攻撃による署名方式の内部情報の漏えいに備え、署名方式の各アルゴリズムの処理中に利用する情報が、ある制限された範囲内であれば漏えいしたとしても署名方式の安全性を確保できるよう設計されている(例えば、非特許文献2参照)。
【先行技術文献】
【非特許文献】
【0003】
【非特許文献1】Mihir Bellare、Sara K.Miner、“A Forward−Secure Digital Signature Scheme.”CRYPTO’99、LNCS 1666、pp.431−448、1999.
【非特許文献2】Elette Boyle、Gil Segev、Daniel Wichs、“Fully Leakage−Resilient Signatures”、インターネットURL:http://eprint.iacr.org/2010/488.pdf
【発明の概要】
【発明が解決しようとする課題】
【0004】
しかしながら、サイドチャネル攻撃は日々その精度が向上していると考えられる。その為、LR方式において、現時点における最良のサイドチャネル攻撃を用いた場合、署名方式が許容できる量の情報漏えいしか発生することが無かったとしても、その状況が将来にわたって保証されるわけではない。許容できる量の情報漏えいを超えて情報が漏えいしてしまった場合、LR方式によっては署名鍵情報全てを漏えいする可能性がある。一方、FS方式は、このようなサイドチャネル攻撃を想定したものではない。
そこで、署名鍵全体や内部情報の漏えいが両方共起こりうる状況を想定したとしても、過去に生成した署名の信頼性を保証することのできる署名方式による署名を行うことが望ましい。
【0005】
本発明は、このような状況に鑑みてなされたもので、FS方式およびLR方式両方の性質を持つ署名方式を提供する。
【課題を解決するための手段】
【0006】
上述した課題を解決するために、本発明は、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署名を検証する検証部と、を有する検証装置と、を備えることを特徴とする電子署名システムである。
【0007】
また、本発明は、鍵更新要求が入力されると、鍵記憶部に記憶されている複数のLR署名鍵を、鍵更新アルゴリズムにより更新する鍵更新部と、を備えることを特徴とする。
【0008】
また、本発明は、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署名について検証が成功した場合に、検証成功と判定する検証部と、を有する検証装置と、を備えることを特徴とする電子署名システムである。
【0009】
また、本発明は、電子署名装置の鍵更新部は、鍵更新要求が入力されると、二分木における各ノードに割り当てられたLR署名鍵を、鍵更新アルゴリズムにより更新し、更新したLR署名鍵に基づいてFSLR署名鍵を生成することを特徴とする。
【0010】
また、本発明は、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署名を検証するステップと、を備えることを特徴とする電子署名方法である。
【0011】
また、本発明は、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署名について検証が成功した場合に、検証成功と判定するステップと、を備えることを特徴とする電子署名方法である。
【発明の効果】
【0012】
以上説明したように、本発明によれば、電子署名装置が、LR方式の鍵生成アルゴリズムによりLR署名鍵とLR検証鍵とを生成し、生成したLR署名鍵を、一方向性を持つように期間毎に更新し、検証装置は、対応するLR検証鍵により検証処理を行うようにしたので、FS方式およびLR方式両方の性質を持つ署名方式を提供することができる。
【図面の簡単な説明】
【0013】
【図1】本発明の一実施形態による電子署名システムの構成例を示すブロック図である。
【図2】本発明の一実施形態によるFSLR方式の概要を示す図である。
【図3】本発明の一実施形態により利用するアルゴリズムの例を示す図である。
【図4】本発明の第1の実施形態によるLR署名鍵とLR検証鍵との生成例を示す図である。
【図5】本発明の第1の実施形態によるFSLR署名鍵の期間更新の例を示す図である。
【図6】本発明の第1の実施形態によるFSLR署名鍵の鍵更新の例を示す図である。
【図7】本発明の第1の実施形態によるFSLR署名の例を示す図である。
【図8】本発明の第1の実施形態による電子署名装置のFSLR鍵生成処理の動作例を示すフローチャートである。
【図9】本発明の第1の実施形態による検証装置のFSLR検証処理の動作例を示すフローチャートである。
【図10】本発明の第2の実施形態による二分木の例を示す図である。
【図11】本発明の第2の実施形態による二分木の表記法の例を示す図である。
【図12】本発明の第2の実施形態によるLR署名鍵とLR検証鍵との生成例を示す図である。
【図13】本発明の第2の実施形態によるLR署名の生成例を示す図である。
【図14】本発明の第2の実施形態によるLR署名の生成例を示す図である。
【図15】本発明の第2の実施形態によるLR署名の生成例を示す図である。
【図16】本発明の第2の実施形態によるFSLR署名鍵の例を示す図である。
【図17】本発明の第2の実施形態によるFSLR署名鍵の期間更新の例を示す図である。
【図18】本発明の第2の実施形態によるFSLR署名鍵の期間更新の例を示す図である。
【図19】本発明の第2の実施形態によるFSLR署名鍵の鍵更新の例を示す図である。
【図20】本発明の第2の実施形態によるFSLR署名の例を示す図である。
【図21】本発明の第2の実施形態による電子署名装置のFSLR鍵生成処理の動作例を示すフローチャートである。
【図22】本発明の第2の実施形態による検証装置のFSLR検証処理の動作例を示すフローチャートである。
【発明を実施するための形態】
【0014】
以下、本発明の一実施形態について、図面を参照して説明する。
<第1の実施形態>
図1は、本発明の第1の実施形態による電子署名システム1の構成を示すブロック図である。電子署名システム1は、電子署名装置10と、検証装置20とを備えており、Forward−Secure方式(以下、FS方式)とLeakage−Resilient方式(以下、LR方式)との両方の性質を持つ署名方式を提供する。
【0015】
まず、FS方式について説明する。デジタル署名方式において、 もっとも大きな脅威の一つは署名鍵の漏えいである。署名鍵が漏えいしてしまうと、署名方式のライフサイクル全体において、署名の偽造が容易にできてしまう。そこで、FS方式では、このような脅威に対し、署名方式のライフサイクルを「ピリオド」と呼ばれる期間(時間間隔)に分割し、検証鍵を固定としたまま、署名鍵をピリオド毎に更新する。これにより、現在のピリオドの署名鍵が漏えいしたとしても、過去のピリオドの署名鍵で生成した署名については、偽造を困難にすることを可能としている。上述の非特許文献1には、BellareらによるFS方式が記載されている。ここでは、二分木を用いた構成が示されており、署名鍵は、一般的な署名方式の鍵生成アルゴリズムで生成された署名鍵、検証鍵、および署名生成アルゴリズムで生成された署名から構成されている。署名鍵の構成要素の中には、ピリオドを更新しても長期にわたり保持している必要のあるものが存在する。また、署名鍵の構成要素のうち、検証鍵および署名はたとえ全て漏えいしたとしても署名方式の安全性には影響しない。一方、署名鍵の構成要素のうち、署名鍵の情報が部分的に漏えいすることは安全性に影響があるため、ランダマイズすることによる更新が必要である。
【0016】
次に、LR方式について説明する。既存のデジタル署名に対する安全性のモデルでは、署名方式において利用されている署名鍵や内部の乱数情報、または署名生成時の内部状態についての漏えいに関しては定式化されていない。しかし、実世界においては署名方式を実装したハードウェアに対してサイドチャネル攻撃を行う事により、それらのさまざまな情報を得ることが起こり得る。そのため、既存の安全性のモデルにおいて証明されたとしてもサイドチャネル攻撃が考えられる状況おいて安全性が満たされているとは言えない。そこで、LR方式では、既存のデジタル署名のモデルにおいて考慮されていなかったサイドチャネル攻撃などによるさまざまな情報の取得を、偽造者に許可する形でセキュリティモデルを定義している。各署名方式により様々なセキュリティモデルの定義が存在する。上述の非特許文献2には、BoyleらによるLR方式が示されている。
【0017】
このようなFS方式とLR方式とは、上述のように異なる課題、目的を持って研究されているものであるが、本実施形態では、署名鍵を構成する要素を、すべてBoyleらによるLR方式の鍵生成アルゴリズムで生成し、ピリオド毎に更新することで、LR方式とFS方式との双方の方式の性質をもつ署名方式を構成する。以下の説明においては、このような電子署名の方式をFSLR方式という。FSLR方式では、LR方式と同様に、サイドチャネル攻撃などによる署名方式の内部情報の漏えいについて考慮する。さらに、ある時点において署名方式の署名鍵の情報がすべて漏えいしてしまう事を想定し、FS方式の性質も具備するものとする。LR方式の性質を持つためには、上述のように鍵更新をすることによる署名鍵のランダマイズが必要である。FS方式の性質を持つためには,ピリオドの概念が必要であり、ピリオド変更時に鍵を更新するが、その時の更新が一方向性を持つ必要がある。上述のようなFS方式とLR方式とを組み合わせることにより、FS方式の署名鍵をランダマイズし、FSLR方式を実現することが可能である。以下、FSLR方式に基づいて生成する署名鍵をFSLR署名鍵(SKt、i)(tは期間(ピリオド)、iはピリオド内での鍵更新回数)といい、検証鍵をFSLR検証鍵(VK)といい、FSLR署名鍵に基づいて生成された署名をFSLR署名(Σ)という。また、LR方式の署名鍵をLR署名鍵(sk)といい、検証鍵をLR検証鍵(vk)といい、LR署名鍵に基づいて生成された署名をLR署名(σ)という。
【0018】
図2は、本実施形態によるFSLR方式の概要を示す図である。FSLR方式では、電子署名装置10が、FSLR署名鍵(SK0、0)とFSLR検証鍵(VK)とを生成し、FSLR検証鍵(VK)を公開する。そして、電子署名装置10は、任意のタイミングでFSLR署名鍵(SK0、0)のピリオド更新を行い、FSLR署名鍵SK(SK1、0)を生成する。この時点で、FSLR署名鍵(SK0、0)は無効化され、FSLR署名鍵SK(SK1、0)が有効になる。このように、ピリオド毎にFSLR署名鍵(SKt、i)の更新を行い、FSLR署名(Σ)を生成する際には、その時点で有効なFSLR署名鍵(SKt、i)を用いてFSLR署名(Σ)を生成する。FSLR検証鍵(VK)は、全てのピリオドにおいて同一の鍵を用いることができる。また、ピリオド内においても、FSLR署名鍵(SKt、i)を更新し、FSLR署名鍵(SKt、i+1)を生成することができる。この時点で、FSLR署名鍵(SKt、i)は無効化され、FSLR署名鍵SK(SKt、i+1)が有効になる。これにより、例えばピリオドtにおいてFSLR署名鍵SK(SKt、n)が漏えいした場合でも、ピリオドt−1以前のFSLR署名(Σ)を偽造することが困難であるようにすることができる。すなわち、FS方式の電子署名と、LR方式の電子署名との双方の特徴を持つFSLR方式の電子署名を行うことができる。
【0019】
図1に戻り、電子署名装置10は、入力部11と、出力部12と、生成アルゴリズム記憶部13と、鍵生成部14と、鍵記憶部15と、期間更新部16と、鍵更新部17と、署名生成部18とを備えたコンピュータ装置である。電子署名装置10には、例えば、いわゆるPC(Personal Computer)や、IC(Integrated Circuit)カードなどが適用できる。
【0020】
入力部11は、情報の入力を受け付ける。例えば、電子署名装置10がPCであれば、キーボードやマウス、ICカードリーダ等の入力デバイスであり、電子署名装置10がICカードであれば、外部のICカードリーダと通信する通信部である。入力部11には、ユーザにより、任意のタイミングで期間更新要求や鍵更新要求が入力される。ここで、任意のタイミングとは、例えば期間、電子署名装置10による署名の生成回数等によって、FSLR方式の管理者等によって予め定められたタイミングでも良い。
【0021】
出力部12は、電子署名装置10によって生成される、FSLR検証鍵やFSLR署名等の各種情報を出力する。出力部12は、例えば、生成した情報をICカード等に書き込むICカードリータ等のデバイスである。
【0022】
生成アルゴリズム記憶部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とに対応する。
【0023】
鍵生成アルゴリズム(L−KG)は、セキュリティパラメタkを入力とし、初期署名鍵sk、検証鍵vkを出力する((sk、vk)←L−KG(1))。ここで、本実施形態において、例えばアルゴリズムFがxを入力とし、内部に乱数(r)を用いた確率的アルゴリズムによりyを出力する場合、y←F(x)と表記する。アルゴリズムFがxおよび乱数情報rを入力とし、確定的アルゴリズムによりyを出力する場合、y:=F(x、r)と表記する。x=yと表記するときは、条件式としてxとyとが等しいことを示す。
鍵更新アルゴリズム(L−Kupd)は、署名鍵skを入力とし、更新後の署名鍵(ski+1)を出力する(ski+1←L−Kupd(sk))。
署名生成アルゴリズム(L−Sig)は、署名鍵sk、メッセージMを入力とし、署名σを出力する(σ←L−Sig(sk、M))。
【0024】
鍵生成部14は、生成アルゴリズム記憶部13に記憶されている鍵生成アルゴリズム(L−KG)を読み出し、読み出した鍵生成アルゴリズム(L−KG)に基づいて、複数の期間毎に対応付けられたLR署名鍵とLR検証鍵との組み合わせを生成し、生成した複数のLR署名鍵であるFSLR署名鍵を鍵記憶部15に記憶させ、生成した複数のLR検証鍵であるFSLR検証鍵を出力する。例えば、ピリオドの総数をTとすると、図4に示すように、複数のLR検証鍵vk〜vkT−1を生成し、FSLR検証鍵であるVKとする。また、複数のLR署名鍵sk0、0〜skT−1、0を生成し、ピリオド0のFSLR署名鍵であるSK0、0とする。
【0025】
具体的には、鍵生成部14は、以下手順によりFSLR署名鍵(SK0、0)とFSLR検証鍵VKとを生成する。
1.s∈{0、・・・、T−1}に対して、(sks、0、vks、0)←L−KG(1)を計算する。
2.SK0、0:=(sk0、0、sk1、0、sk2、0、・・・、skT−1、0)とする。
3.VK:=(vk、vk、・・・、vkT−1)とする。
4.FSLR署名鍵(SK0、0)、FSLR検証鍵(VK)を出力する。ここで、FSLR署名鍵(SK0、0)は鍵記憶部15に記憶させる。
【0026】
鍵記憶部15には、鍵生成部14によって鍵生成アルゴリズムを用いて生成されたFSLR署名鍵(SK0、0)が記憶される。
期間更新部16は、期間更新要求が入力されると、鍵記憶部15に記憶されている、複数の期間毎に対応付けられたLR署名鍵(sk)のうち、最も早い期間に対応付けられたLR署名鍵を削除し、削除されていないLR署名鍵(sk)を、生成アルゴリズム記憶部13に記憶されている鍵更新アルゴリズム(L−Kupd)により更新する。例えば、図5に示すように、ピリオド0からピリオド1への期間更新要求が入力されると、鍵記憶部15に記憶されているSK0、0に含まれる複数のskのうち、sk0、0を削除し、他のsk(sk1、0、sk2、0、・・・、skT−1、0)を鍵更新アルゴリズム(L−Kupd)により更新する。
【0027】
具体的には、期間更新部16は、以下手順によりピリオドを更新したFSLR署名鍵を生成する。ここでは、期間更新前のピリオドをtとし、期間更新後のピリオドをt+1とする。
1.SKt、i:=(skt、i、skt+1、i、・・・、skT−1、i)とおく。
2.skt、iを削除する。
3.s∈{t+1、・・・、T−1}に対して、sks、0←L−Kupd(sks、i)を計算する。
4.SKt+1、0:=(skt+1、0、・・・、skT−1、0)とおく。
5.ピリオドt+1、SKt+1、0を出力する。
【0028】
鍵更新部17は、鍵更新要求が入力されると、生成アルゴリズム記憶部13に記憶されている鍵更新アルゴリズム(L−Kupd)を読み出し、鍵記憶部15に記憶されている複数のLR署名鍵を、読み出した鍵更新アルゴリズム(L−Kupd)により更新する。例えば、図6に示すように、鍵記憶部15に記憶されているSKt、iに含まれる複数のsk(skt、i、・・・、skT−1、i)を鍵更新アルゴリズム(L−Kupd)により更新する。
【0029】
具体的には、鍵更新部17は、以下手順により更新したFSLR署名鍵を生成する。
1.SKt、i:=(skt、i、skt+1、i、・・・、skT−1、i)とおく。
2.s∈{t、・・・、T−1}に対して、sks、i+1←L−Kupd(sks、i)を計算する。
3.SKt、i+1:=(skt、i+1、・・・、skT−1、i+1)を出力する。
このように、期間更新はピリオドの更新を伴い、鍵の更新も行うアルゴリズムであり、鍵更新はピリオドの更新を伴わずに、鍵の更新を行うアルゴリズムである。
【0030】
署名生成部18は、入力されるメッセージと、鍵記憶部15に記憶されている、複数の期間毎に対応付けられたLR署名鍵のうち、最も早い期間に対応付けられたLR署名鍵とに基づいて生成されたLR署名を、メッセージに対するFSLR署名として出力する。具体的には、生成アルゴリズム記憶部13に記憶されている署名生成アルゴリズム(L−Sig)を読み出し、図7に示すように、現在のピリオドtに対応するskt、iを用いて、署名アルゴリズム(L−SIG)によりメッセージMのLR署名を生成する。
【0031】
具体的には、署名生成部18は、以下手順によりFSLR署名Σを出力する。
1.σ←L−SIG(skt、i、M)
2.(t、Σ:=σ)を出力する。
【0032】
検証装置20は、電子署名装置10により生成されたFSLR署名を検証するコンピュータ装置である。検証装置20は、入力部21と、出力部22と、検証アルゴリズム記憶部23と、検証部24とを備えている。
【0033】
入力部21は、情報の入力を受け付ける。電子署名装置10と同様に、例えば検証装置20がPCであれば、キーボードやマウス、ICカードリーダ等の入力デバイスであり、検証装置20がICカードであれば、外部のICカードリーダと通信する通信部である。入力部11には、検証の対象となるピリオドt、FSLR検証鍵VK、メッセージM、FSLR署名Σ等の情報が入力される。
出力部22は、検証装置20による検証結果を出力する。例えば、出力部12は、検証結果を送信する通信部や、検証結果を表示するディスプレイである。
【0034】
検証アルゴリズム記憶部23には、上述したようなLR方式に基づくLR署名を検証する検証アルゴリズム(L−Vfy)が記憶されている。検証アルゴリズム(L−Vfy)は、検証鍵vk、メッセージM、署名σを入力とし、1(valid)または0(invalid)の処理結果bを出力する(b←L−Vfy(vk、M、σ))。
【0035】
次に、本実施形態による電子署名システム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署名(Σ)を生成して出力する。
【0036】
図9は、検証装置20によるFSLR検証処理の動作例を示すフローチャートである。検証装置20の入力部21は、メッセージ(M)とFSLR署名(Σ)との入力を受け付ける(ステップS11)。検証部24が、検証アルゴリズム記憶部23に記憶されている検証アルゴリズムを読み出し、読み出した検証アルゴリズムによりメッセージ(M)に対するFSLR署名(Σ)の検証を行う(ステップS12)。検証部24が、FSLR署名(Σ)が生成されたピリオドに対応するLR検証鍵によるLR署名(σ)について検証成功したと判定すれば(ステップS11:YES)、検証成功の検証結果を出力する(ステップS13)。検証部24が、検証失敗したと判定すれば(ステップS12:NO)、検証失敗の検証結果を出力する(ステップS14)。
【0037】
以上説明したように、本実施形態によれば、LR方式のアルゴリズムを用いて、ピリオド毎に一方向性のある鍵の更新を行うようにした。これにより、FS方式およびLR方式両方の性質を持つ署名方式が提供できる。
【0038】
<第2の実施形態>
次に、本発明の第2の実施形態について説明する。本実施形態における電子署名システム1の構成は、第1の実施形態において図1に示した電子署名システム1の構成と同様である。以下、第1の実施形態と異なる処理等について説明する。本実施形態では、BellareらによるFS方式で用いられた二分木を利用したピリオドごとの鍵の更新を用い、署名鍵を構成する要素を、すべてBoyleらによるLR方式の鍵生成アルゴリズムにより生成する。
【0039】
本実施形態における電子署名装置10の鍵生成部14は、生成アルゴリズム記憶部13に記憶されている鍵生成アルゴリズム(L−KG)と署名生成アルゴリズム(L−Sig)とを読み出し、読み出したアルゴリズムを用いて、FSLR署名鍵とFSLR検証鍵とを生成する。まず、鍵生成部14は、複数のピリオド毎に、そのピリオドを識別する期間情報を対応付けた同レベルの複数の葉ノードを有する二分木を生成し、鍵記憶部15に記憶させる。図10は、鍵生成部14が生成する二分木の例を示す図である。ここでは、8つのピリオドを示す葉ノードのそれぞれに、「000」〜「111」の期間情報をノード番号として対応付ける。ノード番号は二進法によるビット列であるとする。根ノードのノード番号はεとする。根ノードεの左の子ノードを「0」とし、右の子ノードを「1」としている。さらに、ノード「0」を親ノードとする左の子ノードを「00」とし、右の子ノードを「01」としている。このように、親ノードの左の子ノードには、親ノードのノード番号の末尾に0を付したノード番号を対応付け、親ノードの右の子ノードには、親ノードのノード番号の末尾に1を付したノード番号を対応付けている。
【0040】
この二分木において、以下の表記法を利用する。 各ノードのノード番号をωとしたとき、そのビット列表現はω=ωω・・・ωとする。根ノードはεで表現し、そのビット列表現は空文字とする。深さはdで表す。ノードω=ωω・・・ωに対して、子ノードをω0=ωω・・・ω0、ω1=ωω・・・ω1と表す。ノードω=ωω・・・ω0、およびω=ωω・・・ω1に対して、親ノードをω=ωω・・・ωと表す。ノードt=t・・・tに対し、j∈{1、・・・、d−1}について、t|j=t・・・tと表し、t|0=εと表す。さらに、t|j0=t・・・t0、t|j1=t・・・t1、と表す。二分木において、j=1、・・・、d+1に対し、葉ノードtと根ノードとのパス上の深さjにおける兄弟ノード (sibling)を以下式(1)のように定義する。
【0041】
【数1】

【0042】
ノードω∈{0、1}≦j、j∈{1、・・・、d}に対して、DF(ω)を以下式(2)のように定義する。
【0043】
【数2】

【0044】
このような表記法に沿った、深さd=4の二分木、およびsiblingとDFの例を図11に示す。
また、鍵生成部14は、図12に示すように、二分木の各ノードに、生成アルゴリズム記憶部13から読み出した鍵生成アルゴリズムにより生成したLR署名鍵(sk)とLR検証鍵(vk)とを割り当てる。さらに、図13に示すように、根ノードに割り当てられたLR署名鍵(skε)と、親ノードに対する双方の子ノードに割り当てられたLR検証鍵を結合した情報(vk||vk)とに基づいて、生成アルゴリズム記憶部13から読み出した署名生成アルゴリズムによりLR署名(σε)を生成し、鍵記憶部15に記憶させる。鍵生成部14は、図14に示すように、二分木における葉ノード以外のノード毎に、このようなLR署名の生成処理を行う。
【0045】
さらに、鍵生成部14は、図15に示すように、葉ノードに割り当てられたLR署名鍵(例えば、sk000)と、その葉ノードに対応付けられた期間情報(例えば、ノード番号「000」)とに基づいて、生成アルゴリズム記憶部13から読み出した署名生成アルゴリズムによりLR署名(例えば、σ000)を生成する。そして、図16に破線に囲まれて示すような、生成した複数のLR署名(σε、σ、σ00、σ000、σ001)と、葉ノードに割り当てられたLR署名鍵(sk000、sk001)及びLR検証鍵(vk000、vk001)と、親ノードに対して左の子ノードに割り当てられたLR検証鍵(vk、vk00)と、その親ノードに対して右の子ノードに割り当てられたLR署名鍵(sk、sk01)及びLR検証鍵(vk、vk01)とを要素として、FSLR署名鍵(SK0、0)を生成する。例えば、これらの情報を配列に格納することにより、FSLR署名鍵(SK0、0)を生成する。また、鍵生成部14は、二分木における根ノード(ε)に割り当てたLR検証鍵(vkε)を、FSLR署名鍵(SK0、0)に対応するFSLR検証鍵(VK)として出力する。
【0046】
このように、FSLR鍵を生成する鍵生成アルゴリズム(Kg)は、セキュリティパラメタkと、ピリオドの総数Tを入力とし、初期ピリオドt、FSLR署名鍵SK0、0、FSLR検証鍵VKを出力する((t、sk0、0、vk)←Kg(1、T))。t:=0とする。これにより、ピリオドtのFSLR署名鍵は、二分木の葉ノードω=t から根ノードεまでのパス上に存在するノード、 およびその兄弟ノードに対応させた、L−Kg(1)により生成した鍵で構成される。ピリオドtにおいて、深さjにおけるノード番号ω=t|jの内部ノードに対応させる、署名鍵の更新をi回実施した鍵ペアを、(sk(t|d)、i、vk(t|j))=(skt、i、vk)と表記する。
【0047】
具体的には、鍵生成部14は、以下手順によりFSLR署名鍵(SK0、0)とFSLR検証鍵VKとを生成する。
1、Tを多項式オーダーの数とし、t:=0log(T)とする。
2、(skε、vkε)←L−Kg(1)を計算する。
3、j∈{0、・・・、d−1}に対して、以下を実行する。
a、(sk(t|j0)、0、vk(t|j0))←L−Kg(1
b、(sk(t|j1)、0、vk(t|j1))←L−Kg(1
c、σ(t|j)←L−Sig(sk(t|j)、0、vk(t|j0)||vk(t|j1))
d、sk(t|j)、0を削除する。
4、σ(t)←L−Sig(sk(t)、0、t)を計算する。
5、以下式(3)によりピリオドt、FSLR署名鍵(SK0、0)、FSLR検証鍵(VK)を出力する。
【0048】
【数3】

【0049】
鍵記憶部15には、鍵生成部14によって生成された二分木が記憶される。
期間更新部16は、期間更新要求が入力されると、鍵記憶部15に記憶された二分木において最も左の葉ノードを削除し、その葉ノード以外の各ノードに割り当てられたLR署名鍵とLR検証鍵と、そのLR署名鍵に基づいて生成されたLR署名とに基づいて、ピリオド更新したFSLR署名鍵を生成する。図17に示した図において、破線に囲まれた情報が、ピリオド更新後のピリオド2(ノード番号「001」)におけるFSLR署名鍵である。また、図18に示した図において、破線に囲まれた情報が、ピリオド更新後のピリオド3(ノード番号「010」)におけるFSLR署名鍵である。
すなわち、期間更新部16は、カレントピリオドt、カレントピリオドのFSLR署名鍵SKt、iを入力とし、更新後のピリオドt+1、更新後のFSLR署名鍵SKt+1、iを出力する。
【0050】
具体的には、期間更新部16は、以下手順によりピリオドを更新したFSLR署名鍵を生成する。
1、DF(t)の深さをj´とする。
2、j∈{0、・・・、j´−1}に対して、
a、ω:=sibling(j、t+1)とする。
b、ω=⊥のとき、sk(t+1|j1)、0:=⊥とする。
c、ω≠のとき、sk(ω)、i+1←L−Upd(sk(ω)、i)を計算し、sk(t+1j|1)、0:=sk(ω)、i+1とする。
3、j∈{j´、・・・、d−1}に対して、以下を実行する。
a、(sk(t+1|j0)、0、vk(t+1|j0))←L−Kg(1)
b、(sk(t+1|j1)、0、vk(t+1|j1))←L−Kg(1)
c、σ(t+1|j)←L−Sig(sk(t+1|j1)、0、vk(t+1|j0)||vk(t+1|j1))
d、sk(t+1|j)、0を削除する。
4、σ(t+1)←L−Sig(sk(t+1)、0、t+1)を計算する。
5、以下式(4)によりピリオドおよびFSLR署名鍵(t+1、SKt+1、0)を出力する。
【0051】
【数4】

【0052】
鍵更新部17は、期間更新要求が入力されると、二分木における各ノードに割り当てられたLR署名鍵を鍵更新アルゴリズムにより更新し、更新したLR署名鍵が含まれる各ノードに割り当てられたLR署名鍵とLR検証鍵と、そのLR署名鍵に基づいて生成されたLR署名とに基づいて、更新したFSLR署名鍵を生成する。また、鍵更新部17は、鍵更新要求が入力されると、同様に、二分木における各ノードに割り当てられたLR署名鍵を、鍵更新アルゴリズムにより更新し、更新したLR署名鍵に基づいてFSLR署名鍵を生成する。図19は、ピリオド3(ノード番号「010」)において行う鍵更新の例を示す図である。
【0053】
すなわち、鍵更新部17は、カレントピリオドのFSLR署名鍵SKt、iを入力とし、更新後のFSLR署名鍵SKt、i+1を出力する。具体的には、鍵更新部17は、以下手順により更新したFSLR署名鍵を生成する。
1、j∈{0、・・・、d−1}に対して、
a、ω:=sibling(j、t)とする。
b、ω=⊥のとき、sk(t|j1)、i+1:=⊥とする。
c、ω≠のとき、sk(t|j1)、i+1←L−Upd(sk(ω)、i)を計算する。
2、以下式(5)によりFSLR署名鍵SKt、i+1を出力する。
【0054】
【数5】

【0055】
署名生成部18は、入力されるメッセージと葉ノードに割り当てたLR署名鍵とに基づいて、署名生成アルゴリズムにより生成したLR署名と、ノード毎のLR署名鍵に基づいて生成されたLR署名と、LR検証鍵とを、メッセージに対するFSLR署名(Σ)として出力する。図20は、ピリオド3(ノード番号「010」)において行う署名生成の例を示す図である。
すなわち、署名生成部18は、カレントピリオドt、カレントピリオドの署名鍵SKt、i、メッセージMを入力とし、カレントピリオドt、FSLR署名Σを出力する。具体的には、署名生成部18は、以下手順によりFSLR署名Σを出力する。
1、ピリオドおよび署名鍵(t、SKt、i) を以下式(6)のように表記する。
【0056】
【数6】

【0057】
2、σ←L−Sig(sk(t)、i、M)を計算する。
3、以下式(7)により、更新後のピリオドおよびFSLR署名(t、Σ)を出力する。
【0058】
【数7】

【0059】
本実施形態における検証装置20の検証部24は、FSLR署名に含まれる全てのLR署名について検証が成功した場合に、検証成功と判定する。署名が生成されたピリオドt、FSLR検証鍵VK、メッセージM、FSLR署名Σを入力とし、1(valid)または0(invalid)を出力する。具体的には、検証部24は、以下手順により検証結果を出力する。
1、ピリオドおよび署名(t、Σ)を以下式(8)のように表記する。
【0060】
【数8】

【0061】
2、j∈{0、・・・、d−1}に対して、L−Vfy(vk(t|j)、vk(t|j0)||vk(t|j1)、σ(t|j))を出力する。
3、L−Vfy(vk(t)、M、σ)を出力する。
4、L−Vfy(vk(t)、t、σ(t))を出力する。
5、2〜4の全てにおいて1を出力していれば処理結果b=1とし、そうでなければb=0とする。
6、処理結果bを出力する。
【0062】
次に、本実施形態による電子署名システム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)。
【0063】
図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)。
【0064】
なお、本実施形態においては、初期の鍵生成段階にて二分木の各ノードに対応する要素を生成しておくようにしても良いが、鍵の要素のうち、全ての要素ではなく、そのピリオドにおいて必要となる要素のみを生成し、鍵記憶部15に記憶させておくこともできる。ここでは、必要でなくなった要素を削除することもできる。例えば上述の例において、ピリオド「000」の時点では、図16において破線に囲まれて示した要素のみを記憶させておくことができる。すなわち、第1の実施形態においては、初期時点において、期間Tに含まれる全ての期間に対応する複数のLR署名鍵sk0、0〜skT−1、0を予め生成しておく必要があるが、第2の実施形態によれば、そのピリオドにおける要素のみを、鍵更新の度に更新して鍵記憶部15に記憶させることができる。これにより、鍵記憶部15に記憶させておく情報の量を、第1の実施形態に比べて低減させることができる。これにより、電子署名装置10におけるメモリ消費量や、鍵漏えいのリスクを低減させることが可能となる。
【0065】
なお、本発明における処理部の機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより電子署名処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、OSや周辺機器等のハードウェアを含むものとする。また、「コンピュータシステム」は、ホームページ提供環境(あるいは表示環境)を備えたWWWシステムも含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ROM、CD−ROM等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ(RAM)のように、一定時間プログラムを保持しているものも含むものとする。
【0066】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク(通信網)や電話回線等の通信回線(通信線)のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル(差分プログラム)であっても良い。
【符号の説明】
【0067】
1 電子署名システム
10 電子署名装置
11 入力部
12 出力部
13 生成アルゴリズム記憶部
14 鍵生成部
15 鍵記憶部
16 期間更新部
17 鍵更新部
18 署名生成部
20 検証装置
21 入力部
22 出力部
23 検証アルゴリズム記憶部
24 検証部

【特許請求の範囲】
【請求項1】
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署名を検証する検証部と、
を有する検証装置と、
を備えることを特徴とする電子署名システム。
【請求項2】
鍵更新要求が入力されると、前記鍵記憶部に記憶されている複数の前記LR署名鍵を、前記鍵更新アルゴリズムにより更新する鍵更新部と、
を備えることを特徴とする請求項1に記載の電子署名システム。
【請求項3】
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署名について検証が成功した場合に、検証成功と判定する検証部と、
を有する検証装置と、
を備えることを特徴とする電子署名システム。
【請求項4】
前記電子署名装置の前記鍵更新部は、鍵更新要求が入力されると、前記二分木における各ノードに割り当てられた前記LR署名鍵を、前記鍵更新アルゴリズムにより更新し、更新した当該LR署名鍵に基づいて前記FSLR署名鍵を生成する
ことを特徴とする請求項3に記載の電子署名システム。
【請求項5】
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署名を検証するステップと、
を備えることを特徴とする電子署名方法。
【請求項6】
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署名について検証が成功した場合に、検証成功と判定するステップと、
を備えることを特徴とする電子署名方法。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate

【図22】
image rotate


【公開番号】特開2013−38605(P2013−38605A)
【公開日】平成25年2月21日(2013.2.21)
【国際特許分類】
【出願番号】特願2011−173271(P2011−173271)
【出願日】平成23年8月8日(2011.8.8)
【新規性喪失の例外の表示】特許法第30条第1項適用申請有り 平成23年2月24日 社団法人電子情報通信学会発行の「電子情報通信学会技術研究報告 信学技報 Vol.110 No.442」に発表
【出願人】(000102728)株式会社エヌ・ティ・ティ・データ (438)
【Fターム(参考)】