JP2023522752A - 分散された鍵のバックアップストレージからの復元 - Google Patents

Abstract

分散された秘密鍵をバックアップストレージから復元する方法が開示されている。オリジナルの秘密鍵が生成され、二つ以上のサーバに分散される。第１のサーバは、少なくとも第１のサーバが保持するオリジナルの秘密鍵のシェアを含むバックアップを作成する。各サーバは、少なくとも一度、オリジナルの秘密鍵をリフレッシュする。各リフレッシュの間、サーバはリフレッシュされた分散された秘密鍵と、従前の秘密鍵とリフレッシュされた秘密鍵との間の分散された差分を生成し、各サーバは差分のシェアの秘密バージョンを生成して他のサーバの少なくとも一部とシェアし、各サーバは差分のシェアの受信された秘密バージョンと従前の累積された秘密バージョンに基づいて他のサーバから受信された差分のシェアの累積された秘密バージョンを生成する。第１のサーバは、バックアップからオリジナルの秘密鍵のシェアを復元し、他のサーバに差分のシェアの累積された秘密バージョンを要求し、受け取った累積された秘密バージョンとオリジナルの秘密鍵の復元されたシェアから、最新のリフレッシュされた秘密鍵のシェアを復元する。

Description

発明の属する技術分野
本発明は、バックアップストレージから分散された秘密鍵を復元する方法に関するものである。本発明による方法によれば、バックアップ作成後、分散された秘密鍵が数回リフレッシュされた場合でも、秘密鍵を安全に復元することができる。

発明の背景
閾値暗号化方式または閾値署名方式において、秘密鍵は、各サーバが秘密鍵の少なくとも一つのシェアを保持し、いずれのサーバもすべてのシェア、ひいては秘密鍵全体へのアクセスを有しないように、二つ以上のサーバの間で分散されることがある。鍵を用いて暗号化、復号化、または署名を行う場合、トランザクションを有効にするためには、少なくとも予め定義された数のサーバのサブセットが参加する必要がある。したがって、敵対者は、閾値基準を満たす不正な署名、暗号化、復号化を行うために、十分な数の鍵のシェアにアクセスするために、複数のサーバを危険にさらす必要がある。

各サーバは、適切な時間間隔で秘密鍵のシェアのバックアップを作成することが望まれる。バックアップは独立したものであり、各サーバは必ずしも同時にバックアップを作成する必要はない。もし、あるサーバに障害が発生し、秘密鍵のシェアを含むコンテンツをバックアップから復元する必要がある場合、このサーバは復元されるが、他のサーバは影響を受けない。

長期間の秘密鍵、例えば長期間にわたって秘密シェアされる秘密鍵の場合、敵対者は徐々に十分な数の鍵のシェアにアクセスできるようになり、秘密鍵を不正に使用できるようになる可能性がある。これを回避するために、秘密鍵、ひいては鍵のシェアは時々リフレッシュされることがある。したがって、敵対者は十分な数の鍵のシェアにアクセスすることだけが必要なのではない。また、敵対者は秘密鍵が二回リフレッシュされる間に、同じ時間内に鍵のシェアにアクセスする必要がある。これは「積極的な秘密のシェアリング(proactive secret sharing)」と呼ばれることもある。

しかし、バックアップを作成した時点から、バックアップから鍵のシェアを復元する必要がある時点まで、秘密鍵が一回以上リフレッシュされている場合、バックアップから得られる鍵のシェアは現在適用できる鍵のシェアと異なるため、有効でなくなる。

本発明の実施形態の目的は、秘密鍵の機密性を損なうことなくリフレッシュされた秘密鍵を復元することができる、バックアップストレージから分散された秘密鍵を復元するための方法を提供することである。

本発明の実施形態のさらなる目的は、バックアップストレージから分散された秘密鍵を復元するための方法であって、プロアクティブな秘密性を維持しながら、リフレッシュされた秘密鍵を復元することができる方法を提供することである。

本発明は、バックアップストレージから分散された秘密鍵を復元するための方法を提供し、この方法は、
オリジナルの秘密鍵を生成し、オリジナルの秘密鍵を二つ以上のサーバに分散するステップであって、各サーバが、それによりオリジナルの秘密鍵のシェアを保持し、どのサーバもオリジナルの秘密鍵の全てのシェアを保持しないようにするステップと、
第１のサーバが、バックアップを作成するステップであって、バックアップが少なくとも第１のサーバによって保持されるオリジナルの秘密鍵のシェアを含む、生成するステップと、
サーバが、少なくとも一回、オリジナルのリフレッシュするステップであって、各リフレッシュは、
各サーバが、リフレッシュされた分散された秘密鍵、及び従前の秘密鍵とリフレッシュされた秘密鍵との分散された差分を生成し、各サーバが分散された差分のシェアを保持し、分散された差分はゼロのシェアリングを構成し、サーバは従前の秘密鍵のシェアを破棄するステップと、
各サーバが、分散された差分のシェアの秘密バージョンを生成し、その秘密バージョンを他のサーバの少なくとも一部とシェアするステップと、
各サーバが、分散された差分のシェアの受信した秘密バージョンと従前の累積された秘密バージョンとに基づいて、他のサーバから受信した分散された差分のシェアの累積された秘密バージョンを生成するステップと
を含む、リフレッシュするステップと、
第１のサーバが、バックアップからオリジナルの秘密鍵のシェアを復元し、他のサーバに分散された差分のシェアの累積された秘密バージョンを要求するステップと、
他のサーバの少なくとも一部が、第１のサーバの分散された差分のうちの、第１のサーバのシェアの累積された秘密バージョンを提供するステップと、
第１のサーバが、受け取った累積された秘密バージョンとオリジナルの秘密鍵の復元されたシェアとから、最新のリフレッシュされた秘密鍵のシェアを復元するステップと
を含む。

したがって、本発明による方法は、バックアップストレージから分散された秘密鍵を復元する方法である。秘密鍵は、例えば、秘密の暗号化／復号化鍵または秘密署名鍵、すなわち、デジタル署名を生成するために適用される秘密鍵であればよい。

本発明は、次に、添付の図面を参照してさらに詳細に説明される。

図１は、先行技術の方法を説明する図であり 図２～図８は、本発明の７つの異なる実施形態による方法を説明する図である。 図２～図８は、本発明の７つの異なる実施形態による方法を説明する図である。 図２～図８は、本発明の７つの異なる実施形態による方法を説明する図である。 図２～図８は、本発明の７つの異なる実施形態による方法を説明する図である。 図２～図８は、本発明の７つの異なる実施形態による方法を説明する図である。 図２～図８は、本発明の７つの異なる実施形態による方法を説明する図である。 図２～図８は、本発明の７つの異なる実施形態による方法を説明する図である。

本発明の実施形態の目的は、秘密鍵の機密性を損なうことなくリフレッシュされた秘密鍵を復元することができる、バックアップストレージから分散された秘密鍵を復元するための方法を提供することである。

本発明の実施形態のさらなる目的は、バックアップストレージから分散された秘密鍵を復元するための方法であって、プロアクティブな秘密性を維持しながら、リフレッシュされた秘密鍵を復元することができる方法を提供することである。

本発明は、バックアップストレージから分散された秘密鍵を復元するための方法を提供し、この方法は、
オリジナルの秘密鍵を生成し、オリジナルの秘密鍵を二つ以上のサーバに分散するステップであって、各サーバが、それによりオリジナルの秘密鍵のシェアを保持し、どのサーバもオリジナルの秘密鍵の全てのシェアを保持しないようにするステップと、
第１のサーバが、バックアップを作成するステップであって、バックアップが少なくとも第１のサーバによって保持されるオリジナルの秘密鍵のシェアを含む、生成するステップと、
サーバが、少なくとも一回、オリジナルのリフレッシュするステップであって、各リフレッシュは、
各サーバが、リフレッシュされた分散された秘密鍵、及び従前の秘密鍵とリフレッシュされた秘密鍵との分散された差分を生成し、各サーバが分散された差分のシェアを保持し、分散された差分はゼロのシェアリングを構成し、サーバは従前の秘密鍵のシェアを破棄するステップと、
各サーバが、分散された差分のシェアの秘密バージョンを生成し、その秘密バージョンを他のサーバの少なくとも一部とシェアするステップと、
各サーバが、分散された差分のシェアの受信した秘密バージョンと従前の累積された秘密バージョンとに基づいて、他のサーバから受信した分散された差分のシェアの累積された秘密バージョンを生成するステップと
を含む、リフレッシュするステップと、
第１のサーバが、バックアップからオリジナルの秘密鍵のシェアを復元し、他のサーバに分散された差分のシェアの累積された秘密バージョンを要求するステップと、
他のサーバの少なくとも一部が、第１のサーバの分散された差分のうちの、第１のサーバのシェアの累積された秘密バージョンを提供するステップと、
第１のサーバが、受けた累積された秘密バージョンとオリジナルの秘密鍵の復元されたシェアとから、最新のリフレッシュされた秘密鍵のシェアを復元するステップと
を含む。

したがって、本発明による方法は、バックアップストレージから分散された秘密鍵を復元する方法である。秘密鍵は、例えば、秘密の暗号化／復号化鍵または秘密署名鍵、すなわち、デジタル署名を生成するために適用される秘密鍵であればよい。

この方法によれば、オリジナルの秘密鍵が生成され、二つ以上のサーバに分散されるが、各サーバはオリジナルの秘密鍵のシェアを保持し、どのサーバも秘密鍵のすべてのシェアを持たないようにされる。したがって、どのサーバもオリジナルの秘密鍵全体を再構成することができず、それによって、オリジナルの秘密鍵を使用するために、予め定義された数のサーバの少なくともサブセットが参加する必要がある。秘密鍵は、最初に生成され、その後、サーバの間で分散されてもよいし、サーバは、例えば秘密のシェアリングを用いて、分散された形式で直接秘密鍵を生成することに協力してもよい。

サーバは、互いに物理的に分離された別々のハードウェアサーバであってもよい。代替策として、サーバは仮想サーバの形態であってもよく、必ずしも別々のハードウェア上に配置されなくてもよい。ただし、いずれのサーバも他のサーバに保存されたコンテンツにアクセスできないという意味で、サーバは互いに分離されている。

オリジナルの秘密鍵の生成後、第１のサーバはバックアップを作成する。第１のサーバはオリジナルの秘密鍵の第１のシェアを保有しているので、作成されたバックアップにはこのオリジナルの秘密鍵のこの第１のシェアが含まれる。第１のサーバのバックアップは、他のサーバのバックアップとは独立して行われる。

バックアップが作成された後のある時点で、各サーバはオリジナルの秘密鍵を少なくとも１回リフレッシュする。各リフレッシュは、以下に示す方法で行われる。

最初に、サーバは、リフレッシュされた分散された秘密鍵と、前回の秘密鍵とリフレッシュされた秘密鍵との分散された差分を生成する。リフレッシュされた分散された秘密鍵および/または分散された差分は、オリジナルの秘密鍵が生成された方法と同様の方法で生成されてもよい。これについては、以下でさらに詳しく説明する。いずれにせよ、各サーバはリフレッシュされた秘密鍵のシェアと、分散された差分のシェアを保持することになる。さらに、どのサーバもリフレッシュされた秘密鍵の全てのシェアを保持せず、どのサーバも分散された差分の全てのシェアを持たない。したがって、どのサーバもリフレッシュされた秘密鍵全体も分散された差分全体も自分では再構成することができない。

本明細書では、「従前の秘密鍵」という用語は、リフレッシュが実行される時点で有効な分散された秘密鍵を意味すると解釈されるべきである。したがって、第１のリフレッシュが実行されるとき、従前の秘密鍵はオリジナルの秘密鍵である。第２のリフレッシュが行われたとき、従前の秘密鍵は、秘密鍵の第１のリフレッシュ時に生成されたリフレッシュされた秘密鍵、等である。

このとき、分散された差分はゼロのシェアリングとなる。これにより、リフレッシュされた秘密鍵は、分散された秘密鍵の間の差分がゼロになるという意味で、従前の秘密鍵、ひいてはオリジナルの秘密鍵と同一となる。しかし、鍵のリフレッシュ後にサーバにより保持される秘密鍵のシェアは、鍵のリフレッシュの前にサーバにより保持される秘密鍵のシェアと同一ではない。

リフレッシュ後の秘密鍵が生成され、各サーバに分散されると、各サーバは従前の秘密鍵の個々のシェアを破棄する。これにより、従前の秘密鍵は破棄され、リフレッシュされた分散された秘密鍵が、次のリフレッシュが行われるまで有効なバージョンとなる。さらに、従前の秘密鍵のシェアのいずれにもアクセスすることができなくなり、それに応じて、従前の秘密鍵全体を構築することができなくなる。

さらに、各サーバは、差分のシェアの秘密バージョンを生成し、その秘密バージョンを他のサーバの少なくともいくつかとシェアする。秘密バージョンは、例えば、差分のシェアの暗号化バージョンであり得る。代替的または追加的に、サーバは、他のサーバ間で差分のそのシェアのシェアを分散してもよく、その場合、秘密バージョンは、シェアの秘密のシェアリングの形態であってもよい。いずれにせよ、サーバは、差分のシェアの秘密バージョンを他のサーバに公開するだけであり、所定のサーバのみが秘密バージョンから差分のシェアを再構築することができる。したがって、どのサーバも、受けた秘密バージョンから、他のサーバが保持する実際の差分のシェアを知ることはできない。したがって、従前の分散された秘密鍵のシェアと差分のシェアの秘密バージョンにアクセスした敵対者は、リフレッシュされた分散された鍵の対応するシェアを再構築することができない。

最後に、各サーバは、他のサーバから受信した差分のシェアの累積された秘密バージョンと、従前の累積された秘密バージョンとに基づいて、他のサーバから受信した差分のシェアの累積された秘密バージョンを生成する。このように、差分のシェアの累積された秘密バージョンは、オリジナルの分散された秘密鍵のシェアとリフレッシュされた秘密鍵の現在有効なシェアとの間の夫々の差分を表す。累積された秘密バージョンは、様々な方法で生成されてもよい。これについては、以下でさらに詳細に説明する。

分散された秘密鍵が上記の方法で何回もリフレッシュされたとき、第１のサーバで、第１のサーバ、ひいては第１のサーバが保持している分散された秘密鍵のシェアを回復することを必要とする事象(incident)が発生する。しかし、バックアップストレージに格納されている分散された鍵のシェアは、オリジナルの分散された秘密鍵のシェアであり、バックアップ作成後、少なくとも１回は分散秘密鍵がリフレッシュされているので、オリジナルの秘密鍵はもはや有効ではなく、第１のサーバが保持している現在有効な秘密鍵のシェアは、バックアップから直ちに直接復元することはできない。

そこで、第１のサーバは、バックアップからオリジナルの秘密鍵のシェア、すなわち実際に利用可能なシェアを復元し、他のサーバに対して、その差分のシェアの累積された秘密バージョンを要求する。

この要求に応答して、他のサーバの少なくともいくつかは、第１のサーバの差分のシェアの蓄積された秘密バージョンを第１のサーバに提供する。いくつかの実施形態では、他のサーバのうちの一つだけが蓄積された秘密バージョンを提供してもよく、他の実施形態では、他のサーバのうちの二つ以上が蓄積された秘密バージョンを提供してもよい。したがって、第１のサーバは、現在、オリジナルの秘密鍵のそのシェアと、オリジナルの秘密鍵の第１のサーバのシェアと現在有効な秘密鍵の第１のサーバのシェアとの間の差の秘密表現とを所有する状態にある。しかし、蓄積された秘密バージョンだけが第１のサーバに提供されたので、どのサーバも、リフレッシュされた秘密鍵の中間バージョンの第１のサーバのシェアに関する知識を一切持っていない。

最後に、第１のサーバは、受け取った累積された秘密バージョンとオリジナルの秘密鍵の復元されたシェアから、最新のリフレッシュされた秘密鍵のシェア、すなわち、現在有効な秘密鍵を復元する。上述したように、累積された秘密バージョンは、オリジナルの秘密鍵の第１のサーバのシェアと、現在有効な秘密鍵の第１のサーバのシェア、すなわち最新のリフレッシュされた秘密鍵のシェアとの間の差分を表す。したがって、第１のサーバは、受信した累積された秘密バージョンからこの差分を導出することができ、それによって、第１のサーバは、オリジナルのシェアと導出された差分から最新のリフレッシュされた秘密鍵のシェアを容易に再構築することができる。

このように、本発明に係る方法は、閾値鍵システムの秘密鍵のシェアの独立したバックアップを可能にし、秘密鍵の漏洩リスクが低いという意味で高いセキュリティを維持しつつ、分散された秘密鍵を頻繁にリフレッシュし、バックアップから鍵のシェアを確実に復元できるようにするものである。

特に、鍵のシェアの復元は、鍵のシェアの最新のリフレッシュされたバージョンのみを復元し、潜在的な中間のリフレッシュされたバージョンは復元しないため、敵対者がそのような中間のリフレッシュされたバージョンにアクセスすることは不可能である。それによって、敵対者は、リフレッシュの期間が満了した後、同じリフレッシュに属する十分な数の鍵のシェアを収集することを妨げられる。

したがって、本発明に係る方法は、サーバが、サーバの鍵のシェアの古いバージョンと、サーバが他のサーバのうちの一つ以上から受け取る秘密の累積された差分とを含むバックアップから、その現在の秘密の鍵のシェアを復元することを可能にする。特に、この方法は、他のサーバに第１のサーバの秘密鍵のシェアを復元する能力を付与することなく、第１のサーバのシェアを復元することを可能にする。

各サーバが差分のシェアの秘密バージョンを生成するステップは、加法的同型性スキームによって実行されてもよく、各サーバが累積された秘密バージョンを生成するステップは、各サーバが差分のシェアの受け取った秘密バージョンをそれぞれの従前の累積された秘密バージョンに追加し、従前の累積された秘密バージョンを破棄することから構成されてもよい。

加法的同型性スキームとは、暗号化された領域で加算が可能なスキーム、すなわち、Ｅ（ｄ_１＋ｄ_２）＝Ｅ（ｄ_１）＋Ｅ（ｄ_２）であり、Ｅは暗号化を意味する。このように、差分のシェアの秘密バージョンを生成するために加法的同型性スキームが適用される場合、それぞれのサーバは、自分のシェアｄ_ｉを暗号化し、暗号化バージョンＥ（ｄ_ｉ）を他のサーバに転送することができる。そして、他のサーバは、暗号化されたバージョンを加算するだけで、差分のシェアの合計の暗号化されたバージョンを得ることができる。

したがって、本実施形態によれば、本方法は、以下のように実行されてもよい。簡単のために、方法は、第１のサーバの観点から説明される、すなわち、第１のサーバによって保持されるシェアのみが説明される。しかし、同様のステップを他のサーバが実行してもよいことに留意すべきである。

第１のリフレッシュが実行されると、第１のサーバは、オリジナルの秘密鍵と第１のリフレッシュされた秘密鍵との差分のシェア、ｄ_１を生成する。この差分のシェアｄ_１は、オリジナルの秘密鍵の第１のサーバのシェアと、第１のリフレッシュされた秘密鍵の第１のサーバのシェアとの間の差分に相当する。次に、第１のサーバは、そのシェアｄ_１を加法的同型性スキームを用いて暗号化し、それによって、シェアｄ_１の秘密バージョンＥ（ｄ_１）を得る。この秘密バージョンＥ（ｄ_１）は、他のサーバの少なくとも一つに転送される。このシェアｄ１の秘密バージョンによって、第１の蓄積された秘密バージョンＡ_１＝Ｅ（ｄ_１）が構成される。

第２のリフレッシュが実行されるとき、第１のサーバは、同様に、第１のリフレッシュされた秘密鍵と第２のリフレッシュされた秘密鍵との間の差分のそのシェア、ｄ_２を生成する。これにより、オリジナルの秘密鍵の第１のサーバのシェアと、第２のリフレッシュされた秘密鍵の第１のサーバのシェアとの差分は、ｄ_１＋ｄ_２となる。

次に、第１のサーバは、そのシェアｄ_２を加法的同型性スキームを用いて復号化し、それによってシェアｄ_２の秘密バージョンＥ（ｄ_２）を得る。秘密バージョンＥ（ｄ_２）は、次に、他のサーバの少なくとも一つに転送される。第２のシェアの秘密バージョンＥ（ｄ_２）の受信に応答して、他のサーバは、オリジナルの秘密鍵と第２のリフレッシュされた秘密鍵との差分の第１のサーバのシェア、ｄ１＋ｄ_２の第２の累積された秘密バージョンＡ_２を生成し、新たに受信した秘密バージョンＥ（ｄ_２）を以前に受信した秘密バージョンＥ（ｄ_１）に追加し、それによりＡ_２＝Ｅ（ｄ_１）＋Ｅ（ｄ_２）＝Ａ_１＋Ｅ（ｄ_２）を得る。Ｅは加法的同型性スキームを表すので、蓄積された秘密バージョンは、実際には、蓄積された差分の秘密バージョン、すなわち、Ａ_２＝Ｅ（ｄ_１）＋Ｅ（ｄ_２）＝Ｅ（ｄ_１＋ｄ_２）である。第２の蓄積された秘密バージョンＡ_２が生成されると、サーバは、第１の蓄積された秘密バージョンＡ_１を破棄する。

３回目のリフレッシュが行われると、上記の手順が繰り返され、３回目の蓄積された秘密バージョンＡ_３が生成され、Ａ_３＝Ａ_２＋Ｅ（ｄ_３）＝Ｅ（ｄ_１＋ｄ_２＋ｄ_３）となり、前の蓄積された秘密バージョンＡ_２が破棄される。

これをリフレッシュのたびに繰り返すことにより、各サーバは常に最新バージョンの蓄積された秘密バージョンＡ_ｎ＝Ｅ（ｄ_１＋ｄ_２＋．．．＋ｄ_ｎ）を保持し、それ以前のバージョンの蓄積された秘密バージョンは保持しないようにする。

第１のサーバのバックアップが必要な場合、第１のサーバはバックアップストレージからオリジナルの秘密鍵のシェアを取得し、他のサーバに差分の蓄積された秘密バージョンを要求する。そして、他のサーバの少なくとも一つは、現在有効なバージョンの蓄積された秘密バージョンＡ_ｎを、第１のサーバに提供する。そして、第１のサーバは、受け取った蓄積された秘密バージョンＡ_ｎを復号することにより、オリジナルの秘密鍵の第１のサーバのシェアと現在有効なリフレッシュされた秘密鍵の第１のサーバのシェアとの間の実際の差分ｄ_１＋ｄ_２＋．．．＋ｄ_ｎを取得することができる。したがって、第１のサーバは、オリジナルの秘密鍵の復元されたシェアに累積された差を加えることによって、現在有効なリフレッシュされた秘密鍵のシェアを復元することができる。したがって、現在有効なリフレッシュされた鍵のシェアは、中間のシェアのいずれかを明らかにすることなく復元される。

加法的同型性スキームの一例は、Ｐａｌｌｉｅｒの公開鍵暗号化スキームである。

加法的同型性スキームは、公開鍵暗号化スキームであってもよく、第１のサーバがバックアップを作成するステップは、バックアップの一部としてプライベート復号化鍵を格納することを含んでもよい。本実施形態によれば、秘密復号化鍵は、第１のサーバが他のサーバから受信した蓄積された秘密バージョンを復号する必要がある場合に必要であり、それ以外の場合に必要であるとは限らない。バックアップの一部として秘密復号化鍵を格納することにより、バックアップから第１のサーバを復元する必要がある場合にのみバックアップ格納にアクセスするため、敵対者が秘密暗号化鍵にアクセスすることが困難であることが保証される。一方、このような状況が発生した場合、第１のサーバは、秘密暗号化鍵を含むバックアップストレージの内容を取得し、それによって、秘密暗号化鍵は、現在有効な秘密鍵のシェアを復元する一環として、受信した蓄積された秘密バージョンを復号するために第１のサーバが利用できるようにする。バックアップを作成するとき、第１のサーバは、さらに、バックアップストレージに格納された後、第１のサーバから秘密復号化鍵を削除してもよい。同様に、バックアップを復元する際、第１のサーバは、受信した秘密累積バージョンの差分を復号するために一旦秘密復号化鍵を使用した後、第１のサーバから秘密復号化鍵を削除してもよい。これにより、第１のサーバを侵害した敵対者が秘密復号化鍵にアクセスできる期間を限定することができるので、安全性を高めることができる。

これまで説明したように、本発明は、秘密鍵ｓのシェアがｓ＝ｓ_１＋ｓ_２＋．．．＋ｓ_ｎを満たす加算的シェアリングの観点から説明されており、リフレッシュ処理で発生する差分は、各サーバが局所的に秘密のシェアにゼロのシェアリングで加算する加算的シェアリングの形態であった。代替の実施形態では、秘密のシェアリングは乗法的であってもよく、すなわち、秘密のシェアｓはｓ＝ｓ_１＊ｓ_２＊．．．＊ｓ_ｎを満たし、秘密のシェアリングをリフレッシュするステップは、１の乗法的ランダムシェアリングを生成し、これを既存の秘密のシェアリングに乗算して、リフレッシュされたシェアリングを生成することからなり、それぞれのサーバが、１のそのシェアと秘密のシェアとを局所的に乗算することによって、そのシェアリングが生成される。この場合、差分のシェアの秘密バージョンを生成することは、乗法的同型性スキームによって実行されてもよい。これは、ＥｌＧａｍａｌ暗号化スキームのような乗法的に同型性の公開鍵暗号化スキームであり得る。

以下では、引き続き加法的な表記を用いる。すなわち、秘密のシェアリングが、ゼロのシェアリングを加えてリフレッシュされ、合計ｄ_１＋ｄ_２＋．．．＋ｄ_ｎが生成されると言うことにする。しかし、この方法は、乗法的シェアリングの場合にも同様に機能し、１のシェアリングを乗算することによって秘密のシェアリングがリフレッシュされ、累積されたｄ_１＊ｄ_２＊．．．＊ｄ_ｎの秘密バージョンが生成される。

代替策として、秘密復号化鍵は、例えば、コールドストレージ、ハードウェアセキュアモデル（ＨＳＭ）のような外部ストレージに別々に格納されてもよく、及び／又は、第１のサーバで容易に利用できない暗号化鍵によって復号されるか、パスワードによって保護されてもよい。例えば、暗号化鍵やパスワードは、管理者によって管理されてもよい。この場合、バックアップからの復元時に、例えば、コールドストレージから秘密暗号化鍵を要求したり、管理者に秘密復号化鍵の復号を要求したり、蓄積された秘密バージョンの復号を実行したりすることにより、別途秘密暗号化鍵を取得する必要がある。

各サーバが差分のそのシェアの秘密バージョンを生成するステップは、各サーバが差分のそのシェアのシェアリングを作成し、他のサーバの少なくとも一部の間でシェアを分配することを含んでもよい。シェアリングは、例えば、秘密のシェアリングの形態であってもよい。本実施形態によれば、差分のシェアの秘密バージョンは、作成されたシェアリングの形態である。それにより、他のいずれのサーバも、差分のシェアの全体を把握することはできない。本実施形態によれば、サーバは、次の分散された差分の第１のサーバのシェアを受け取ると、これを分散された差分の第１のサーバのシェアの従前のシェアに加算して、分散された差分の第１のサーバのシェアの新しい累積されたシェアを獲得し、その古いシェアを破棄する。このような方法でシェアリングを作成することは、上述した公開鍵暗号化スキームの代替手段として適用することができる。また、代替策として、他のサーバに分散されたシェアがさらに暗号化されるという意味で、これら二つのアプローチを組み合わせてもよい。

各リフレッシュは、
サーバが、ゼロのシェアリングを作成し、各サーバが、ゼロのシェアリングのシェアを従前の秘密鍵のシェアに追加し、それによってサーバ間で分散されるリフレッシュされた秘密鍵を作成し、従前の秘密鍵のシェアを破棄するステップであって、ゼロのシェアリングは分散された差分を構成する、破棄するステップと、
各サーバが、ゼロのシェアリングのシェアの秘密バージョンを生成し、他のサーバの少なくとも一部と秘密バージョンをシェアリングするステップと
を、含んでもよい。

この実施形態によれば、リフレッシュされた秘密鍵は、サーバが、その中で、ゼロのシェアリング、例えばゼロの秘密のシェアリングを生成し、その後、このゼロのシェアリングを従前の秘密鍵に追加することによって、生成される。これは、各サーバがゼロのシェアリングのシェアを従前の秘密鍵のシェアに追加することによって行われる。さらに、この実施形態によれば、サーバによって保持される分散された差分のシェアは、それぞれのサーバによって保持されるゼロのシェアリングのシェアである。

代替策として、サーバは、従前の秘密鍵の新しいシェアリングを作成することによってリフレッシュされた秘密鍵を生成し、新しいリフレッシュされた秘密鍵および従前のリフレッシュされた秘密鍵のそれぞれのシェアから分散された差分を導出してもよい。

本方法は、バックアップをオフラインストレージに保存するステップをさらに含んでもよい。この実施形態によれば、バックアップはオンラインではアクセスできず、したがって、敵対者はバックアップにアクセスするためにオフラインストレージに物理的に侵入する必要があるであろう。オフラインストレージは、例えば、ＵＳＢストレージやディスクなどのポータブル記憶媒体の形態であり、安全な、若しくは別の、制限されたエリアにロックされている可能性がある。オフラインストレージの位置は、サーバの位置と異なる場合があり、その場合、バックアップの作成時、およびバックアップの復元が必要なときに、物理的にバックアップを位置間で転送する必要がある。このため、バックアップの作成が面倒になり、あまり頻繁にバックアップが作成されない場合がある。このため、二つのバックアップの間に秘密鍵のリフレッシュが多く行われることが予想されるため、本発明の方法は非常に有意義である。

秘密鍵をリフレッシュする各ステップは、各サーバがゼロ知識証明を検証することによって、差分のシェアの受信した秘密バージョンの正しさを検証するステップをさらに含んでいてもよい。

秘密鍵への不正アクセスを試みることとは別に、敵対者は、正直な当事者、すなわち正直なサーバに偽の情報を提供することによって、システムを積極的に破壊しようとすることもできる。例えば、敵対者はサーバの一つ、例えば第１のサーバを破損させることができる。この場合、他のサーバによって受信され、第１のサーバから発信された差分のシェアが破損される可能性がある。したがって、当事者の１人が所定のプロトコルから逸脱した場合に、それを検出できるようにする必要性があり得る。本実施形態によれば、これは、ゼロ知識証明の検証によって行われる。

本明細書において、「ゼロ知識証明」という用語は、一方の当事者が、秘密に関する詳細を明らかにすることなく、秘密を知っていることを他方の当事者に対して証明する方法を意味すると解釈されるべきである。したがって、本実施形態によれば、第１のサーバは、他のサーバに転送される差分のシェアの秘密バージョンが、実際のシェアの秘密バージョンであることを実際に証明する。第１のサーバは、ゼロ知識で、すなわち、実際のシェアに関する詳細を明らかにすることなく、これを行う。その後、他のサーバは証明を検証し、証明が無効であることが判明した場合、他のサーバは、第１のサーバが破損していることを知り、リフレッシュプロトコルを中止させることができる。

代替的に若しくは追加的に、本方法は、第１のサーバがゼロ知識証明を検証することによって、受信した累積秘密バージョンの正しさを検証するステップをさらに含んでもよい。

これは、上述した実施形態と同様である。ただし、この場合、バックアップからの復元時に受信した蓄積された秘密バージョンが実際に正しいことを保証するのは、第１のサーバである。それによって、第１のサーバは、他のサーバのうちの一つ以上が破損しているか、及び／又は所定のプロトコルから逸脱しているかを検出することが可能である。この場合、第１のサーバは、復元プロセスを中止させることができる。

代替的に若しくは追加的に、秘密をリフレッシュする各ステップは、各サーバが他のサーバと同じ秘密の差分を保持していることを、例えば差分、または差分のハッシュダイジェストを放送して比較することにより検証するステップをさらに含んでもよい。各サーバが同じ秘密差異を保持していることに同意しない場合、リフレッシュ処理は中止されてもよい。

なお、分散された秘密鍵は、秘密署名鍵であってもよい。この実施形態によれば、本システムは、分散された秘密鍵を用いて、デジタル署名を提供するために適用される。

さらに、この実施形態によれば、差分の秘密のシェア及び／又は蓄積された秘密バージョンの正しさは、サーバがテスト署名、例えば閾値署名を生成し、当事者がテスト署名が有効かつ正しいことを検証することによって保証されてもよい。

代替策として、分散された秘密鍵は、秘密暗号化鍵であってもよい。この実施形態によれば、システムは、分散された秘密鍵を用いて、データの暗号化及び復号化を提供するように利用される。

サーバが二つしかない特別な場合、第２のサーバは、自身のシェアの値を知っており、二つのシェアの合計がゼロであることを知っているので、第１のサーバのシェアの値がゼロであることを既に知っている。この場合、また、秘密バージョンとゼロシェアが暗号化を使用して生成される場合、ゼロ知識証明を使用する必要はない。第２のサーバは、代わりに、第１のサーバのゼロのシェアの暗号化を自ら実行し、これを第１のサーバから受信した秘密バージョンと比較することによって、受信したゼロの秘密のシェアの正しさを検証することができる。これは、決定論的暗号化スキームを使用することによって、またはその代わりに、第１のサーバが、そのゼロのシェアを暗号化するために使用したランダムネスを第２のサーバに明らかにさせることによって、行うことができる。

この方法は、第１のサーバが新しいバックアップを作成するステップと、サーバがオリジナルの秘密鍵をリフレッシュするステップとを少なくとも１回繰り返すことをさらに含み、第１のサーバがオリジナルの秘密鍵のシェアを復元するステップは、新しいバックアップとともに保存された秘密鍵のシェアを復元することを、含み得る。

本実施形態によれば、新たなバックアップが作成される度に上述した処理が繰り返され、バックアップからの復元が必要な場合には、利用可能な最新のバックアップが使用される。したがって、新しいバックアップが作成された時点で有効であった分散された秘密鍵は、例えば、請求項の方法の意味において、オリジナルの秘密鍵とみなすことができる。

代替的に若しくは追加的に、各リフレッシュは、第１のサーバが差分のシェアの累積された秘密バージョンを生成し、第１のサーバで累積された秘密バージョンを格納するステップをさらに含み、差分のシェアの秘密バージョンは新しいバックアップの一部を形成し、第１のサーバが最新のリフレッシュした秘密鍵のシェアを復元するステップは、新しいバックアップの一部を形成する秘密鍵の復元済みのシェア、新しいバックアップの一部を形成する累積した差の秘密バージョンおよび他のサーバの少なくともいくつかから受信する累積した秘密バージョンに基づいて実行されてもよい。

場合によっては、サーバのバックアップは、独立した自律的なプロセスとして実行され、分散された秘密鍵の生成とは相関がないことがある。したがって、あるバックアップに含まれる秘密鍵のシェアは、バックアップに含まれるシェアと他のサーバから受け取った蓄積された秘密バージョンとに基づいて、第１のサーバの最新のリフレッシュされた鍵のシェアを容易に復元することができないという意味において、他のサーバが保持する蓄積された差分のシェアの秘密バージョンと必ずしも一致しない可能性がある。本実施形態によれば、これは以下のように処理することができる。

第１のサーバは、リフレッシュのたびに、差分のシェアの累積された秘密バージョンを生成して他のサーバに送信するだけでなく、自らも累積された差分のそれ自身のシェアについての累積された秘密バージョンを保持し、これをその時点で有効なリフレッシュされた秘密鍵のシェアと共に記憶し、従前のバージョンを削除しておく。差分の累積された秘密バージョンは、累積された差分の個々の差分を容易に導き出せないようなものであることが好ましい。例えば、これは、差分の累積された秘密バージョンが、復号化が第１のサーバからアクセスできない同型の公開鍵暗号化に基づいていることを必要とし、例えば、復号化鍵は、コールドストレージ又はハードウェアセキュリティモジュール（ＨＳＭ）に格納されていてもよい。

新しいバックアップが作成されると、その時点で有効なリフレッシュされた秘密鍵のシェアと、その時点で有効な累積された差分の秘密バージョンとが、新しいバックアップの一部を構成する、すなわち、新しいバックアップの一部として保存される。

後の時点で、バックアップから秘密鍵のシェアを復元する必要がある場合、第１のサーバは、もはや有効ではないリフレッシュされたシェアと蓄積された差分の秘密バージョンとをバックアップから復元する。また、第１のサーバは、少なくともいくつかの他のサーバから、蓄積された差分の秘密バージョンを受信する。暗号化の同型性を利用して、第１のサーバは、バックアップからの差分の秘密バージョンと、他のサーバの少なくともいくつかから受け取った差分の秘密バージョンとを加算する。これは、バックアップからのもはや有効でないリフレッシュされたシェアと、第１のサーバが復元したいと思う最新のリフレッシュされたシェアとの間の累積された差分である結合された累積された差分の秘密バージョンを生成する。

次に、第１のサーバは、この結合された秘密の累積された差分を、例えば、コールドストレージから秘密の復号化鍵を要求すること、結合された秘密の累積された差分をハードウェアセキュリティモジュール（ＨＳＭ）に送信することなどにより復号化する。次に、第１のサーバは、その最新のリフレッシュされたバージョンのシェアを復元するために、復号された累積された差分をバックアップからそのもはや有効ではないシェアに加える（バックアップからの累積された差分を加えると、シェアはその作成時に戻り、他のサーバからの累積された差分を加えるとその作成時から現在の時間のシェアに至る）。

このように、オリジナルの秘密鍵のシェアを復元するステップと、最新のリフレッシュされた秘密鍵のシェアを復元するステップは、上記のように一つのステップで実行されてもよい。あるいは、これらは別々のステップとして実行されてもよく、その場合、バックアップの一部を形成する累積された差分によって、オリジナル秘密鍵の第１のサーバのシェアが復元され、その後、復元されたオリジナルのシェアと受信した累積秘密バージョンとに基づいて、上記の方法で、最新のリフレッシュされた秘密鍵のシェアが復元されるようにしてもよい。

図面の詳細な説明
図１は、分散された秘密鍵をバックアップストレージから復元するための先行技術方法を説明するための図である。図１に示す例では、オリジナルの秘密鍵ｓは、三つのサーバ、すなわちサーバ１、サーバ２、サーバ３に分散されている。したがって、各サーバは秘密鍵のシェアを持ち、どのサーバもすべてのシェア、ひいては鍵の全体を所有することはない。したがって、サーバ１はシェアｓ１＾１を、サーバ２はシェアｓ２＾１を、サーバ３はシェアｓ３＾１を保有する。秘密鍵は、代替的に、二つのサーバ間、または四つ以上のサーバ間で分配されてもよく、図１における三つのサーバの存在は単に例示に過ぎないことに留意されたい。

時刻Ｔ＾１（オリジナルの秘密鍵がサーバ間で分散された直後でもよい）において、サーバ１はバックアップをコールドストアに保存する。このバックアップは、サーバ１の秘密鍵のシェアｓ１＾１から構成される。

時刻Ｔ＾２において、サーバは分散された秘密鍵をリフレッシュし、各サーバはリフレッシュされた秘密鍵のシェアを保持する。従って、サーバ１はシェアｓ１＾２を、サーバ２はシェアｓ２＾２を、サーバ３はシェアｓ３＾２を保持し、従前のシェアは無効となり、削除された。

時刻Ｔ＾３において、同様に分散された秘密鍵のリフレッシュが行われる。これにより、サーバ１がシェアｓ１＾３を、サーバ２がシェアｓ２＾３を、サーバ３がシェアｓ３＾３を保有する。なお、このリフレッシュ処理は、さらに複数回繰り返されてもよい。

シェアｓ１＾３、ｓ２＾３、ｓ３＾３が有効な間に、サーバ１にデータ損失が発生し、バックアップからの復元が必要となる。しかし、バックアップとともに保存されていた鍵のシェアは、現在有効な鍵のシェアであるｓ１＾３ではなく、有効でなくなったｓ１＾１である。したがって、サーバ１は、現在有効な秘密鍵のシェアをバックアップから復元することができない。

図２は、本発明の第１の実施形態による方法を説明するための図である。図２では、簡略化のために、サーバ１およびサーバ２の二つのサーバのみが図示されている。しかしながら、代替的に、三つ以上のサーバが適用され得ることに留意されたい。

図１を参照して上述した先行技術の方法と同様に、秘密鍵は二つのサーバ間で分配され、サーバ１はそのシェアｓ１＾１のバックアップをコールドストアに保存する。しかし、サーバ１も秘密鍵ｓｋと公開鍵ｐｋとの鍵の対を作成し、秘密鍵ｓｋはバックアップとともにコールドストアに保存される。この鍵の対は、加法的同型性暗号化スキームを構成する。

また、図１を参照して上述した先行技術の方法と同様に、分散された秘密鍵は、複数回リフレッシュされる。図２に示される方法では、分散された秘密鍵の各リフレッシュは、以下の方法で実行される。

分散された秘密鍵は標準的な方法でリフレッシュされ、それによってリフレッシュされた分散された秘密鍵と、リフレッシュされた秘密鍵と従前の秘密鍵との間の差分が生成され、その差分はサーバ間でゼロのシェアリングを構成している。これは少なくとも二つの方法で行うことができる。サーバはゼロのシェアリングを生成し、各サーバはゼロのシェアリングのシェアを従前の秘密鍵のシェアに追加し、それによってリフレッシュされた鍵のシェアを取得してもよい。代替策として、サーバは、例えば、従前の鍵の新しいシェアリングを作成することによって、リフレッシュされた鍵を生成してもよく、各サーバは、従前の秘密鍵のシェアとリフレッシュされた秘密鍵のシェアの間の差としてゼロのシェアリングのシェアを導き出してもよい。

いずれにしても、秘密鍵の第１のリフレッシュの後、時間Ｔ２＾において、第１のサーバはリフレッシュされた秘密鍵のシェアｓ１＾２を保持し、ｓ１＾２＝ｓ１＾１＋ｄ１＾１であり、ここでｄ１＾１はサーバ１の、ゼロのシェアリングのシェアである。

次にサーバ１は、従前に生成した鍵の対の公開鍵を用いて、ゼロのシェアリングのシェア、ｄ１＾１を暗号化し、それによりＤ＾１＝Ｅｎｃ_ｐｋ（ｄ１＾１）を得て、サーバ２を含む他のサーバにＤ１を提供する。サーバ１は、さらにｓ１＾１、ｄ１＾１、ｓｋを削除し、それによりｓｋはバックアップストレージにのみ保存される。

Ｄ＾１を受け取ると、サーバ２は、受け取った暗号化された、ゼロのシェアリングのシェアの、累積されたバージョンを生成する。Ｄ＾１は、第１のリフレッシュに関するものであるため、サーバ２が受信する第１の暗号化されたシェアでもあり、したがって、累積されたバージョンはこの場合、Ａ＾１＝Ｄ＾１である。

次のリフレッシュの際、サーバ１は暗号化されたシェア、Ｄ＾２＝Ｅｎｃ_ｐｋ（ｄ１＾２）をサーバ２に提供し、サーバ２は新しい累積されたバージョン、Ａ＾２＝Ａ＾１＋Ｄ＾２＝Ｄ＾１＋Ｄ＾２を生成して、Ａ＾１を削除する。さらに、それ以降のリフレッシュの度に、サーバ２は、新たな累積されたバージョン、Ａ＾ｎ＝Ａ＾（ｎ－１）＋Ｄ＾ｎ＝Ｄ＾１＋Ｄ＾２＋．．．＋Ｄ＾（ｎ－１）＋Ｄ＾ｎを生成し、従前の累積されたバージョン、Ａ＾（ｎ－１）を削除する。ゼロのシェアリングのシェアに適用される暗号化は、加法的同型性暗号化スキームで行われるので、暗号化されたバージョンの合計は、合計の暗号化されたバージョン、すなわち、Ｅｎｃ_ｐｋ（ｄ１＾１＋ｄ１＾２）＝Ｅｎｃ_ｐｋ（ｄ１＾１）＋Ｅｎｃ_ｐｋ（ｄ１＾２）＝Ｄ＾１＋Ｄ＾２に等しくなる。したがって、サーバ２が保持する累積されたバージョンは、バックアップが作成されてから実行された各リフレッシュに関連するサーバ１の、ゼロのシェアリングのシェアの、合計の暗号化されたバージョンに相当する。

図２に示される方法において、サーバ１は、秘密鍵のシェアｓ１＾４が有効である間に、バックアップからの復元を必要とするデータ損失を経験する。そこで、サーバ１は、バックアップから、オリジナルの分散された秘密鍵、ｓ１＾１と秘密鍵ｓｋとの、シェアを復元する。さらに、サーバ１は、現在有効な蓄積されたバージョンＡ＾４を他のサーバに要求し、少なくともサーバ２は、Ａ＾４をサーバ１に返す。

サーバ１は、復元された秘密鍵ｓｋを用いてＡ＾４を復号し、オリジナルの分散された秘密鍵のサーバ１のシェアに加算された差分の合計を得ることができる。つまり、
Ｄｅｃ_ｓｋ（Ａ＾４） ＝ Ｄｅｃ_ｓｋ（Ｄ＾１＋Ｄ＾２＋Ｄ＾３）
＝ Ｄｅｃ_ｓｋ（Ｄ＾１）＋Ｄｅｃ_ｓｋ（Ｄ＾２）＋Ｄｅｃ_ｓｋ（Ｄ＾３）
＝ ｄ１＾１＋ｄ１＾２＋ｄ１＾３

したがって、サーバ１は、ｓ１＾４＝ｓ１＾１＋ｄ１＾１＋ｄ１＾２＋ｄ１＾３＝ｓ１＾１＋Ｄｅｃ_ｓｋ（Ａ＾４）となるので、復元されたオリジナルのシェアｓ１＾１に、復号化された累積されたバージョンＤｅｃ_ｓｋ（Ａ＾４）を加えることにより、有効な分散された鍵のシェアｓ１＾４を復元することができる。

さらに、中間のリフレッシュされた鍵のシェアｓ１＾２、ｓ１＾３のいずれについても、サーバ１に対して何も明かすことなく、有効なシェアが復元される。

図３は、本発明の第２の実施形態による方法を説明するための図である。この方法は、図２に例示された方法と非常によく似ているので、ここでは詳細な説明を省略する。ただし、図３に例示した方法では、分散された秘密鍵のリフレッシュは、以下の手順で実行される。

サーバ１は、図２を参照して上述した方法で、リフレッシュされた秘密鍵のシェアと、リフレッシュされた鍵と従前の鍵との間の差分を構成するゼロのシェアとを、取得する。そして、差分のサーバ１のシェアの秘密のシェアリング、第１のリフレッシュにおけるｄ１＾１が、作成され、他のサーバの各々がシェアを受け取る。例えば、サーバ２は、シェアａ２＾１を受け取る。

サーバ２を含む他のサーバは、各リフレッシュ時に、新たに受信したシェアを従前の累積されたバージョンＡ２＾（ｎ－１）に追加し、その後、従前の累積されたバージョンＡ２＾（ｎ－１）を削除することによって、差分の累積されたバージョンＡ２＾ｎを生成する。

秘密鍵のシェアｓ１＾４が有効な間に、サーバ１にデータ損失が発生し、バックアップからの復元が必要となる。そこで、サーバ１は、オリジナルの分散された秘密鍵ｓ１＾１をバックアップから復元し、他のサーバに蓄積されたバージョンを要求する。他のサーバは、サーバ１に対して蓄積されたバージョンを提供する。例えば、サーバ２はａ２＾４を提供し、サーバｉはａｉ＾４を提供する。そして、サーバ１は、他のサーバから受け取った累積されたバージョンを再結合することにより、各リフレッシュに関連する差分の合計を復元することができ、復元された合計を復元されたオリジナルのシェアｓ１＾１に加えることにより、有効なシェアｓ１＾４を得ることができる。また、本実施形態では、中間のリフレッシュされた鍵のシェアｓ１＾２、ｓ１＾３のいずれについても、何も明らかにされない。

図４は、本発明の第３の実施形態による方法を説明するための図である。図４に示された方法は、図２及び図３に示された方法と非常に類似しているので、ここでは詳細な説明は省略する。しかし、図４の実施形態では、サーバ１の差分ｄ１＾１のシェアは、図３を参照して上述したように秘密シェアされ、秘密のシェアは、それぞれの他のサーバに提供される前に、図２を参照して上述したように、加法的同型性暗号化スキームを使用して暗号化される。したがって、図４の実施形態は、図２の実施形態と図３の実施形態との組み合わせと見なすことができる。これにより、システムにさらなる安全性が付加される。

図５は、本発明の第４の実施形態による方法を説明するための図である。図５の方法は、図２に図示された方法と非常に類似しているので、ここでは詳細な説明を省略する。

図５に例示される方法では、サーバ１は、各リフレッシュ中にゼロ知識証明、ＺＫＰを生成し、これを、ゼロシェアリングのシェアの暗号化されたバージョンと共に他のサーバに転送する。その後、他のサーバはゼロ知識証明を検証する。少なくとも一つのサーバがゼロ知識証明が有効でないと判断した場合、リフレッシュ処理は中断される。

図６は、本発明の第５の実施形態による方法を説明するための図である。図６の方法は、図２に例示された方法と非常に類似しているので、ここでは詳細な説明を省略する。ただし、図６に例示した方法では、各サーバは、各リフレッシュ時に、自分のバージョンを他の全てのサーバに送信し、各サーバは、受信したバージョンを比較することにより、蓄積されたバージョンを比較する。そして、少なくとも一つのサーバが、同一でない累積バージョンを受信した場合には、リフレッシュ処理を中止する。

図７は、本発明の第６の実施形態による方法を説明するための図である。図７の方法は、図３に示された方法と非常に類似しているので、ここでは詳細な説明を省略する。しかしながら、図７の実施形態では、各リフレッシュは、リフレッシュされた秘密鍵およびゼロのシェアリングが生成される前に実行される追加の検証ステップを含む。

分散された秘密鍵は、この場合、デジタル閾値署名の生成に使用される署名鍵であり、各サーバは、公開検証鍵ＶＫを所持している。追加の検証ステップでは、サーバはランダムメッセージＭ＾１について合意し、分散された鍵の夫々のシェアを用いてランダムメッセージに署名し、これにより署名ＳＩＧ＾１を生成する。生成された署名は各サーバに提供され、各サーバは公開検証鍵ＶＫにより署名を検証する。少なくとも一つのサーバが署名を検証できない場合、リフレッシュ処理は中断される。

なお、図４～７は分散された秘密鍵のリフレッシュのみを図示しているが、バックアップからの復元も、基本的には図２または図３を参照して上述した方法で実行できることを理解されたい。

図８は、本発明の第７の実施形態による方法を説明するための図である。図８の方法は、図２に図示された方法と非常に類似しているので、ここでは詳細な説明は省略する。

図８に例示された方法は、図７の実施形態と同様に、閾値署名スキームを使用するが、図７の実施形態とは対照的に、図８の方法では、分散された秘密鍵は閾値署名スキームの分散された鍵と同一である必要はない。図８の実施形態では、閾値署名スキームの公開検証鍵（ＶＫ）は、バックアップに格納されている。

図８の実施形態では、サーバは、分散された署名鍵を用いて差分の暗号化されたシェアＤ＾１に署名し、それによって署名ＳＩＧ＾１を生成する。各サーバは、ＳＩＧ＾１を差分の蓄積されたバージョンとともに保存する。

復元が必要な場合、サーバ１は他のサーバに蓄積されたバージョンを要求し、他のサーバも現在有効な署名（図８の例では、ＳＩＧ＾２）を提供する。次に、サーバ１は、署名ＳＩＧ＾２を検証し、検証できない場合、復元プロセスを中止する。

選択的に、タイムスタンプが含まれていてもよく、その場合、サーバ１は、Ｔ＾２が実際にデータ損失の直前の時間を表していることも検証する。

Claims (12)

1. 分散された秘密鍵をバックアップストレージから復元するための方法であって、
   オリジナルの秘密鍵を生成し、オリジナルの秘密鍵を二つ以上のサーバに分散するステップであって、各サーバがオリジナルの秘密鍵のシェアを保持し、どのサーバもオリジナルの秘密鍵の全てのシェアを保持しない、分散するステップと、
   第１のサーバが、バックアップを作成するステップであって、バックアップは少なくとも第１のサーバによって保持されるオリジナルの秘密鍵のシェアを含む、作成するステップと、
   前記サーバが、少なくとも一度、オリジナルの秘密鍵をリフレッシュするステップであって、各リフレッシュするステップは、
   前記サーバが、リフレッシュされた分散された秘密鍵、及び、前回の秘密鍵とリフレッシュされた秘密鍵との分散された差分を生成し、各サーバが分散された差分のシェアを保持し、分散された差分がゼロのシェアを構成し、前記サーバが前回の秘密鍵のシェアを破棄するステップと、
   各サーバが、前記分散された差分のシェアの秘密バージョンを生成し、該秘密バージョンを他のサーバの少なくとも一部とシェアするステップと、
   各サーバが、受信した前記分散された差分のシェアの受信した秘密バージョンと従前の累積された秘密バージョンとに基づいて、他のサーバから受信した前記分散された差分のシェアの累積された秘密バージョンを生成するステップと
   を含む、リフレッシュするステップと、
   前記第１のサーバが、前記バックアップから前記オリジナルの秘密鍵のシェアを復元して、前記他のサーバに前記分散された差分のシェアの前記累積された秘密バージョンを要求するステップと、
   前記他のサーバのうちの少なくとも幾つかが、前記第１のサーバの前記分散された差分の累積された秘密バージョンを、前記第１のサーバに提供するステップと、
   前記第１のサーバが、前記受信した蓄積された秘密バージョンと前記オリジナルの秘密鍵の前記復元されたシェアから、最新のリフレッシュされた秘密鍵のシェアを復元するステップと
   を含む、方法。
2. 各サーバが、前記分散された差分のシェアの秘密バージョンを生成する前記ステップは、加法的同型性スキームによって実行され、
   各サーバが、累積された秘密バージョンを生成する前記ステップは、各サーバが、前記分散された差分のシェアの前記受信した秘密バージョンを、夫々の従前の累積された秘密バージョンに加え、前記従前の累積された秘密バージョンを破棄することを含む、
   請求項１に記載の方法。
3. 前記加法的同型性スキームは公開鍵暗号化スキームであり、
   前記第１のサーバがバックアップを作成する前記ステップは、バックアップの一部としてプライベート復号化鍵を記憶することを含む、
   請求項２に記載の方法。
4. 各サーバが、前記分散された差分のシェアの秘密バージョンを生成する前記ステップは、各サーバが、前記分散された差分のシェアのシェアリングを作成し、他のサーバの少なくとも一部の間で前記シェアを分散することを含む、
   請求項２又は３に記載の方法。
5. 各リフレッシュは、
   前記サーバが、ゼロのシェアリングを作成し、各サーバが、ゼロの前記シェアリングのシェアを従前の秘密鍵のシェアに追加し、それによって前記サーバの間で分散される前記リフレッシュされた秘密鍵を作成し、前記従前の秘密鍵のシェアを破棄するステップであって、ゼロの前記シェアリングは分散された差分を構成する、破棄するステップと、
   各サーバが、ゼロの前記シェアリングの秘密バージョンを生成し、前記他のサーバの少なくとも一部と該秘密バージョンをシェアリングするステップと
   を含む、請求項１～４のいずれか一に記載の方法。
6. オフラインストレージに前記バックアップを記憶するステップを、更に含む、
   請求項１～５のいずれか一に記載の方法。
7. 前記秘密鍵をリフレッシュする各ステップは、各サーバが、ゼロ知識証明を検証することにより、前記分散された差分の前記シェアについての前記受信した秘密バージョンの正しさを検証するステップを
   更に含む、請求項１～６のいずれか一に記載の方法。
8. 前記第１のサーバが、ゼロ知識証明を検証することにより、前記受信した蓄積された秘密バージョンの正しさを検証するステップを、
   更に含む、請求項１～７のいずれか一に記載の方法。
9. 前記分散された秘密鍵が秘密署名鍵である、請求項１～８のいずれか一に記載の方法。
10. 前記分散された秘密鍵が秘密暗号化鍵である、請求項１～８のいずれか一に記載の方法。
11. 更に、
    前記第１のサーバが、新しいバックアップを作成するステップと、
    前記サーバが前記オリジナルの秘密鍵をリフレッシュする前記ステップを少なくとも１回繰り返すステップと
    を含み、
    第１のサーバが、前記オリジナルの秘密鍵のシェアを復元するステップは、前記新しいバックアップにより記憶された前記秘密鍵のシェアを復元することを含む、
    請求項１～１０のいずれか一に記載の方法。
12. 各リフレッシュは、更に、第１のサーバが、前記分散された差分のシェアについての累積された秘密バージョンを生成し、前記第１のサーバにて前記累積された秘密バージョンを記憶するステップを、含み、
    前記分散された差分のシェアの前記秘密バージョンが、前記新しいバックアップの一部を形成し、
    前記第１のサーバが、前記最新のリフレッシュされた秘密鍵のシェアを復元するステップが、前記新しいバックアップの一部を形成する前記秘密鍵の前記復元されたシェアと、前記新しいバックアップの一部を形成する前記累積した差分の前記秘密バージョン及び前記他のサーバの少なくとも一部から受信した前記累積した秘密バージョンと
    に基づいて実施される、請求項１１に記載の方法。

Images