(57)【要約】【課題】証明可能安全性のあるフォワード・セキュア署名方式の基礎となり、さらに、セキュアで効率的な細粒度フォワード・セキュア署名方式の基礎にもなり、ハッカーの侵入に対し直ちに反応することを可能にし、それにより署名を再発行することなく過去の署名が依然有効なままで、したがって漏出した鍵に基づく将来の署名値を識別することができるような方法を提供すること。【解決手段】一般に、準備された各署名は、昇順インデックスを有し、あるインデックスが使用されたあとは、それより小さいインデックスは署名のために使用できない。したがって、敵が侵入したときはいつでも、たとえば、現在の期間に対する失効メッセージの一部分として現在のインデックスについてある特別のメッセージに署名することにより、真正の署名者が現在のインデックスを正しく告知することができる。したがって、先行の期間に作成されたすべての署名、ならびに、告知されたインデックスまでの取り消された期間に作成されたすべての署名は、有効でありつまり知れ渡らないことが理解される。
2005535206.tif 000002
【特許請求の範囲】
【請求項１】
署名方式を使用して、接続されたコンピュータ・ノードのネットワークにおいて適用可能な秘密暗号鍵（ｓｋ）、および公開暗号鍵（ｐｋ）を提供する方法であって、第１のコンピュータ・ノードで実行可能であり、
２つのランダム因数値（Ｐ，Ｑ）を選択すること、
前記２つの選択されたランダム因数値（Ｐ，Ｑ）を乗算して、係数値（Ｎ）を得ること、および
前記係数値（Ｎ）に基づいて秘密基底値（ｇ'，ｈ'，ｘ'）を選択すること
により、前記秘密暗号鍵（ｓｋ）を生成するステップであって、前記秘密基底値（ｇ'，ｈ'，ｘ'）が、前記秘密暗号鍵（ｇ'，ｈ'，ｘ'）の一部をなすステップと、
（Ｉ）個の指数値（ｅ１，…，ｅＩ）を選択すること、および
前記指数値（ｅ１，…，ｅＩ）および前記秘密基底値（ｇ'，ｈ'，ｘ'）から公開基底値（ｇ，ｈ，ｘ）を導くこと
により、前記公開暗号鍵（ｐｋ）を生成するステップであって、公開鍵（ｇ，ｈ，ｘ）および前記係数値（Ｎ）が、前記公開暗号鍵（ｇ，ｈ，ｘ，Ｎ）の一部をなすステップと、
前記２つのランダム因数値（Ｐ，Ｑ）を削除するステップと、
前記ネットワーク内に前記公開暗号鍵（ｇ，ｈ，ｘ，Ｎ）を提供するステップと
を含み、前記公開暗号鍵（ｇ，ｈ，ｘ，Ｎ）および前記選択された指数値（ｅ１，…，ｅＩ）の少なくとも１つが、検証のために前記ネットワーク内で第２のコンピュータ・ノードに送るべきメッセージ（ｍ）上の署名値（i，ｙ，ａ）を検証するために使用可能である方法。
【請求項２】
ネットワーク内で前記指数値（ｅ１，…，ｅＩ）の記述を提供するステップをさらに含む、請求項１に記載の方法。
【請求項３】
侵入が検出された場合に、前記署名値（i，ｙ，ａ）の妥当性を伝えることを可能にするために、前記選択された指数値（ｅ１，…，ｅＩ）の位数を確定するステップをさらに含む、請求項１または２に記載の方法。
【請求項４】
接続されたコンピュータ・ノードのネットワークにおいてメッセージ（ｍ）上で署名値（i，ｙ，ａ）を提供する方法であって、第１のコンピュータ・ノードで実行可能であり、
第１の署名要素（ａ）を選択するステップと、
（Ｉ）個の指数値（ｅ１，…，ｅＩ）から署名指数値（ｅi）を選択するステップと、
提供された秘密暗号鍵（ｇ'i，ｈ'i，ｘ'i）、前記メッセージｍ、および前記（Ｉ）個の指数値（ｅ１，…，ｅＩ）から第２の署名要素（ｙ）を導き、それにより、前記第１の署名要素（ａ）、前記第２の署名要素（ｙ）、および前記署名指数値（ｅi）が、前記メッセージ（ｍ）および提供された公開暗号鍵（ｇ，ｈ，ｘ，Ｎ）との既知の関係を満たすようにするステップとを含み、前記署名値（i，ｙ，ａ）は、前記第１の署名要素（ａ）、前記第２の署名要素（ｙ）、および、前記指数値（ｅi）への署名参照（i）を含み、
前記署名値（i，ｙ，ａ）が、検証のために前記ネットワーク内で第２のコンピュータ・ノードに送信可能である方法。
【請求項５】
第２の署名要素（ｙ）を導く前記ステップが、提供された公開暗号鍵（ｇ，ｈ，ｘ，Ｎ）、前記提供された秘密暗号鍵（ｇ'i，ｈ'i，ｘ'i）、および前記指数値（ｅ１，…，ｅＩ）を使用して、署名基底値（ｇi，ｈi，ｘi）を導くステップをさらに含む、請求項４に記載の方法。
【請求項６】
前記提供された秘密暗号鍵（ｇ'i，ｈ'i，ｘ'i）、および前記選択された署名指数値（ｅi）から新しい秘密暗号鍵ｇ'i＋１，ｈ'i＋１，ｘ'i＋１を導くステップをさらに含む、請求項４または５に記載の方法。
【請求項７】
接続されたコンピュータ・ノードのネットワークにおいてメッセージ（ｍ）上の署名値（i，ｙ，ａ）を検証する方法であって、第２のコンピュータ・ノードで実行可能であり、
前記署名値（i，ｙ，ａ）を第１のコンピュータ・ノードから受け取るステップと、
前記署名値（i，ｙ，ａ）から署名指数値（ｅi）を導くステップと、
前記署名指数値（ｅi）、および前記署名値（i，ｙ，ａ）の部分が、前記メッセージ（ｍ）および提供された公開暗号鍵（ｇ，ｈ，ｘ，Ｎ）との既知の関係を満たすかどうか検証し、満たさない場合は、前記署名値（i，ｙ，ａ）を拒否するステップとを含み、
前記署名値（i，ｙ，ａ）が、第１の署名要素（ａ）、（Ｉ）個の指数値（ｅ１，…，ｅＩ）、提供された秘密暗号鍵（ｇ'i，ｈ'i，ｘ'i）、および前記メッセージ（ｍ）から生成される方法。
【請求項８】
署名値（i，ｙ，ａ）に関係する秘密暗号鍵（ｓｋ）が漏出した場合に、接続されたコンピュータ・ノードのネットワーク内で前記署名値（i，ｙ，ａ）の妥当性を伝える方法であって、
指数値（ｅ１，…，ｅＩ）の位数を確定するステップと、
前記ネットワーク内で、前記指数値（ｅ１，…，ｅＩ）の記述、および前記指数値（ｅ１，…，ｅＩ）の前記位数を発行するステップと、
前記ネットワーク内で、前記指数値（ｅ１，…，ｅＩ）のうちの１つへの失効参照（ｊ）を発行し、それにより前記署名値（i，ｙ，ａ）の前記妥当性が、前記失効参照（ｊ）、指数値（ｅ１，…，ｅＩ）の前記位数、および提供された公開暗号鍵（ｐｋ）を使用することによって決定可能になる方法。
【請求項９】
前記各指数値（ｅ１，…，ｅＩ）を多くとも１つの署名値（i，ｙ，ａ）に適用することをさらに含む、請求項１ないし８のいずれかに記載の方法。
【請求項１０】
請求項１ないし９のいずれか一項に記載の方法の各ステップをコンピュータに実行させるプログラム。
【請求項１１】
請求項１０記載の前記プログラムをコンピュータ可読記録媒体に記録した、記録媒体。
【請求項１２】
請求項１１に記載のコンピュータ可読記録媒体と、
前記方法を実行するためのプロセッサとを含み、
前記プロセッサが、前記ネットワーク内で交換されるメッセージへのアクセスを有する、ネットワーク・デバイス（ｐi）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、接続されたコンピュータ・ノードのネットワークにおいて適用可能な、署名方式を使用して秘密暗号鍵および公開暗号鍵を提供する方法に関する。さらに本発明は、接続されたコンピュータ・ノードのネットワークにおいて、メッセージ上で署名値を提供しそれを検証する方法に関する。また、侵入が検出された場合に、生成された署名値の妥当性を知らせる方法も本明細書に開示する。
【背景技術】
【０００２】
電子署名またはデジタル署名は、情報を認証するために使用される。すなわち、電子ドキュメントの内容を、署名者、より正確には署名者の公開鍵と安全に結びつけるために使用される。真正の署名者のみが、有効な署名を作成することができるべきであり、誰もが、署名者が実際にそのドキュメントに署名したことを確信できるように、署名を検証することができるべきである。多数のデジタル署名方式がこれまで提案されてきたが、現在実際に使用されているものは少数である。
【０００３】
通常のデジタル署名方式は、基本的な欠点を持っている。たとえばハッカーが署名者のコンピュータに侵入するなどしたために秘密鍵が漏えいし、この漏えいが発覚し、公開鍵が無効にされると、署名者によって作成されたすべての署名が知れ渡るようになっており、すなわち、署名が署名者により作成されたのかそれともハッカーによって作成されたのかを見分けることがもはや不可能になっている。したがって、通常の署名方式自体は、否認防止（non-repudiation）を提供することができない。否認防止を達成するための可能な１つの方法は、いわゆるタイム・スタンピング・サービスを使用するものである。この場合、信頼される第３者に各署名が送られ、信頼される第３者が、署名ならびに現在のデータおよび時間を含むメッセージに署名する。署名者がその公開鍵を無効にする前にタイムスタンプが押されていた場合、署名は知れ渡っていないと見なされる。したがって、信頼される第３者の鍵は漏えいしないと想定すると、否認防止が保証される。ただし、この解決法は、信頼される第３者、たとえばタイム・スタンピング・サービスとの頻繁な対話を必要とするが、これは望ましいことではない。
【０００４】
他の可能な方法は、鍵を頻繁に変更する、すなわち日毎に異なる鍵ペアを使用し過去の日付のすべての秘密鍵を削除するものである。そうすると、ユーザがある日の鍵を無効にすることなくその日が過ぎた場合に、その鍵に関して作成されたすべての署名は、知れ渡っていないことがわかる。それには、やはり信頼される第３者との頻繁な対話が必要となるか、または公開鍵が多数となり、すなわち多数の公開鍵からなるリストが必要となる。フォワード・セキュア署名方式は、第４回ＡＣＭコンピュータおよび通信セキュリティ会議（ＡＣＭ  ＣＣＳ）（１９９７年）でその著者によって発表された原稿「公開鍵暗号化についての２つの所見（Two remarks on public-key cryptography）」２０００年９月においてＲ．アンダーソン（R.Anderson）によって導入され、「フォワード・セキュア・デジタル署名方式  A forward-secure digital signaturescheme」、マイケル・ウィナー（Michael Wiener）編、暗号学の進展（Advances in Cryptology）−クリプト９９（ＣＲＹＰＴＯ'９９）、ＬＣＮＳの１６６６巻、４３１〜４４８頁、シュプリンガー出版、１９９９年において、ベラーレ（Bellare）およびマイナー（Miner）によって定式化された。フォワード・セキュア署名方式は、各期間ごとに、ただ１つの公開鍵および多数の秘密鍵を設けることにより、この問題を解決する。実際、ほとんどのフォワード・セキュア署名方式は、現在の期間の秘密鍵を、先行の期間の鍵から一方向的に導き出すことを可能にするものである。
【０００５】
原理上は、フォワード・セキュア署名方式は、どんな通常の署名方式からも得ることができ、すなわち、署名者が各期間に対する新しい秘密鍵および公開鍵を選択する。フォワード・セキュア署名方式の公開鍵は、それが有効な期間のうちは、１組の通常の公開鍵インデックスになる。メッセージに署名するために、署名者はその期間の秘密鍵を使用する。ある期間を過ぎると、署名者は、その個別の秘密鍵を削除する。この方式がフォワード・セキュアであることは簡単にわかる。ただし、この方式は、（公開および秘密の）格納の点から見るとむしろ非効率である。
【０００６】
しかし、現行のフォワード・セキュア署名方式には以下の問題がある。ハッカーが侵入した場合、この期間に作成されたすべての署名を取り消さなければならず、（真正の）署名者は、署名を再発行する必要がある。これに対する１つの解決法は、鍵の更新の複雑さが署名の複雑さに匹敵する場合のみに有効となる短い期間を用いることである。
【非特許文献１】Ｒ．アンダーソン（R. Anderson）、「公開鍵暗号化についての２つの所見（Tworemarks on public-key cryptography）」２０００年９月、第４回ＡＣＭコンピュータおよび通信セキュリティ会議（ＡＣＭ  ＣＣＳ）原稿（１９９７年）
【非特許文献２】ベラーレ（Bellare）、マイナー（Miner）、「フォワード・セキュア・デジタル署名方式  Aforward-secure digital signature scheme」、暗号学の進展（Advances in Cryptology）−クリプト９９（ＣＲＹＰＴＯ'９９）、マイケル・ウィナー（MichaelWiener）編ＬＣＮＳの１６６６巻、４３１〜４４８頁、シュプリンガー出版、１９９９年
【発明の開示】
【発明が解決しようとする課題】
【０００７】
上記のことから、より安全で効率的な改良されたフォワード・セキュア署名方式が求められている。この方式は、ハッカーの侵入に対し、過去の署名を再発行せずに直ちに対処することを可能にするものである。
【課題を解決するための手段】
【０００８】
本発明の第１の態様によれば、署名方式を使用して、接続されたコンピュータ・ノードのネットワークにおいて適用可能な秘密暗号鍵ｓｋおよび公開暗号鍵ｐｋを提供する方法が提供される。この方法は第１のコンピュータ・ノードによって実行可能であり、２つのランダム因数値Ｐ，Ｑを選択し、選択された２つのランダム因数値Ｐ，Ｑを乗算して係数値（Ｎ）を求め、係数値Ｎに基づいて秘密基底値（secret base value）ｇ'，ｈ'，ｘ'を選択することによって、秘密暗号鍵ｓｋを生成するステップを含み、秘密基底値ｇ'，ｈ'，ｘ'は、秘密暗号鍵ｇ'，ｈ'，ｘ'の一部をなす。この方法はさらに、Ｉ個の指数値ｅ１，…，ｅＩを選択し、指数値ｅ１，…，ｅＩおよび秘密基底値ｇ'，ｈ'，ｘ'から公開基底値ｇ，ｈ，ｘを導くことによって、公開暗号鍵ｐｋを生成するステップを含み、公開基底値ｇ，ｈ，ｘ、および係数値Ｎは、公開暗号鍵ｇ，ｈ，ｘ，Ｎの一部をなす。この方法はさらに、２つのランダム因数値Ｐ，Ｑを削除するステップと、ネットワーク内で公開暗号鍵ｇ，ｈ，ｘ，Ｎを提供するステップを含み、公開暗号鍵ｇ，ｈ，ｘ，Ｎ、および選択された指数値ｅ１，…，ｅＩの少なくとも１つが、ネットワーク内で検査のために第２のコンピュータ・ノードに送られるべきメッセージ上の署名値i，ｙ，ａを検査するために使用可能である。
【０００９】
本発明の第２の態様では、接続されたコンピュータ・ノードのネットワーク内でメッセージｍ上の署名値i，ｙ，ａを提供する方法が提供される。この方法は第１のコンピュータ・ノードで実行可能であり、第１の署名要素ａを選択するステップと、Ｉ個の指数値ｅ１，…，ｅＩから指数値ｅiを選択するステップと、提供された秘密暗号鍵ｇ'i，ｈ'i，ｘ'i、メッセージｍ、およびＩ個の指数値ｅ１，…，ｅＩから、第２の署名要素ｙを導き出すステップとを含み、これによって、第１の署名要素ａ、第２の署名要素ｙ、および署名指数値ｅiが、メッセージｍおよび提供された公開暗号鍵ｇ，ｈ，ｘ，Ｎとの既知の関係を満たすようにされ、これらの署名値i，ｙ，ａは、第１の署名要素ａ、第２の署名要素ｙ、および署名指数値ｅiへの署名参照iを含み、署名値i，ｙ，ａは、検証のためにネットワーク内で第２のコンピュータ・ノードに送信可能である。
【００１０】
本発明の第３の態様では、接続されたコンピュータ・ノードのネットワーク内でメッセージｍ上の署名値i，ｙ，ａを検証する方法が提供される。この方法は第２のコンピュータ・ノードで実行可能であり、第１のコンピュータ・ノードから署名値i，ｙ，ａを受け取るステップと、署名値i，ｙ，ａから署名指数値ｅiを導くステップと、署名指数値ｅiおよび署名値i，ｙ，ａの部分が、メッセージｍおよび提供された公開暗号鍵ｇ，ｈ，ｘ，Ｎとの既知の関係を満たすかどうかを検証し、満たさない場合は、署名値i，ｙ，ａを拒否するステップとを含み、これらの署名値i，ｙ，ａは、第１の署名要素ａ、Ｉ個の指数値ｅ１，…，ｅＩ、提供された秘密暗号鍵ｇ'i，ｈ'i，ｘ'iおよびメッセージｍから生成される。
【００１１】
本発明の第４の態様では、署名値i，ｙ，ａに関係する秘密暗号鍵ｓｋが漏出した場合に、接続されたコンピュータ・ノードのネットワークにおいて署名値i，ｙ，ａの妥当性を知らせる方法が提供される。この方法は、指数値ｅ１，…，ｅＩの位数を確定するステップと、ネットワーク内で指数値ｅ１，…，ｅＩの記述および指数値ｅ１，…，ｅＩの位数を発行するステップと、ネットワーク内で指数値ｅ１，…，ｅＩのうちの１つに対する失効参照ｊを発行するステップとを含み、署名値i，ｙ，ａの妥当性が、失効参照ｊ、指数値ｅ１，…，ｅＩの位数、提供された公開暗号鍵ｐｋを使用することによって判定可能になる。
【００１２】
これら提示の方法は、証明可能安全性がある、すなわちその安全性がランダム・オラクル・モデルなどヒューリスティクでないものに依拠している、フォワード・セキュア署名方式の基礎となる。さらに、提示の方法はまた、セキュアで効率的な細粒度フォワード・セキュア署名の基礎となる。後者の方式では、ハッカーの侵入に対し直ちに対処することが可能になり、したがって過去の署名値がそれを再発行することなく引き続き有効であり、したがって漏出した鍵に基づく将来の署名値が識別できるようになる。言い換えれば、細粒度フォワード・セキュア署名方式を使用するときには、秘密暗号鍵が漏出した場合に、現在の期間に生成された署名値を再署名する必要がない。再署名は、再び各当事者に連絡し、場合によってはいくらかの再折衝を行う必要があるので、冗長である。
【００１３】
一般に、この提示の方法は、フォワード・セキュア署名方式の基礎となり、署名とも呼ばれる準備された各署名値は、昇順インデックスiとも見なされる昇順署名参照（ascending signature reference）iを持つ。このインデックスiは、それがいったん使用された後は、署名を行うのにそれより低いインデックスを再び使用することができないように、署名値i，ｙ，ａに付加される。こうすると、敵が侵入したときはいつでも、真正の署名者は、たとえば、現在の期間の失効メッセージの一部分として、現在のインデックスに関してある特別のメッセージを署名することによって、現在のインデックスを正しく告知することができる。したがって、先行の期間に作成されたすべての署名、ならびに告知されたインデックスまでの取り消された期間に作成されたすべての署名は、有効であり、つまり知れ渡らないことが理解されよう。
【００１４】
細粒度フォワード・セキュア署名方式では、通常のフォワード・セキュア署名方式におけるように期間を使用するのではなく、新しいメッセージが署名されるといつでも秘密暗号鍵を更新する。署名者のシステムに侵入があり、侵入検出システムと呼ばれるツールの存在により直ちに通知することができる場合、公開暗号鍵ｇ，ｈ，ｘ，Ｎを無効にし、最近使用したインデックスiを発行することができる。したがって、他のコンピュータ・ノードが、既に発行された署名の妥当性について通知を受けることができる。これにより、他の当事者が、過去の署名の再発行を必要とせずに既に漏出した提供された秘密暗号鍵ｇ'i，ｈ'i，ｘ'iを使用して署名をするのを防止することができる。
【００１５】
指数値ｅ１，…，ｅＩの記述をネットワーク内で提供することができる。これにより、すべての関係当事者が署名の妥当性を検証することが可能になる。
【００１６】
侵入が検出された場合に、署名値i，ｙ，ａの妥当性を伝えることを可能にするために、選択された指数値ｅ１，…，ｅＩの位数を確定することができる。これにより、提示の方式の細粒度特性が可能になる。
【００１７】
各指数値ｅ１，…，ｅＩは、多くとも１つの署名値i，ｙ，ａに適用することができ、その署名値によりセキュア署名方式を提供することが可能になる。
【００１８】
署名要素ｙを導出するステップがさらに、提供された公開暗号鍵ｇ，ｈ，ｘ，Ｎ、提供された秘密暗号鍵ｇ'i，ｈ'i，ｘ'i、および指数値ｅ１，…，ｅＩを使用することにより、署名基底値ｇi，ｈi，ｘiを導き出すステップを含む場合、より効率的な署名の生成を達成することができる。
【００１９】
提供された秘密暗号鍵ｇ'i，ｈ'i，ｘ'i、および選択された署名指数値ｅiから新しい秘密暗号ｇ'i＋１，ｈ'i＋１，ｘ'i＋１が導かれる場合、フォワードセキュリティが達成できるという利点がもたらされる。
【００２０】
本発明の好ましい実施形態を、単に例として以下の概略図を参照し下記で詳しく説明する。
【００２１】
図面は、単に説明のために示したものにすぎず、必ずしも本発明の実際の例を原寸に比例して表したものではない。
【００２２】
用語集
下記は、説明を理解する助けとなる非公式の定義である。記号は、傍らに示す用語に関するもので、ここでの記述の範囲内で用いられる。
Ｐ，Ｑ  ランダム因数値、好ましくは素数
Ｎ  係数値
ｋ  Ｎのビット数
ｅ１，…，ｅＩ  指数値
ｅi  署名指数値
Ｗ  シード、指数値の記述の部分
ＱＲＮ  Ｚ＊ｎにおける平方の部分群
ｌ  セキュリティ・パラメータ
｛０，１｝ｌ  長さｌのビット・ストリング
ｇ'，ｈ'，ｘ'秘密暗号鍵（ｓｋ）の部分である秘密基底値
ｇ'i，ｈ'i，ｘ'i  提供された秘密暗号鍵
ｇ'i＋１，ｈ'i＋１，ｘ'i＋１  新しいまたは更新された秘密暗号鍵
ｇ，ｈ，ｘ  公開基底値を形成する
ｇ，ｈ，ｘ，Ｎ  公開暗号鍵（ｐｋ）または提供された公開暗号鍵（ｐｋ）
ａ  第１の署名要素
ｙ  第２の署名要素
i  署名指数値ｅiへの署名参照
ｊ  失効参照
ｊ'  署名参照
Ｉ  生成可能な署名値の数
i，ｙ，ａ  署名値を形成する
ｍ  メッセージ
ｐ１，ｐ２，ｐ３，ｐ４  第１、第２、第３、第４のコンピュータ・ノード
ｔ０  開始時間
Ｔ  期間
ｔ△  持続時間
ｓ  期間あたり生成可能な署名値の数
【発明を実施するための最良の形態】
【００２３】
全般的に図面を参照して、ネットワークにおける細粒度フォワード・セキュア署名方式の特徴を下記でさらに詳細に説明する。
【００２４】
通常のコンピュータ・システム２の例を示す図１を参照する。このシステムは、通信回線５を介してネットワークに接続された第１、第２、第３、第４のコンピュータ・ノードｐ１，ｐ２，ｐ３，ｐ４を含んでいる。各コンピュータ・ノードｐ１，ｐ２，ｐ３，ｐ４は、チップ上のコンピュータやウェアラブル・コンピュータから大規模なコンピュータ・システムまで当技術分野で知られるどんなタイプのコンピュータ装置またはネットワーク装置でもよい。その通信回線は、データまたはメッセージをあるコンピュータ・ノードから他のコンピュータ・ノードに送信するための通常知られるどんな手段でもよい。たとえば、通信回線は、コンピュータ・ノードのｐ１，ｐ２，ｐ３，ｐ４の各対の間の単一の双方向通信回線５でも、コンピュータ・ノードのｐ１，ｐ２，ｐ３，ｐ４の各対の間の各方向に１本ある単一方向回線でもよい。通常のコンピュータ・システム２は、フォワード・セキュア署名方式、および細粒度フォワード・セキュア署名方式を形成し可能にする以下の説明を容易にするために示したものである。
【００２５】
鍵の生成
図２は、接続されたコンピュータ・ノードのネットワークにおいて適用できる秘密暗号鍵および公開暗号鍵を提供するための概略流れ図である。実施されるステップが、それぞれボックス内に示され番号が付けられている。同じ参照番号または記号は、同じまたは同様の部分を示すのに使用される。
【００２６】
ここでは、秘密鍵とも呼ばれる秘密暗号鍵ｓｋ、および公開鍵とも呼ばれる公開暗号鍵の生成は、第１のコンピュータ・ノードｐ１で行われる。
【００２７】
まず、秘密暗号鍵ｓｋを生成するのに、２０、２１で示される２つのランダム因数値Ｐ，Ｑを選択する。次いで、この２つの選択されたランダム因数値Ｐ，Ｑを乗算し、これにより２２に示す係数値Ｎを得る。次いでボックス２３に示すように、係数値Ｎに基づいて秘密基底値ｇ'，ｈ'，ｘ'を選択する。秘密基底値ｇ'，ｈ'，ｘ'は、やはりｇ'，ｈ'，ｘ'として示される秘密暗号鍵ｓｋの一部になっている。
【００２８】
次に、公開暗号鍵ｐｋを生成するために、ボックス２４に示すＩ個の指数値ｅ１，…，ｅＩを選択する。指数値ｅ１，…，ｅＩおよび秘密基底値ｇ'，ｈ'，ｘ'から、２５に示す公開基底値ｇ，ｈ，ｘが導かれる。公開基底値ｇ，ｈ，ｘおよび係数値Ｎは、２６に示すｇ，ｈ，ｘ，Ｎとも示される公開暗号鍵ｐｋの一部を形成する。２７に示すように、２つのランダム因数値Ｐ，Ｑは、セキュリティ上の理由により後で削除すべきである。２８に示す公開暗号鍵ｇ，ｈ，ｘ，Ｎは、ネットワーク内に提供され、したがってコンピュータ・ノードｐ２，ｐ３，ｐ４は、この鍵にアクセスできる。後で、公開暗号鍵ｇ，ｈ，ｘ，Ｎと、選択された指数値ｅ１，…，ｅＩの少なくとも１つを使用して、ネットワーク内でたとえば第２のコンピュータ・ノードｐ２に検証の目的で送信されるメッセージｍ上の署名とも呼ばれる署名値i，ｙ，ａを、検証することができる。
【００２９】
秘密暗号鍵ｓｋおよび公開暗号鍵ｐｋの生成を、下記では、いくらかより数学的な詳細を伴う実施形態として提示する。まず、ｋビットサイズのランダムＲＳＡ係数値Ｎを選択する。係数値Ｎは、２つの安全な素数（safe prime）の積であることが好ましい。ＱＲＮは、Ｚ＊ｎ内の平方の部分群を表し、したがってすべての群演算はこの群において行われることになる。Ｉ個のランダムで一意のｌ＋１ビット素数指数値ｅ１，…，ｅＩを作成するために、ランダム・シードＷが選択され、ある擬似乱数ジェネレータに適用することによって使用される。（公開暗号鍵ｐｋの一部分である）このシードＷの発行により、任意のコンピュータ・ノードｐ２，ｐ３，ｐ４が、指数値ｅ１，…，ｅＩを生成することが可能になる。すべての指数値ｅ１，…，ｅＩを公開暗号鍵ｐｋの一部分として発行することも可能である。さらに、異なる署名者が同じ指数を使用することができるので、それらを、ある信頼される機関から発行することもできる。さらに、秘密基底値ｇ'，ｈ'，ｘ'は、ＱＲＮからランダムに選択される。それは、次のように計算される。
【００３０】
【数１】
2005535206.tif 000003
【００３１】
ただし、公開暗号鍵ｐｋは、ｐｋ：＝Ｎ、ｇ，ｈ，ｘ、Ｗである。秘密暗号鍵ｓｋは、ｓｋ：＝ｇ'，ｈ'，ｘ'である。i：＝０にセットされる。
【００３２】
署名
図３は、接続されたコンピュータ・ノードのネットワーク内でメッセージｍ上で署名値を提供する概略流れ図を示す。公開暗号鍵ｐｋがまだ無効にされていない場合、メッセージｍ上の署名値i，ｙ，ａは、第１のコンピュータ・ノードｐ１で実行される。第１のコンピュータ・ノードｐ１は、署名者または署名側とも呼ばれる。まず、３０に示すように、第１の署名要素ａが選択される。さらに、ボックス３１に示すように、署名指数値ｅiが、Ｉ個の指数値ｅ１，…，ｅＩから選択される。ボックス３２に示す第２の署名要素ｙは、３３に示す提供された秘密暗号鍵ｇ'i，ｈ'i，ｘ'iと、３４に示すメッセージｍと、Ｉ個の指数値ｅ１，…，ｅＩから導かれ、したがって、第１の署名要素ａ、第２の署名要素ｙ、および署名指数値ｅiは、既知の関係を満たすようになる。その関係は、メッセージｍと、ｇ，ｈ，ｘ，Ｎを含む提供された公開暗号鍵ｐｋとを有する検証方程式として表すことができる。３５に示す署名値i，ｙ，ａは、最終的に、第１の署名値ａ、第２の署名値ｙ、および、署名指数値ｅiへの署名参照iを含む。次いで、署名値i，ｙ，ａは、ネットワーク内でたとえばコンピュータ・ノードｐ２に検証のために送られる。
【００３３】
署名値i，ｙ，ａの生成について、以下でいくらかより数学的な側面に関して説明する。メッセージｍが署名されるものと仮定する。たとえば秘密暗号鍵ｓｋが漏えいしたため、公開暗号鍵ｐｋが取り消された場合、またはi＞Ｉすなわち生成可能な署名値の最大数に達した場合、署名することが打ち切られる。秘密暗号鍵ｓｋi＝ｇ'i，ｈ'i，ｘ'iが与えられた場合、要素ｇi，ｈi，ｘiを計算することができ、次式のようになる。
【００３４】
【数２】
2005535206.tif 000004
【００３５】
次いで、ランダムでａ∈Ｒ｛０，１｝ｌである第１の署名要素ａを選択し、次式を計算する。
【００３６】
【数３】
2005535206.tif 000005
【００３７】
メッセージｍ上の署名は、この場合i，ｙ，ａである。
【００３８】
署名をした後、次式の計算を行い、
【００３９】
【数４】
2005535206.tif 000006
【００４０】
次いで秘密暗号鍵ｓｋをｓｋi＋１：＝（ｇ'i＋１，ｈ'i＋１，ｘ'i＋１）にセットすることにより、秘密暗号鍵ｓｋを更新し、また、i：＝i＋１に更新する。
【００４１】
署名の検証
図４は、署名値i，ｙ，ａを検証するための概略流れ図を示す。ここでは、メッセージ上の署名値i，ｙ，ａの検証が、第２のコンピュータ・ノードｐ２で行われる。ボックス４０に示す署名値i，ｙ，ａを、第２のコンピュータ・ノードｐ２が第１のコンピュータ・ノードｐ１から受信する。次いで、第２のコンピュータ・ノードｐ２は、ボックス４１に示す署名指数値ｅiを署名値i，ｙ，ａから導く。ボックス４２に示すように、署名指数値ｅiが、Ｉ個の指数値ｅ１，…，ｅＩの要素であるか否かを検証することができる。ボックス４３に示す指数値ｅ１，…，ｅＩの記述は、ネットワーク内でアクセス可能である。署名指数値ｅiがＩ個の指数値ｅ１，…，ｅＩの要素でない場合、署名値i，ｙ，ａを拒否することができる。ボックス４４に示すように、署名指数値ｅi、および署名値の部分i，ｙ，ａが、既知の関係、すなわち、メッセージｍ、およびボックス４３に示す提供された公開暗号鍵ｇ，ｈ，ｘ，Ｎを有する検証方程式を満たすか否かを検証する。この検証が失敗した場合、署名値i，ｙ，ａは拒否される。検証４２および４４の結果は、「Ｔ」および「Ｆ」の形で示される「真」または「偽」であり、「偽」すなわち「Ｆ」は、署名値i，ｙ，ａの拒否となり「真」すなわち「Ｔ」は、その受諾となる。署名値i，ｙ，ａは、第１の署名要素ａ、Ｉ個の指数値ｅ１，…，ｅＩ、提供された秘密暗号鍵ｇ'i，ｈ'i，ｘ'i、およびメッセージｍから生成されたと判定することができる。
【００４２】
他の例では、検証者（verifier）とも呼ばれる第２のコンピュータ・ノードｐ２が、i，ｙ，ａ，Ｗが、署名すなわちメッセージｍ上の署名値であるか否かを検査する。まず、０≦i≦Ｉであるかどうかが検査される。次に、第２のコンピュータ・ノードｐ２が、やはり署名値i，ｙ，ａ，Ｗに含まれる署名参照iおよびシードＷから、署名指数値ｅiを生成する。最後に、検証者すなわち第２のコンピュータ・ノードｐ２は、下記の既知の関係すなわち検証方程式が満たされる場合に、署名を受諾する。
【００４３】
【数５】
2005535206.tif 000007
【００４４】
失効
図５は、署名値i，ｙ，ａと関係する５４に示す秘密暗号鍵ｓｋが漏出した場合に、接続されたコンピュータ・ノードのネットワーク内で、署名値i，ｙ，ａの妥当性を伝えるための概略流れ図を示す。署名値i，ｙ，ａの妥当性は、ネットワーク内で以下のように伝えられる。５０に示すように指数値ｅ１，…，ｅＩの位数が確定され、５１に示すように、その記述がネットワーク内に提供される。５１に示すように、指数値ｅ１，…，ｅＩの位数も、ネットワーク内で発行される。さらに、５２に示すように、指数値ｅ１，…，ｅＩのうちの１つへの失効参照ｊもネットワーク内で発行され、したがって、失効参照ｊ、指数値ｅ１，…，ｅＩの位数、および５５に示す提供された公開暗号鍵ｐｋを使用することによって、５３に示すように署名値i，ｙ，ａの妥当性が判定可能になる。
【００４５】
ランダムオラクルなしで証明可能安全性のあるフォワード・セキュア署名方式および細粒度フォワード・セキュア署名方式として、提示の署名方式をどのように使用するかを示すいくらかより簡潔な実施形態を以下に示す。
【００４６】
フォワード・セキュア署名方式
提示の署名方式は、期間あたり１つのメッセージしか署名できないという特定の性質を有するフォワード・セキュア署名方式として使用することができる。つまり、各インデックスiを、メッセージにではなく期間に割り当てる。
【００４７】
もちろん、期間あたり単一のメッセージしか署名できないのでは、あまり実用的ではない。しかし、通常の任意の署名方式Ｓを提示の署名方式と一緒に使用して、次に述べるように、期間あたり多数のメッセージに署名することができるフォワード・セキュア署名方式を得ることができる。
【００４８】
各期間Ｔi（ただし１≦i≦Ｉ）ごとに、新しいインスタンスすなわち公開鍵と秘密鍵の対Ｓ（Ｓiと呼ぶ）を生成し、その公開鍵ｐｋiをi番目のメッセージとして提示の署名方式で署名する。
【００４９】
期間Ｔiにおいてメッセージｍに署名するために、次いで署名方式Ｓiを使用してメッセージｍに署名することができ、その結果、署名Ｓｍが得られる。したがって、メッセージｍ上の最終の署名は、署名Ｓｍ、公開鍵ｐｋi、および提示の署名方式にインデックスiを適用して実施されるその公開鍵に基づく署名を含む。
【００５０】
細粒度フォワード・セキュア署名方式
上記に提示の署名方式は、侵入が発生したことを主張し、署名者がその署名に使用したものより小さいインデックスを発行することにより、不正な署名者が過去に作成された署名を無効化するのを防ぐことができない。署名者が、署名の生成後に、侵入の発生を主張することによってその間に署名を依然として取り消すことができる若干の時間（たとえば１時間）を与えられることは避けられないように思われる。これは、署名者に、侵入が起きたのを理解しそれに反応するためにいくらかの時間を与えるべきだからである。下記では、この問題を解決するための３つの例Ｉ、ＩＩ、ＩＩを提示する。
【００５１】
Ｉ．２レベル方式
提示の署名方式のＡ方式と称する１つの例を使用する。この場合、各インデックスは期間を示し、つまりここではインデックスiはｔ０＋i＊ｔ△からｔ０＋（i＋１）ｔ△までの期間Ｔiを示す（ただしｔ０は開始時間であり、ｔ△は持続時間である）。この方式の公開鍵は、ユーザの公開鍵となる。さらに、公開鍵の部分として１つのパラメータｊ△が発行され、このパラメータｊ△は、ユーザが秘密暗号鍵の漏えいに気付くのにかかり得る時間を制御する。
【００５２】
次に、各期間ごとに、提示の署名方式のＢi方式と称する第２の例が使用され、その期間のインデックスiについてＡ方式を使用してその公開鍵に署名する。この後、Ａ方式の秘密鍵が更新され、この方式の現在の新しいインデックスは、i＋１となる。
【００５３】
現在の期間Ｔiのｊ番のメッセージに署名するために、インデックスｊを有するＢi方式が使用される。メッセージ上の署名は、この署名、Ｂi方式の公開鍵、および、Ａ方式で作成された公開鍵に基づく署名を含む。さらに、Ｂi方式の秘密鍵への署名が更新された後、新しい現インデックスは、ｊ：＝ｊ＋１である。
【００５４】
署名者は、自身の鍵を無効にしたいときはいつでも、たとえば期間Ｔi'に、この旨を示すここではｊ'である現在のインデックスを使用しＢi方式で署名された所定のメッセージを、信頼される第３者（以下ではＴＴＰと略記する）に送る。このような署名は、失効署名（revocation signature）と呼ばれる。ＴＴＰは、署名を検証し、現在の期間がＴi'であるかどうかを検査する。そうである場合、ＴＴＰは失効を承認し、署名を適切に発行する。署名者は、同じ期間中に何回か失効を行うことを妨げられることはない。
【００５５】
失効が発生しなかった場合、または、i≦i'かつｊ≦ｊ'−ｊ△であり、インデックスi'およびｊ'を有する失効が発生した場合（ただし、i'およびｊ'は、ＴＴＰにより発行された失効署名のインデックスのうちで最小のインデックスである）、インデックスiおよびｊを有するユーザの署名は、有効と見なされる。ある署名が署名された期間が過ぎるまでは、その署名が有効であるか否かは確かではない。ただし、どのフォワード・セキュア署名方式でもこのことは同様である。
【００５６】
署名者が、１つの鍵を何回も失効させることができるのは、そうでなければ、その秘密鍵を知っている敵が、署名者の現在のインデックスよりも大きいインデックスｊ'を有する失効メッセージを送ることができるからである。このことから細粒度フォワード・セキュア署名方式が生まれたことが容易にわかる。提示の署名方式の代わりに、Ａ方式としてどんなフォワード・セキュア署名方式を利用することもできる。
【００５７】
ＩＩ．公開アーカイブの使用
第２の例では、前記の例におけるＡ方式を、公開アーカイブで置き換える。このアーカイブからメッセージを削除することはできず、メッセージがアーカイブによって受け取られるちょうどその時間と一緒にメッセージが発行されると仮定される。
【００５８】
このようなアーカイブが与えられた場合、細粒度フォワード・セキュア署名方式は、提示の署名方式の１つの例だけを使用して以下のように達成される。メッセージｍ上の署名は、現在のインデックスを使用して提示の署名方式で行われる。署名の後、秘密鍵が更新される。
【００５９】
各期間の終わりに、提示の署名方式を適用し、現在のインデックス、ここではｊを使用することによって、ユーザは、所定のメッセージ、たとえば≪期間Ｔiに使用された最終インデックス≫に署名し、次いで秘密鍵を更新し、このインデックス署名を公開アーカイブに送る。公開アーカイブは、その署名を受け取った時間と一緒にメッセージを送る。
【００６０】
署名者が自身の鍵を無効にしたいときはいつでも、たとえば期間Ｔi'に、署名者は、この旨を指示する好ましくは所定のメッセージを、現在のインデックスｊ'を使用して提示の署名方式で署名して、ＴＴＰに送る。ＴＴＰは、署名を検証し、Ｔ'iが現在の期間であるかどうか、また、署名者が先行期間に公開アーカイブに提供したインデックス署名のインデックスｊよりもｊ'が小さくないかどうかを検査する。小さくない場合、ＴＴＰが失効を承認し、適切に署名を発行する。さらに、署名者は、同じ期間中に何度も失効を行うことを妨げられない。
【００６１】
この第２の例では、失効にされなかった場合、あるいは、失効が行われi＜ｊ'−ｊ△もしくはi＜ｊである場合（ただし、ｊ'はＴＴＰによって発行された失効署名のうち最小のインデックスであり、ｊは、鍵が失効にされた期間に先行する期間に署名者が公開アーカイブに提供したインデックス署名のインデックスｊである）は、インデックスiを有するユーザの署名は有効と見なされる。
【００６２】
この例の方式では、ある期間に署名された署名が有効であることは、その期間が過ぎ、署名者がアーカイブ内のより高いインデックスを有する署名を発行するまで、確かではない。第１の例の解決策と比べて、第２の解決策は、署名がより短いという利点を持つ。
【００６３】
実用上の理由で、アーカイブ内にインデックス署名を発行し失効を行うために、署名者に、期間が過ぎた後いくらかの時間を与えることができる。こうすると、期間の最後に侵入に対処できるようになる。その結果、署名者は、期間ごとに公開アーカイブ内にいくつかのインデックス署名を置くことができるようになり、最小のインデックスを有する署名が、カウントされる署名である。失効が行われなかった場合、または、失効が行われたかi＜ｊ'−ｊ△（ただしｊ'は失効署名のインデックス）である場合、インデックスiを有する署名は、有効とカウントされる。
【００６４】
ＩＩＩ．期間あたりｓ個の署名を可能にする
第３の例では、提示の署名方式の例が１つだけ使用される。期間あたり厳密にｓ個の署名を可能にすることにより、インデックスが期間に束縛される。パラメータｓは、ｔ０およびｔ△と一緒に公開鍵の部分として発行される。
【００６５】
したがって、期間Ｔiに、インデックスi・ｓ，…，（i＋１）ｓ−１を、署名するのに使用することができる。鍵を失効させるために、署名者は、現在のインデックスｊ'で作成した失効署名をＴＴＰに送る。ＴＴＰは、署名を検証し署名のインデックスが現在の期間と合致した場合、それを発行する。
【００６６】
失効が発生しなかった場合、または、インデックスｊ'を有する失効署名が発行され、ｊが期間ｊ'より前の期間に属するか、もしくはｊ＜ｊ'−ｊ△である場合、インデックスｊを有する署名は、有効と見なされる。
【００６７】
第３の例の背景となる原理は、提示の署名方式でメッセージに署名する作業が、秘密鍵を更新することによって支配されることである。したがって、計算能力が与えられた場合にある期間にいくつの署名を発行することができるかを計算することができ、ｓをその数にセットする。その場合は、たとえメッセージに署名がされなくても、秘密鍵の更新を絶えず実行することになる。この手法では、システムの応答の挙動はあまり変更されないが、公開アーカイブを使用せず、第１の例におけるより署名は小さくなる。
【００６８】
先に開示したどの実施形態も、ここで示しまたは説明した他の１つまたは複数の実施形態と組み合わせることができる。これらの実施形態の１つまたは複数の特徴についてもそれが可能である。
【００６９】
この文脈におけるコンピュータ・プログラム手段、またはコンピュータ・プログラムは、特定の機能を、直接的に、あるいは、ａ）他の言語、コード、もしくは表記への変換、ｂ）異なる材料形態での複製のいずれか一方または両方を行った後で、情報処理能力を有するシステムに実施させることを目的とする任意の言語、コード、または表記における１組の命令の任意の表現を意味する。
【図面の簡単な説明】
【００７０】
【図１】接続されたコンピュータ・ノードの典型的なネットワークを示す図である。
【図２】接続されたコンピュータ・ノードのネットワークにおいて適用可能な秘密暗号鍵および公開暗号鍵を提供するための概略流れ図である。
【図３】接続されたコンピュータ・ノードのネットワーク内でメッセージ上の署名値を提供するための概略流れ図である。
【図４】署名値を検証するための概略流れ図である。
【図５】接続されたコンピュータ・ノードのネットワーク内で署名値に関係する秘密暗号鍵が漏出した場合に署名値の妥当性を伝えるための概略流れ図である。
【図１】
2005535206.tif 000008
【図２】
2005535206.tif 000009
【図３】
2005535206.tif 000010
【図４】
2005535206.tif 000011
【図５】
2005535206.tif 000012
【国際調査報告】
2005535206.tif 000013
2005535206.tif 000014
2005535206.tif 000015