(57)【特許請求の範囲】
【請求項１】
下記を具備する暗号サービスを供給する方法：
第１の関数を第１の複数の代替関数として再表現することであって、前記第１の関数は前記暗号サービスを供給するのに有用な特性を有する；
前記第１の複数の代替関数を複数の区別可能な電子暗号処理装置に分配する；第１の操作期間中に、（ｉ）暗号処理装置の選択されたセットの各々において、第１の部分結果を取得するために前記第１の複数の代替関数の少なくとも１つを第１の入力メッセージに電子的に適用し、（ｉｉ）前記入力メッセージに関連する第１の最終電子出力を取得するために第１の部分結果を結合することであって、前記出力は、前記第１の関数を前記入力メッセージに適用することにより得られたであろう出力と同一である；
更新期間において、（ｉ）前記第１の関数を再表現する第２の複数の代替関数を発生する、（ｉｉ）前記第２の複数の代替関数を区別可能な暗号処理装置に分配する；
第２の操作期間中に、（ｉ）暗号処理装置の選択されたセットの各々において、第２の部分結果を取得するために前記第２の複数の代替関数を第２の入力メッセージに電子的に適用する、（ｉｉ）前記入力メッセージに関連する第２の最終電子出力を取得するために第２の部分結果を結合することであって、前記第２の出力は、前記第１の関数を前記第２の入力メッセージに適用することにより得られたであろう前記出力と同一である．
【請求項２】
前記第１の関数はＲＳＡ関数である、請求項１の方法。
【請求項３】
前記ＲＳＡ関数のためのプライベート鍵は整数のサブセット上にある、請求項２の方法。
【請求項４】
前記第１の関数は位数または複数の位数が公に知られていないグループから引き出される鍵を有する暗号関数である、請求項１の方法。
【請求項５】
前記第１の関数は共有平行移動の特性を有する、請求項１の方法。
【請求項６】
前記第１の関数は関連する共有スペースと前記共有スペースにおいて逆数が計算できる特性を有する、請求項１の方法。
【請求項７】
前記第１の関数は関連する共有スペースと前記共有スペースがシミュレート可能な特性を有する、請求項１の方法。
【請求項８】
前記第１の複数の代替関数の各関数は、有限フィールド上のジェネレーターに基づいている、請求項１の方法。
【請求項９】
前記第１の複数の代替関数の各関数は指数関数である、請求項１の方法。
【請求項１０】
複数の代替関数の各関数は、環に関して定義される、請求項１の方法。
【請求項１１】
複数の代替関数の各関数がグループに関して定義される、請求項１の方法。
【請求項１２】
複数の代替関数の各関数は整数のサブセットに関して定義される、請求項１の方法。
【請求項１３】
前記第１の関数は鍵を有する暗号関数であり、
前記第１の関数は、前記鍵の逆数が公に知られた情報を用いて実行可能に計算できない特性を有する、請求項１の方法。
【請求項１４】
前記暗号サービスはデジタル署名サービスである、請求項１の方法。
【請求項１５】
前記暗号(cryptographic)サービスは、暗号化(encryption)サービスである、請求項１の方法。
【請求項１６】
前記暗号サービスは、復号サービスである、請求項１の方法。
【請求項１７】
前記暗号サービスは、認証サービスである、請求項１の方法。
【請求項１８】
前記第２の複数の代替関数を発生するステップは、前記第１の複数の代替関数の少なくともいくつかを前記第２の複数の代替関数として再表現するステップを含む、請求項１の方法。
【請求項１９】
前記第２の複数の代替関数を発生するステップは、前記暗号処理装置のセットが前記第１の複数の代替関数を適用できなくするステップを含む、請求項１の方法。
【請求項２０】
前記第１の関数を第１の複数の代替関数として再表現するステップは、前記第１の関数をｔ−ｏｆ−ｌシステムの形式に再表現するステップを含み、ｌは部分結果を供給するように構成された多数の暗号処理装置であり、ｔは、第１の関数を入力メッセージに適用することにより得られたであろう同じ結果である最終結果を発生するのに必要な部分結果の最小数である、請求項１の方法。
【請求項２１】
数ｌは数ｔより大きい、請求項２０の方法。
【請求項２２】
前記第１の関数を再表現する第２の複数の代替関数を発生するステップは、ｔ’−ｏｆ−ｌ’システムの第１の関数の再表現を発生するステップを含み、ｌ’は部分結果を供給するように構成された多数の暗号処理装置であり、ｔ’は、前記第１の関数を入力メッセージに適用することにより得られたであろう同じ結果で最終結果を発生するのに必要な部分結果の最小数である、請求項２０の方法。
【請求項２３】
数ｌ’は数ｔ’より大きい、請求項２２の方法。
【請求項２４】
数ｔ’は数ｔと等しくない、請求項２２の方法。
【請求項２５】
数ｌ’が数ｌと等しくない、請求項２２の方法。
【請求項２６】
前記第１の関数を再表現する第２の複数の代替関数を発生するステップは、
前記第１の複数の代替関数のすくなくともいくつかをｔ’−ｏｆ−ｔ’システムの形式に再表現するステップと、ｔ’−ｏｆ−ｔ’システムを前記第２の複数の代替関数の形式に再表現するステップを含む、請求項１の方法。
【請求項２７】
前記第１の複数の代替関数のすくなくともいくつかをｔ’−ｏｆ−ｔ’システムの形式に再表現するステップは、
（１）  暗号装置の数ｔ’を選択するステップと、（２）単独でまたは協力して動作しているｔ’暗号処理装置のいずれかが、他のｔ’暗号処理装置がプロトコルに違反して動作しているかどうかを検出することができるように、前記プロトコルを用いたｔ’暗号処理装置の間で情報を通信するステップを含む、請求項２６の方法。
【請求項２８】
複数の装置の任意の少数は、任意に誤動作するかもしれない、請求項１の方法。
【請求項２９】
下記を具備する、公開鍵暗号サービスを供給する方法：
関連する公開鍵およびプライベート鍵を有するＲＳＡ関数を第１の複数の代替関数として再表現することであって、前記ＲＳＡ関数は前記暗号サービスを供給するのに有用な特性を有する；
前記第１の複数の代替関数を複数の区別できる電子暗号処理装置に分配するステップ；
第１の操作期間中に、（ｉ）暗号処理装置の選択されたセットの各々において、第１の部分結果を取得するために前記第１の複数の代替関数の少なくとも１つを第１の入力メッセージに電子的適用し、（ｉｉ）前記第１の入力メッセージに関連する第１の最終電子出力を取得するために第１の部分結果を結合するステップであって、前記第１の出力は、前記ＲＳＡ関数を前記入力メッセージに適用することにより得られたであろう出力に同一であるステップ；
更新期間中に、（ｉ）ＲＳＡ関数を再表現する第２の複数の代替関数を発生することにより、および（ｉｉ）前記第２の複数の代替関数を区別できる暗号処理装置に分配することにより複数の区別できる暗号処理装置を更新するステップ；
第２の操作期間中に、（ｉ）暗号処理装置の選択されたセットの各々において、第２の部分結果を取得するために前記第２の複数の代替関数の少なくとも１つを第２の入力メッセージに電子的に適用し、（ｉｉ）前記第２の入力メッセージに関連する第２の最終電子出力を取得するために第２の部分結果を結合するステップであって、前記第２の出力は、前記ＲＳＡ関数を前記第２の入力メッセージに適用することにより得られたであろう出力と同一であるステップ。
【請求項３０】
前記ＲＳＡ関数のためのプライベート鍵は整数のサブセット上にある、請求項２９の方法。
【請求項３１】
前記第１の複数の代替関数の各関数はジェネレーターを採用する、請求項２９の方法。
【請求項３２】
前記第１の複数の代替関数の各関数は指数関数である、請求項２９の方法。
【請求項３３】
複数の代替関数の各関数は環に関して定義される、請求項２９の方法。
【請求項３４】
複数の代替関数の各関数はグループに関して定義される、請求項２９の方法。
【請求項３５】
複数の代替関数の各関数は整数のサブセットに関して定義される。
【請求項３６】
前記第２の複数の代替関数を発生するステップは、前記第１の複数の代替関数の少なくともいくつかを前記第２の複数の代替関数として再表現するステップを含む、請求項２９の方法。
【請求項３７】
前記第２の複数の代替関数を発生するステップは、前記暗号処理装置のセットが前記第１の複数の代替関数を適用できなくするステップを含む、請求項２９の方法。
【請求項３８】
前記第１の関数を第１の複数の代替関数として再表現するステップは、前記第１の関数をｔ−ｏｆ−ｌシステムの形式で再表現するステップを含み、ｌは部分結果を供給するように構成された多数の暗号処理装置であり、ｔは、前記第１の関数を入力メッセージに適用することにより得られたであろう同じ結果である最終結果を発生するのに必要な部分結果の最小数である、請求項２９の方法。
【請求項３９】
数ｌは数ｔより大きい、請求項３８の方法。
【請求項４０】
前記第１の関数を再表現する第２の複数の代替関数を発生するステップは、ｔ’−ｏｆ−ｌ’システムとして前記第１の関数の再表現を発生するステップを含み、ｌ’は部分結果を供給するように構成された多数の暗号処理装置であり、ｔ’は前記第１の関数を入力メッセージに適用することにより取得されたであろう同じ結果である最終結果を発生するのに必要な部分結果の最小数である、請求項３８の方法。
【請求項４１】
数ｌ’は数ｔ’より大きい、請求項４０の方法。
【請求項４２】
数ｔ’は数ｔと等しくない、請求項４０の方法。
【請求項４３】
数ｌ’は数ｌと等しくない、請求項４０の方法。
【請求項４４】
前記第１の関数を再表現する第２の複数の代替関数を発生するステップは、
前記第１の複数の代替関数の少なくともいくつかをｔ’−ｏｆ−ｌ’システムの形式で再表現するステップと、前記ｔ’−ｏｆ−ｔ’システムを前記第２の複数の代替関数の形式に再表現するステップを含む、請求項２９の方法。
【請求項４５】
前記第１の複数の代替関数のすくなくともいいくつかをｔ’−ｏｆ−ｔ’システムの形式に再表現するステップは、
（１）暗号処理装置のサブセット番号ｔ’を選択するステップと、（２）単独でまたは協力して動作するｔ’暗号処理装置のいずれかが、別のｔ’暗号処理装置がプロトコルに違反して動作しているかどうかを検出することができるように、前記プロトコルを用いたｔ’の暗号処理装置の中で情報を通信するステップとを含む、請求項４４の方法。
【請求項４６】
複数の装置の任意の少数は任意に誤動作するかもしれない、請求項２９の方法。
【請求項４７】
下記ステップを具備する暗号サービスを供給する方法：
第１の関数を第１の複数の代替関数として再表現することであって、前記第１の関数は、位数または複数の位数が公に知られていないドメインから引き出された公開鍵およびプライベート鍵に関連して、暗号サービスを供給するのに有用な特性を有するステップ；
前記第１の複数の代替関数を複数の区別できる電子暗号処理装置に分配するステップ；
第１の操作期間中に、（ｉ）暗号処理装置の選択されたセットの各々において、第１の部分結果を取得するために前記第１の複数の代替関数を第１の入力メッセージに電子的に適用し、（ｉｉ）前記入力メッセージに関連する第１の最終電子出力を取得するために第１の部分結果を結合するステップであって、前記第１の出力は、あたかも、前記第１の関数を前記第１の入力メッセージに適用することにより取得されたかのように、前記公開鍵とプライベート鍵の１つを用いて処理することができる合法的な結果であるステップ；
更新期間中に、（ｉ）前記第１の関数を再表現する第２の複数の代替関数を発生することにより、および（ｉｉ）前記第２の複数の代替関数を、区別できる暗号処理装置に分配することにより前記複数の区別できる暗号処理装置を更新するステップ；
第２の操作期間中に、（ｉ）暗号処理装置の選択されたセットの各々において、第２の部分結果を取得するために前記第２の複数の代替関数の少なくとも１つを第２の入力メッセージに電子的に適用し、（ｉｉ）前記第２の入力メッセージに関連する第２の最終電子出力を取得するために第２の部分結果を結合するステップであって、前記第２の出力は、あたかも前記第１の関数を前記第２の入力メッセージに適用することにより取得されたかのように前記公開鍵およびプライベート鍵の１つを用いて処理することができる合法的な結果であるステップ。
【請求項４８】
前記第１の関数は共有平行移動の特性を有する、請求項４７の方法。
【請求項４９】
前記第１の関数は関連する共有スペースと前記共有スペースにおいて逆数が計算することができる特性を有する、請求項４７の方法。
【請求項５０】
前記第１の関数は関連する共有スペースと共有スペースがシミュレート可能な特性を有する、請求項４７の方法。
【請求項５１】
前記第１の複数の代替関数の各関数は有限フィールドに関するジェネレーターに基づく、請求項４７の方法。
【請求項５２】
前記第１の複数の代替関数の各関数は指数関数である、請求項４７の方法。
【請求項５３】
複数の代替関数の各関数が環に関して定義される、請求項４７の方法。
【請求項５４】
複数の代替関数の各関数がグループに関して定義される、請求項４７の方法。
【請求項５５】
複数の代替関数の各関数が整数のサブセットに関して定義される、請求項４７の方法。
【請求項５６】
前記第１の関数は鍵を有する暗号関数であり；
前記第１の関数は、鍵の逆数が公に知られた情報を用いて実施可能に計算することができない特性を有する、請求項４７の方法。
【請求項５７】
前記暗号サービスはデジタル署名サービスである、請求項４７の方法。
【請求項５８】
前記暗号(cryptographic)サービスは暗号化(encryption)サービスである、請求項４７の方法。
【請求項５９】
前記暗号サービスは復号サービスである、請求項４７の方法。
【請求項６０】
前記暗号サービスは認証サービスである、請求項４７の方法。
【請求項６１】
前記第２の複数の代替関数を発生するステップは、前記第１の複数の代替関数のすくなくともいくつかを前記第２の複数の代替関数として再表現するステップを含む、請求項４７の方法。
【請求項６２】
前記第２の複数の代替関数を発生するステップは、前記暗号処理装置のセットが前記第１の複数の代替関数を適用できなくするステップを含む、請求項４７の方法。
【請求項６３】
前記第１の関数を第１の複数の代替関数として再表現するステップは、前記第１の関数をｔ−ｏｆ−ｌシステムの形式に再表現するステップを含み、ｌは部分結果を供給するように構成された暗号処理装置の数であり、ｔは最終結果を発生するのに必要な部分結果の最小数である、請求項４７の方法。
【請求項６４】
数ｌは数ｔより大きい、請求項６３の方法。
【請求項６５】
前記第１の関数を再表現する第２の複数の代替関数を発生するステップは、ｔ’−ｏｆ−ｌ’システムとして前記第１の関数の再表現を発生するステップを含み、ｌ’は部分結果を供給するように構成された多数の暗号処理装置であり、ｔ’は、前記第１の関数を入力メッセージに適用することにより得られたであろう部分結果の最小数である、請求項６３の方法。
【請求項６６】
数ｌ’は数ｔ’より大きい、請求項６５の方法。
【請求項６７】
数ｔ’は数ｔと等しくない、請求項６５の方法。
【請求項６８】
数ｌ’は数ｌと等しくない、請求項６５の方法。
【請求項６９】
前記第１の関数を再表現する第２の複数の代替関数を発生するステップは、
前記第１の複数の代替関数の少なくともいくつかをｔ’−ｏｆ−ｔ’システムの形式に再表現するステップと、前記ｔ’−ｏｆ−ｔ’システムを前記第２の複数の代替関数に再表現するステップとを含む、請求項４７の方法。
【請求項７０】
前記第１の複数の代替関数の少なくともいくつかをｔ’−ｏｆ−ｔ’システムの形式に再表現するステップは、
（１）暗号処理装置のサブセット番号、ｔ’を選択するステップと、（２）単独でまたは協力して動作するｔ’暗礁処理装置のいずれかが、別のｔ’暗号処理装置がプロトコルに違反して動作しているかどうかを検出することができるように、前記プロトコルを用いたｔ’の暗号処理装置のサブセット番号ｔ’の中で情報を通信するステップとを含む、請求項６９の方法。
【請求項７１】
前記複数の装置の任意の少数は任意に誤動作するかもしれない、請求項４７の方法。
【発明の詳細な説明】
発明の分野
この発明は電子暗号作成システム及び方法に関する。特に、この発明は、通信またはデータ処理ネットワークにおける複数のサーバ間で暗号サービス（例えば電子ドキュメント署名）を配布するためのシステム及び方法に関する。
発明の背景
署名および暗号化／復号のような配布された暗号作成操作におけるある試みが知られている。しかしながら、少数の分散サーバが共謀して停止し、不正を働き、システムの秘密情報を突破するのを助けようとするのに反してその安全性を維持するシステムにおける高レベルの安全性および利用性と結合された操作の有効性を享受するシステムは従来にはない。しきい値暗号作成および移動性の敵の種々の問題に対処する種々の試みが成されてきたが、予防関数分散について論じたものはわずかに過ぎない。
「予防公開鍵」という観念はA. Herzberg, S. Jarecki, H. Krawczyk，及びM. Yung著「予防秘密情報分散」あるいは「絶え間ない漏洩にどのように対処するか、暗号学の進歩」−暗号９５議事録、コンピューサイエンスの講義ノート、９６３巻、D. Coppersmith ed., Springer-Verlag, 1995, pp. 339-352(“［HJKY］”)。に言及されている。この実現方法は、素体における累乗法を有した「離散対数」に基づいていた（すなわち、素数ｐを法として合同である元が与えられれば、ｑがｐ−１を割るＧＦ（ｑ）という生成元を用いる）。この問題は鍵群に対して配布された計算を包含し、この場合の鍵群は、代数構造が公開（公知の位数の群）である定義域から採られる。
暗号作成方式を予防するための他の多くの理論文献にはR. Ostrovsky及びM. Yung著「モバイルウイルス攻撃に耐える方法、分散コンピューティングにおける原理についての第１０回ＡＣＭシンポジウムの議事録」１９９１年、５１−６１頁([OY]”)、R. Cannetti及びA. Herzberg著「一過性の欠陥がある場合のセキュリティの維持について」暗号学の進歩、暗号９４’の議事録(“[CH]”)、A. Herzberg, M. Jakobsson, S. Jarecki, H. KrawczyおよびM. Yung著「予備公開鍵および署名システム」コンピュータおよび通信のセキュリティにおける第４回ＡＣＭシンポジウム(“[HJJKY]”)、Y. Frankel, P. Gemmel, P. MacKenzie及びM. Yung著「予防ＲＳＡ」、Tech Report Version SAND96-0856, Sandia National Laboratories，１９９６年３月(”[FGMY]”)を含む。上述した各文献および下記に示す他の全ての文献を参照することによりそのすべてを本明細書に組込む。
発明の要約
この発明は、高レベルのサービスの利用性、高効率な動作、および高レベルのセキュリティと組み合わされた配布された暗号作成関数の一般的な実現方法を提供する。この発明は、デジタル署名、暗号、エスクロウ、認可等のような種々の非対称鍵暗号作成関数に適用可能である。
この発明の目的は配布される、欠陥のある配布されたコンポーネントの耐性に最適な暗号作成システムおよびサービスを提供することである。
この発明の他の目的はシステムが利用可能であり、ある期間内に過半数のサーバが正しく動作するように複数のサーバを採用する非対象鍵暗号作成システムおよびサービスを提供することである。
この発明の他の目的は、暗号作成関数を配布するためのプロトコル群を持つ非対称鍵暗号作成システムおよびサービスを提供することである。
この発明の他の目的は、鍵の分散を更新し復元することのできる非対称鍵暗号作成システムおよびサービスを提供することである。
この発明の他の目的は最適な復元力を有する非対称鍵暗号作成システムおよびサービスを提供することである。
この発明の他の目的は堅固な暗号系を提供することである。
これらの目的および他の目的は基本暗号作成関数の周期的再表現を含む配布された暗号作成システムおよびサービスを提供することである。再表現は基本暗号作成関数とは異なる関数の集まりに対して適用可能である。再表現は「分散の分散」法（例えば「多から和」あるいは「和から多」）を利用する。これらの方法は事前対策を可能にしt-out-of-1からt-out-of-tあるいはその逆にしきい値パラメータを変更可能である。これらの方法はさらにシステム管理ツールとしてｔと１を動的に変更する。この発明のさらなる観点によれば、プロトコルをチェックして分散暗号作成システムの個々のサーバを監視し、それによりシステムを堅固にする。
この発明の技術は、１）関数が分散変換（すなわちfk1(m)*fk2(m)=fk1・k2(m)の性質を有する場合、２）分散空間における逆元を計算できる場合、３）分散空間がシミュレーション可能な場合（すなわち鍵空間における選択と区別可能なシミュレート可能な空間におけるランダム元を選択可能な場合）、暗号作成関数を実装するシステムに適用可能である。
【図面の簡単な説明】
図１はネットワーク環境に利用可能な分散暗号作成関数あるいは関数群を有し、この発明を具現化するのに適したネットワーク環境を示す図である。
図２は暗号作成サービスのための配布されたシステムへの要求ノードによる例示要求を示す図である。
図３は暗号作成サービスを行う例示の配布されたシステムを示す図である。
図４はこの発明を具現化する配布されたシステム内の一般的な通信を示す図である。
図５はこの発明を具現化する配布されたシステムの動作の一般的なフェーズを示す図である。
図６は通信サーバのシステムを示す図である。
図７はＲＳＡ関数の再表現を示す図である。
図８は堅固な暗号作成システムのチェックプロトコルを示す図である。
図９は非委託エンティティを考慮した保護の追加層を提供する構成を示す図である。
図１０は配布されたシステムにおけるリシャッフルを示す図である。
図１１はユーザ数やしきい値が変化する配布されたシステムを示す図である。
図１２は一般化した準同形の関数の共有の概念を示す図である。
好適な実施の形態の記載
一般には、しきい値暗号作成、特に公開鍵関数のための関数分散は、秘密情報が分散され、あるしきい値の分散保持者からのみ復元可能である秘密情報分散の精神を有する。関数分散は、妥当な独立変数ｍに対して少なくともあるしきい値のt out of the 1サーバの集合がｆｋ（ｍ）を計算できるように、１サーバ群にｆｋ（・）を配布することにより鍵付き暗号作成関数ｆｋ（・）の利用を提供する。これは関数評価（代表的には署名あるいは復号関数）の有用性を増大させる。セキュリティのために、（１）しきい値より少ないサーバを制御し、（２）すべての公開メッセージを聞くことのできる敵は、（同じ機能を有した集中関数ｆｋ（・）を攻撃する敵に比べて）目的のメッセージｍ’に対してｆｋ（ｍ’）を計算する計算上の利点が無い。従って、攻撃者は関数分散保持者のしきい値ｔ以上のメモリを破壊することを強いられるため、その関数は「空間拡散」により保護される。
「復元力」はある期間に許される危険にさらされた、不正を働くサーバの数を記載する属性であり、これは本明細書においてｔと呼ばれるパラメータである。最適ｔ（「最適復元力」）はサーバの合計数が
0004312835.tif 000002
であることを意味する。このｔに対して、多数の任意の不正を働くサーバが（静止している敵に対しても）その計算を「制御」できる。
（移動する敵に対する）「予防セキュリティ」という概念は、配布可能な（すなわち「空間拡散」により保護可能な）寿命の長い暗号作成鍵のメモリの保護を強化する。予防セキュリティは同様に「時間拡散」によりさらに保護される。すなわち、上述したようにしきい値暗号作成（関数分散）を介して配布された関数が与えられると、配布された関数は配布されたサーバのメモリの内容を周期的にリフレッシュする。このリフレッシュ動作は、グローバル鍵を保存する態様の、ローカルサーバの値の「ｔのような再ランダム化」であるがt out of the 1サーバより少ない集合の従前の内容を「無効」にする。これは許されたｔより少ない危険にさらされたサーバから、過去に得られた移動体敵（例えば、ハッカー、ウイルス、悪徳アドミニストレータ等）の知識を無効にさせ、システムに自己保全の性質を与える。
暗号作成関数のための予防システムは、サイズｔのサーバの集合に基本的な関数を計算可能にすることにより関数分散の有用性を継承し、それにより欠陥のあるサーバの小さな集合が有用性が中断されることを防止する。予防システムはさらに堅固な技術を用いて、システムの有用性を能動的に攻撃している悪意のあるサーバを許容する（検出あるいは訂正する）ことによりしきい値の暗号作成システムの有用性を強化することができる。さらに、予防セキュリティは、さらに敵あるいは悪意でない故障により従前に改悪されたサーバのメモリを復元するので、堅固性を強調する。これはシステムに自己治癒の性質を与える。
この結果、システムは、特定の期間に、ｔ−１サーバまでしか制御できないという制限を有して、時がたつにつれてサーバ間で潜在的に移動可能な「移動性の敵」を許容することができる。敵はいつかは（上述した制限の下で）システム全体に訪問することも可能である。しかしながら、システムは敵によるメモリの消去および改ざんから自己治癒し、敵の行為に対して自己保全する。これは（単調に改悪する）静止敵よりさらに強力な敵である。
図１はネットワーク環境に利用可能な暗号作成サービス関数あるいは関数群を有し、この発明を具現化するのに適したネットワーク環境を示す図である。ネットワーク１０１は通信路１０５により相互接続された多数のノード１０３を含む。配布されたシステム１０７はさらに通信路１０９を介してネットワーク１０１と接続する。ノード１０３と接続路１０９については多くの構成が適していると理解されたい。
図２は暗号作成サービスのために要求ノード１１１により配布されたシステム１０７に成された例示要求を示す図である。図示するように、単一の要求ノード１１１は入力通信１１３を配布されたシステム１０７に供給する。配布されたシステム１０７は暗号作成サービスを実行し、出力通信１１５を返す。要求と結果の返信の呈示の方法について多くの変形例が適用可能であると理解されたい。例えば、単一の要求ノード１１１が完全な要求を単一の入力通信１１３に呈示する必要はない。あるいは出力を単一の出力通信１１５で要求ノード１１１に返す必要はない。多くのプロトコルが適用可能であり、要求ノード１１１の個人情報の配布されたシステム１０７による検証、そのサービスの支払いのための確認等のような種々の管理上の相互作用を含むことができる。
図３は暗号作成サービスを実行するための例示の配布されたシステムを示す図である。多数のエージェント１２１の各々は分散された態様で暗号作成サービスを実行することに参加する。図面を簡単にするために、すべてのエージェントには同じ参照番号が付されているが、各々は以下にさらに詳しく述べるように暗号作成サービスを供給する間に異なる機能を実行することができる。入力プロセッサ１２３は要求元ネットワークエンティティ（図示せず）から入力通信１１３を受け取りすべてのエージェント１２１に特定の暗号作成サービス要求に関する情報を供給する。出力プロセッサ１２５は各エージェント１２１から部分結果情報を受け取り結合し、出力通信１１５を要求元ネットワークエンティティ（図示せず）に供給する。入力プロセッサ１２３および出力プロセッサ１２５はネットワーク（図示せず）およびエージェント１２１との間でいわゆる「ファイアウォール」としてセキュリティレイヤを供給しさらにアドミニストレータタスクを引き受けることができる。
多くの暗号作成サービスは非対称暗号作成鍵を入力情報に印加することを含む。例えば、暗号作成サービスが電子文書のデジタル署名であるならば、配布されたシステムは全体としての配布されたシステムに代わってそのドキュメントのための単一の署名を生成する。公開鍵暗号作成システムでは、そのような署名は秘密の署名鍵をメッセージに印加することに相当する。署名の受取人はその署名を、秘密の署名鍵に対応する公開検証鍵を用いて検証することができる。配布されたシステム１０７では、秘密の署名鍵は１つのロケーションに１つの鍵として存在しない。そのかわり、鍵配布者（ディーラーと呼ばれる場合もある）１２７は各エージェント１２１に鍵の分散を分配する。各エージェント１２１は個々の鍵分散を入力に印加し、複数エージェント１２１の集合動作により、単一の公開検証鍵により検証可能な単一の署名を生成する。しかしながら、１つのエージェントはその署名自体を生成するのに十分な情報を所有しない。各エージェントは鍵の分散を保持するので、エージェントはまた「分散保持者」と呼ぶこともできる。
図３の図示のために、両端に矢印を有した太線はすべてのエージェントへの複数の通信路を示す。矢印を持たない細線はエージェント間の個々の通信線を示す。各エージェント１２１は各他のエージェント１２１、鍵配送者１２７、入力プロセッサ１２３、および出力プロセッサ１２５と通信することができる。エージェント１２１は、入力プロセッサ１２３及び出力プロセッサ１２５を介して以外は、ネットワーク（図示せず）にアクセスできないことが望ましい。
この発明の方法は、種々の代替可能な構成により実施できることが理解される。例えば、単一のコンピュータサーバは入力プロセッサ１２３としてもまた出力プロセッサ１２５としても機能することができる。また、（好適ではないが）１台以上のエージェント１２１が入力プロセッサ、出力プロセッサあるいはその両方として動作することが可能である。また、（好適ではないが）独立した鍵配送者１２７に依存するよりも、エージェントの１台が鍵配送機能を実行することもできる。あるいは、エージェントは配送態様で鍵分散を発生することができる。この場合、鍵配送者１２７あるいは１以上のエージェント１２１がその鍵配送プロセスのための管理上の調停者として動作することができる。
以下に詳細に述べるように、配布されたシステム１０７は全エージェントよりも少ない数のエージェント１２１を用いて暗号作成サービスを供給することができる。図４は３台のエージェント１３１、１３３、１３５が前記サービスの提供に関与する場合の配布されたシステム１０７内の包括的な通信を示す図である。他の２つのエージェント１３２、１３４は出力の生成には積極的には参加しない。この図において、入力プロセッサ１２３はメッセージＭを５台のエージェント１３１、１３２、１３３、１３４、１３５に供給する。５台のうちの２台のエージェント１３２、１３４は、入力プロセッサ１２３からの指示により、あるいは他の何らかの通知手段により動作しない。例えば、特定のエージェントがそのサービスに関与することを、メッセージ自体が知らせることも出来るしあるいはヘッダに関連付けることもできる。使用するプロトコルに応じて、全プロセッサが動作することができるが、そのうちの一部を用いて最終計算が行われる。３台の稼働中のエージェント１３１、１３３、１３５の各々はそれぞれの鍵分散を用いて部分結果１３７を生成する。出力プロセッサ１２５は部分結果１３７を受け取り、それらを結合して出力Ｆｋ（Ｍ）を生成する。次に、この出力は（図示しない）ネットワークの要求元ノードに通信される。
図５は配布されたシステムの一般的なフェーズの動作を示す。セットアップフェーズ１４１において、鍵配送者は鍵分散を配布されたシステムのエージェントに配送する。関数印加フェーズ１４３では、エージェントは各鍵の分散を入力に印加し、部分結果を出力プロセッサに供給する。更新フェーズ１４５では、配布されたシステムのメンバが周期的に種々の行動をとりシステムのセキュリティを維持し受動的な故障及び／又はシステムを破壊する積極的な試みから復元する。更新フェーズ１４５の後、配布されたシステムのメンバは関数印加フェーズ１４３の暗号作成サービスの供給に戻る。
多と和
一部のユーザあるいは定足数のユーザがそれぞれの分散を用いて部分結果を得、結合され計算されて最終結果を得ることができるように、秘密あるいは関数は数式の体系を介して分散可能である。所定の入力についての最終結果は上記分散により再表現される関数の最終結果に等しい。以下の記述は配布された分散として再表現される関数の１表現（これは多項式上の項目（「ｐｏｌｙ（多）」により分散すると呼ぶ）に集中する。超平面を有した有限幾何学の使用のような他の手法も可能である。
すべての分散を必要とし、すべての分散を用いて部分結果を得、結合するように秘密あるいは関数を分散可能である。加算を介して結合することに集中し、それゆえこの共有を「ｓｕｍ（和）」による共有と呼ぶ。
安全、堅固なしきい値ＲＳＡ
以下に記載するものは上述した配布されたシステムであって、セキュリティがわかってないシステムに使用するのに適したしきい値ＲＳＡ方式である。このしきい値方式は静止した状態（移動しない）敵モデルにおけるＲＳＡと同じセキュリティのＲＳＡしきい値方式に変更される。この例の基本的着想は逆元計算が容易なShamirしきい値方式を使用することである。
ＲＳＡは公開鍵（ｅ，ｎ）および私有鍵ｄを有したディーラにより生成される。Ｈ＝ｇｃｄ（ｅ，Ｌ）とし、拡張されたユークリッドの互除法を用いて、
0004312835.tif 000003
のようなP, s’を計算する。ｄ≡Ｐ＋ＬＫ’ｍｏｄθ（ｎ）であり、但しｋ’≡ｄｓ’Ｈ−１ｍｏｄθ（ｎ）である。これは、ｅを逆にしなければならないためＨ−１が存在するので計算可能である。{0,L...,L3tC}の係数を有した位数ｔ−１のランダム多項式ｒ（ｘ）（但しｃはｐｏｌｙ（ｎ））はｒ（ｌ＋１）＝Ｌ＊Ｋ’∈Ｚであるように選択される。（係数のうちのｔ係数は予防方式に使用され予防化なしに静的しきい値ＲＳＡに対して１に設定可能である。Ｐ（すなわち各分散保持者の一部）を公開にする（すなわち、各分散保持者のキーの一部にする）。次に公開の補間ポイントｘｉ＝ｉを有したシャドウ保持者ｉは秘密裏にシャドウｓｉ＝ｒ（ｘｉ）∈Ｚを受け取る。分散はＬの倍数である。今、Λ（｜Λ｜＝ｔを分散保持者部分集合とし、以下の式に注目する。
0004312835.tif 000004
Ｌはｓｉを除算し
0004312835.tif 000005
はＬの倍数であり、上記和の項は（その群の逆元なしに）ｓｉからの整数について効率的に計算可能である。それゆえ、メッセージｍの署名を生成するために、各i∈Λは部分結果
0004312835.tif 000006
を計算し、結合関数はｍｐ  ｍｏｄ  ｎを計算し、そして最終結果
0004312835.tif 000007
を計算する。上述した方式はＹの系に類似た算術態様である。DesmedおよびY. Frankel著「認証コードと署名の分散生成」、暗号学の進歩――Crypto 89議事録、コンピュータサイエンスの講義ノート、巻４３５、G. Brassard et., Springer Verlag, 1989, pp. 307-315（″[DF91]″）（これは強い素数のために設計された）。この類似は秘密のロケーションとしてＯよりはむしろ補間ポイントｌ＋１を用いてｓｉ／Ｌとして分散を配布し、それゆえわずかに異なる
0004312835.tif 000008
を選択することによる。
分散の分散（多から和）
次にt-out-of t分散(多から和)プロトコルについて述べる。これは、t-out-of-1多項式ベースの分散方式をt-out-of-tの加算における分散方式に変換するｔサーバ間のプロトコルである。これは和によるt-out-of-t分散を別の和によるt-out-of-t分散に変換する［ＦＧＭＹ］の方式に拡張する。この多から和へのプロトコルは、上記（すなわち「ＤＦ９１」）を「安全なしきい値ＲＳＡ方式」のタイトルが付けられた章で後述する安全システムに変換する現在の状態の乱数化を供給する。この乱数化はまた特に「堅固なしきい値ＲＳＡ方式」のタイトルが付けられた章の堅固性を可能にするように設計される。
図６は秘密のＲＳＡ鍵構成の3 out of 5共有のための多から和を実行する通信サーバ４０１、４０３、４０５、４０７、４０９のシステムを示す。秘密のＲＳＡ鍵は例えば［ＤＦ９１］のように、サーバ４０１が分散ｓ１を有し、サーバ４０３が分散ｓ２を有し、サーバ４０５が分散ｓ３を有し、サーバ４０７が分散ｓ４を有し、およびサーバ４０９が分散ｓ５を有する分散への多項式の手法を用いて配布される。多から和へのプロトコルはいずれか３台のサーバが3 out of 1システムのための各分散を3 out of 3システムに変換可能にする。多から和へのプロトコルが実行された後、時がたつにつれ表示されるように、分散ｓ１を有するサーバ４０１は分散ｓ１’を得、分散ｓ３を有するサーバ４０５は分散ｓ３’を得、分散ｓ４を有するサーバ４０７は分散ｓ４’を得る。新しい分散ｓ１’、ｓ３’、ｓ４’は3 out of 3再構成におけるサーバ間の配布されたプロトコルから得られる。図６の矢印は古い分散に対する新しい分散の関係を示す。例えば、サーバ４０１は、図６に示すように結果がｓ１、ｓ３、およびｓ４の関係を有するプロトコルにより分散ｓ１’を得る。
図７はＲＳＡ関数の再表現を示す。サーバ３０１、３０３、３０５を有する3 out of 3システム構成は多から和へのプロトコルが実行された後に実行可能な加算における3 out of 3分散を示す。すなわち、鍵をかけられたＲＳＡ関数３０９はサーバ３０７と一緒に動作する３０１、３０３、３０５が３０９の場合のように鍵をかけられたＲＳＡの同じ関数評価を計算することができるプロトコルに再表現される。ｄ１＋ｄ２＋ｄ３≡ｄｍｏｄθ（ｎ）とし、サーバ３０１が分散ｄ１を有し、サーバ３０３が分散ｄ２を有し、サーバ３０５が分散ｄ３を有するものとする。上述したように、各サーバ３０１、３０３、３０５は各分散、入力Ｍおよび３０７と動作するときの公開合成関数ｎを用いてＭｄ  ｍｏｄ  ｎを計算することができる。サーバ３０７がサーバ３０１、３０３及び／又は３０５になることは可能である。
サーバ４０１、４０５、４０７（図６）をサーバ３０１、３０３、３０５（図７）に関連づけるために、多から和へのプロトコルの後、サーバ４０１をサーバ３０１として、サーバ４０５をサーバ３０３として、およびサーバ４０７をサーバ３０１として構成することが可能である。さらに、図７において、分散ｓ１’はｄ１と交換され、分散ｓ２’はｄ２により交換され、分散ｓ３’はｄ３により交換される。システムの実装は以下のように行うことができる。
セットアップ：分散の配布中にディーラは最大位数の要素
0004312835.tif 000009
を発行し、
すべてのｉに対して
0004312835.tif 000010
を発行する。Λ（但し｜Λ｜＝ｔ）を分散プロトコルの分散に関与する分散保持者（サーバ）とする。サーバはリーダサーバｉ’を選択する。
分散の分散：サーバｉ：
・j∈Λ＼{i}に対する
0004312835.tif 000011
を生成する。
・自己により保持される分散を
0004312835.tif 000012
に設定する。
・確率的暗号化（これもメッセージに委託する行為）を用いた公開チャンネルを介して
0004312835.tif 000013
をサーバｊにプライベートに送信する。
0004312835.tif 000014
を発行する。
分散の検証と生成：
0004312835.tif 000015
をｊがｉから秘密に受信した委託値にする。これは、正しい委託値を受け取り、分散が正しいサイズであり、種々の委託値間の代数学の関係が相互作用の正当性を示していることを検証する。
１．各サーバｊはすべてのi∈Λ＼{j}に対して検証する。
0004312835.tif 000016
検証が通らない場合には、サーバｉは除去されあたらしいΛが選択される。
0004312835.tif 000017
検証がｊにより論争されるなら、ri,j,0とr’i,j,0が明らかにされ（委託中止）、ｉまたはｊのいずれかが適切に除去される。プロトコルは停止される。
ri,j,0の大きさの最初の検証を用いて、分散保持者が効率よく計算できないような非常に大きな値を敵が送る攻撃を防止する。ri,j,0を送信するパケット（フィールド）のサイズが固定のサイズであって十分大きなサイズであるような異なる技術を用いることができる。
２．すべての検証が通るなら、Ｌがs’jおよび
0004312835.tif 000018
であるようにシャドウ保持者のｊ∈Λ新しいシャドウが
0004312835.tif 000019
である。
３．分散保持者ｊはr”jおよび
0004312835.tif 000020
を発行する。
計算をだめにしようとすると、敵のサーバが強制的に除去される。
0004312835.tif 000021
サーバの環境下でプロトコルが使用する場合には、集合Λはｔの分散保持者という新しい集合に訂正することができ、開始時から分散保持者の集合を作り直すことができる。
注意：上述したステップ２において分散を分割することはこの時点で必要ないが以下に述べる予防の拡張において使用される。
安全しきい値ＲＳＡ方式
ここに述べるのは安全しきい値ＲＳＡプロトコルである。「ヒューリスティックなしきい値ＲＳＡ方式」のタイトルが付されたセクションで上述したように、静的な敵モデルにおけるヒューリスティックなＲＳＡしきい値暗号作成システムの安全性をどのように証明するかは知られていない。問題は、署名者の部分集合がメッセージごとに変わる――これはその安全性をヒューリスティックなもののみする――ときの安全性を証明することである。恐らく安全なプロトコルを得るためには、その手法は、上述した多から和への技術を用いたｔの分散保持者の現在の集合の署名分散を動的に変更することである。次に、この署名は和の分散を用いて行われる。「動的に変換する」とはここでは、ｔの分散保持者のいずれかの新しい集合が署名の前に上述した多から和へのプロトコル通過しなければならないことを意味する。これは、敵に利用可能な部分的視野をランダムかつ独立したものにし、敵の視野をシミュレート可能にする。その視野をシミュレートできることを実証することにより、以下のようにセキュリティの証拠を与えることができる。
ステップ０（セットアップ）：「ヒューリスティックしきい値ＲＳＡ方式」のタイトルが付されたセクションの分散分配プロトコルが実行され、各サーバ毎の暗号化鍵が配送される。ディーラはセットアップ中に最大位数の要素
0004312835.tif 000022
（但しθ（ｎ）に対する相対素数の場合ｇ１＝ｇｍ）（要素は各サーバの鍵の一部であり得る）。同様に、すべてのｉに対する
0004312835.tif 000023
が公開される。
ステップ１（多から和）：論争なしに多から和へのプロトコルを成功裏に完了させるｔサーバの集合が見つかるまで「分散の分散（多から和）」（「多から和」）の上記タイトルが付けられたセクションの多から和への（分散の分散の）プロトコルを実行する。Λをそのプロトコルを成功裏に完了したｔサーバとする。
ステップ２（署名）：各入力メッセージｍに署名するために、Λの各サーバは部分結果
0004312835.tif 000024
をブロードキャストする。（但しS’iは「多」から「和」である）。
0004312835.tif 000025
（但し
0004312835.tif 000026
であり、これは公的に利用可能な結合関数により計算可能である。Λの分散保持者は、多から和への変換を再び行うことなく多から和へのプロトコルで得たＳ’分散を用いて所望の数のメッセージに署名することができる。実行の最適化としてサーバはそのキャッシュ多項式的に異なるΛに対して多くの分散を維持することができる。
復元力のある配布された暗号作成関数サーバにおける堅固性を補償するためのチェックプロトコルの採用
配布された暗号作成サービスにおいて、部分結果の完全性を保証したいと望かもしれない。この目的のために、前記装置は装置と出力プロセス間のチェックプロトコルに従事することができる。このプロトコルの結果として、出力プロセスはどの部分結果が正当であり、その結果を破棄すべきかを判断することができる。すなわち、エラー検出及び消去プロセスを実行する。残りの正当な部分結果を与えられると、出力プロセスは最終結果を結合し計算することができる。
エラー検出および消去の他の例として、出力プロセスは、正しいデータ及び正しくないデータを用いて計算するエラー訂正手続きを適用することができるが、定足数の正しい部分結果がある限り、最終結果は正しい。これは、いくつかのコンポーネントが故障しているかも知れない（ハードウエアまたはソフトウエアの故障）システムにおいてさえも堅固性が維持されることを保証する。入力プロセス及び出力プロセスは、コンポーネントが故障しているかも知れない環境において高可用性システムにおいて複製される必要がある。
図８は堅固な暗号作成システムのためのチェックプロトコルを示す。3 out of 3構成データで示したように、結合関数４２７と結合された３台のサーバ４２１、４２３、４２５がプロトコルを実行している（結合関数４２７は４２１、４２３、４２５のような他のサーバ及び又は他のサーバ群において分散可能である）。４２１の部分結果のための検証プロトコルは４２９で示すように４２３、４２５、及び４２７と関係する相互作用４２１を介して実行される。ＲＳＡ方式の例示的検証を以下に述べる。
堅固なしきい値ＲＳＡ方式
「安全なしきい値ＲＳＡ方式」のタイトルが付されたセクションにおいて上述した方式は安全であるが堅固でない。サイズｔの部分集合は署名中における不正行為を行う関与者を含んでいるかもしれず、新しい部分集合を考慮しなければならなに。堅固性は分散保持者の計算に対する効率的な検証を与える。安全なしきい値ＲＳＡプロトコルは以下に述べるように堅固にすることができる。
セットアップ：検証者を、分散保持者の出力からｍd  ｍｏｄ  ｎを得るための効率的な結合関数を計算するエンティティとするＳｉ’を「分散の分散（多から和）」のタイトルが付けられた上述の分散の分散プロトコルから発生されたサーバｉ’の分散とする。さらに証人
0004312835.tif 000027
を「分散の分散（多から和）」において提供された公開情報を用いて生成させる。
部分結果を検証する：Y. Frankel, P. Gemmel及びM. Yung著「証人ベース暗号作成プログラムチェック及び堅固関数分散」、計算の理論についての第２８回年次シンポジウムの議事録、ＡＣＭ、１９９６、ｐｐ．４９９−５０８（”［ＦＧＹ］”）に記載された技術を使用することができる。あるいはさらに安全な素数ＲＳＡのために、R. Genaro, s.Jarecki, H.Krawczyk, T. Rabin著「堅固なしきい値ＲＳＡ、暗号学の進歩--Crypto 96議事録、「コンピュータサイエンスの講義ノート」、Vol. 1109, N. Loblitz et, Spring-verlag, 1996, pp. 157-172,(“[GJKR2]”)に記載された技術を使用することができる。公知のランダムエレメント（部分群のジェネレータ）ｇｉ及びランダムエレメント（「証人」と呼ばれる）に印加された分散保持者の関数の結果がある。提示を簡単にするために、最大位数のそのようなジェネレータｇを呈することができる。（あるいは、個別に累乗され、次にメッセージと乗算されてチェッカデータを作る多数のランダムジェネレータを用いることができる。
プロトコルは以下のようになる。
１．検証者はシャドウ保持者ｉに以下を与える：
メッセージｍおよびｑ０、ｑ１∈Ｒ｛０、…ｎ−１｝に対してチェッカ
0004312835.tif 000028
２．検証者は（例えば［ＦＧＹ］の２ラウンドプロトコルにおいて）エレメントｑ０、ｑ１を知っていることを証明する。
３．分散保持者は部分結果
0004312835.tif 000029
を返す。
４．S’m,j,Λ, H’を検証者に受信させる。次に検証者は以下を検証する。
0004312835.tif 000030
テストに失敗するとエラーが検出される。
結合されたプロトコルである実装は発行された証人により配布された分散のイニシャルセットアップから成る。上述の「部分結果の検証」と共に実行中の上述の「安全なしきい値ＲＳＡプロトコル」のタイトルが付されたセクションのプロトコルは「堅固なしきい値ＲＳＡ」であり、これは
（１）最適−復元力であり及び（２）その秘密のサイズの位数の小さな永久的分散サイズを有する。
復元力分散暗号作成関数サーバ内のユニット完全性関数の採用
高度の復元力を有する分散暗号作成サービスのアプリケーションは異なる組織により１つの鍵を分散することである。この場合各組織は鍵分散を保持する。各組織は異なる国又は異なるビジネスエンティティであってもよく、これはその装置を相互に疑わせる。
図９は信用していないエンティティを考慮したさらなる保護層を供給する分散保持者のための構成を示す。アイテム４５１は組織としての分散保持者を示し、アイテム４５３及び４５５は組織４５１により使用される機器装置を示す。いくぶんかの不信は例えばその秘密分散保持／計算装置４５５を構築し及び／または署名したソースがエンティティ４５１でないときである。それゆえ、ユーザ４５５の構築者／署名者及びユーザ組織４５１との間に相互の不信がある。
この場合、各分散保持者の組織４５１はその分散を装置４５５に委託するとともに、そのタスクが装置４５３の完全性を保証する第２の装置４５３にも依存する。この装置−完全性装置４５３は計算装置４５５と共に作動して、例えば（１）計算装置４５５に計算のための乱数ビットを供給し、（２）結果の堅固性と正当性を保証するために「対話型チェックプロトコル」に従事し、および（３）計算装置からネットワーク４５７に情報が漏れるのを防止する。完全性装置４５３は、正当な出力が装置４５５により呈示されただけでなく、潜在意識下のチャンネル、タイミングチャンネルあるいは秘密のチャンネルが無いことを保証する。他の保護方式をポリシーにより定義されるファイアウォールにより実施することができる。これは、各装置に対してファイアウォール保護を与える。
小分散堅固しきい値ＲＳＡ
上記方式が大きな分散を持つ理由の一部は予防化を可能にするために特定のフォーマットの分散を持つ必要があるからである。予防化が必要ない場合、分散がＲＳＡ鍵の位数の安全なしきい値ＲＳＡ方式が存在する。永久分散が小さな定数と秘密のサイズとの乗算のみの場合、「サイズ効率のよい安全ＲＳＡ関数分散」が存在する。
これを実現するために、ｒ（ｘ）を「ヒューリスティックなしきい値ＲＳＡ方式」のタイトルが付されたセクションのようにする。分配分散をsi≡(r(i)/L)modθ(n)とする。これは、Ｌが整数でｒ（ｉ）を分割するので可能である。多から和プロトコルの後保持された分散のためには、
0004312835.tif 000031
を記憶し、
0004312835.tif 000032
をサーバが公的に利用可能にさせるだけでよい。
すべての累乗は最初にSi’と計算され、次に
0004312835.tif 000033
により累乗される。ユーザはさらにプライベートな計算のために復号鍵を所有しなければならないことに注意する。
安全予防ＲＳＡ
移動する敵に対して保護するために、分散保持者は自分の分散をリシャッフル（再ランダム化）する。
ある時刻に敵がサーバのメモリにアクセスし，後で敵がサーバから除去された場合には、その過去の情報は更新期間後敵にとって役に立たなくなる。図１０は配布されたシステムにおけるリシャッフルを示す。５台のサーバ３６１、３６３、３６５、３６７及び３６９のシステムは分散Si,jを有し、この分散は期間が変化するにつれ変化する。例えば、サーバ３６１は期間１において、分散S1,jを有し、期間２にはS1,2を、および期間３にはS1,3を有する。結合関数はこの期間影響されないが、ある１つの期間内およびいくつかの期間で３７１として異なるサーバが機能することは可能である。
ここに述べるのは、この実装の異形において分散がリフレッシュされる安全な予防ＲＳＡプロトコルである。
分散配布（セットアップ）：これは「堅固なしきい値ＲＳＡ方式」のセクションにおける堅固なしきい値ＲＳＡのようなセットアップである。ディーラは公開鍵（ｅ，ｎ）および私有鍵ｄを使ってＲＳＡを生成する。次に「ヒューリスティックしきい値ＲＳＡ方式」のタイトルが付されたセクションのようにＬ・Ｋ’の分散Si,0を生成する。ディーラはさらに、最大位数の
0004312835.tif 000034
に対して{g, gd}を発行し、すべてのｉについて値
0004312835.tif 000035
を発行する（さらに多くのジェネレータを使えば、各々にこの値が発行される）。
更新期間：ｕ←ｕ＋１とする。
分散更新及び復元：この意図は時刻ｕ＋１に分散を、時刻ｕで保持された分散に関係無くｔ態様にすることである。分散プロトコルの「多から和」分散が実行され
0004312835.tif 000036
（但しＷはＬを除算する公開値である）というt-out-of-t分散が作られる。これにより分散は加算的に分散され、分散動作の「和から多」の分散が行われる。すなわち、各サーバｉはShamirしきい値方式を使用するすべてのサーバｊによりそのSi’（およびその結果生じる公開値ｗ）を分散する。１分散保持者の各々は、Λにより生成された、ｔシャドウズS,’の各々のすべての多分散を加算する。それゆえ、各シャドウ保持者はＬ・Ｋ’の分散を持つことになる。
このプロトコルはすべてのユーザの分散を更新する。それゆえ、古い分散が存在する（更新）かあるいは存在しないか（復元）は関係ない。これは新しく取引された分散が、署名が実行される方式になるためである。以下の動作が行われる。
１．Λにより定義されたｔシャドウ保持者のある集合が論争が無く、各Si’及び公開ｗを分散することに同意するまで時間ｕ−１ｕ−１ Si,u-1からの分散により分散プロトコルの「多から和」分散（「分散の分散（多から和）」のセクション）を実行する。分散プロトコルの以下の「和から多」分散を実行すると（この目的は、ロケーションｌ＋１の多項式の値としてその値をランダムに再分散することである）。
（ａ）各ｉ∈ΛはSi’を分散する（最も低い番号付けがされたメンバもその分散における公開ｗを分散する。すなわち、最小のｉ∈Λに対してSi’←Si’+W）。この分散は｛０、Ｌ，…，ＬＣ｝（但しｃは「ヒューリスティックしきい値ＲＳＡ方式」のタイトルがつけられたセクションと同様である）における係数を用いて位数ｔ−１のランダム多項式ri”(x)を生成し、そしてＬがすべての分散を分割する分散ri’(l+1)+Si’の多項式である
0004312835.tif 000037
を計算する。
（ｂ）つぎにサーバｉ∈Λはすべての
0004312835.tif 000038
を発行し、プライベートにｊ∈｛1,...,1｝についてwi,j=ri’(j)∈{1,....,1}送信する。
（ｃ）各サーバｊは検証する
・［Ｆ］が（適正な分散）を検証するのと同様
0004312835.tif 000039
・（適正な秘密）を検証：
0004312835.tif 000040
（但し証人
0004312835.tif 000041
は「分散の分散（多から和）」のセクションの公開値から生成される。（但し
0004312835.tif 000042
と乗算しなければならない最低指数を持つサーバを除く）。
・正しいフォーマットを検証する：ＬがWi,jを分割する。
（ｄ）次に論争の解決が実行される。検出した故障および破壊されたシステムコンポーネント（サーバ群）がリブートされ分散更新処理が、論争が無くなるまで最初から続く。
（ｅ）今、
0004312835.tif 000043
である。過去のヒストリーを消去し新しい現在のシャドウSi,uを維持する。
0004312835.tif 000044
の乗算ｍｏｄ  ｎを用いて発行される。
簡単なメモリ「リフレッシュ」手続きにより予防的に維持される（システムサイズ１、鍵Ｐの公開部及びジェネレータのような）共通の「公開」定数：各サーバは各サーバに現在値を送り、多数値が新しい永久値になる。
Wi,jのサイズは、分散保持者が効率よく計算できないような大きさの分散を敵が送る攻撃を予防するのに十分な大きさの固定サイズのパケットを介して送られる。
ＲＳＡ関数アプリケーション：時間をｕとする。堅固性が必要なければ、シャドウSi,wを用いて「安全なしきい値ＲＳＡ方式」のタイトルが付けられたセクションにおける安全なしきい値ＲＳＡとして正確に実行する。さもなれば、「堅固なしきい値ＲＳＡ方式」のタイトルが付けられたセクションにおける安全なしきい値ＲＳＡとして正確に実行する。さもなければ、「堅固なしきい値ＲＳＡ方式」のタイトルが付されたセクションのプロトコルのように検証により計算を行う。
動的管理関数分散
この実施の形態は、他の目的に使用することができる。上述した方法は、t-out-of-1から加算的に分散t-out-of-tに行き、戻る、非常に柔軟性のある変換である。戻るときは、分散しきい値を変換することができると共にサーバ数を増加させ、例えばt’-out-of-1’（もちろｎ、t’<tであれば、更新時にせいぜいt’-1が破壊されると仮定して）のサーバ数を持つことが出来る。同様にして、サーバ台数を減少させることができ、破壊されたサーバ数について類似の仮定が成り立つ。これにより、この柔軟性のある技術の強度が実証される。
システムは、動的管理に対して種々の方法で変更することができる。すなわち、変更無し、ユーザ追加／しきい値同じ、ユーザ追加／しきい値減少、ユーザ追加／しきい値増加、ユーザ削除／しきい値同じ、ユーザ削除／しきい値減少、ユーザ削除／しきい値増加である。図１１はユーザ及びしきい値の数が変更される配布されたシステムを示す。始めにサーバ４０１、４０３、４０５、４０７、及び４０９を有する3 out of 5システムから構成されるシステムにおいて、サーバ４１１を含めるように「ユーザ追加／しきい値増加動的管理」動作が実行される。「ユーザ追加／しきい値増加動的管理」動作の後、システムは4 out of 6システムとなる。又、図１１に示すように、ユーザ削除／しきい値と同じ動的管理システムが実行されると、サーバ４０９が除去され、システムは4 out of 5システムとなる。
注）：好奇心があるのみでサーバのメモリに影響を与えない敵、すなわち破壊的（悪意）でない場合には、ｔサーバが常に利用可能であることが確かなら例えt>n/2でも、より大きな位数ｔの多項式を持つことが出来、敵はある期間に、せいぜいt-1 of themを制御できるに過ぎない。
３．９予防システムの一般化された実施の形態
図１２は一般的な準同形関数の分散を示す。４２１として示される関数Ｆは入力としてメッセージＭ及び秘密鍵ｋを受け取り、次にこれら２つの入力値を与えられて結果Fk(M)を返す。予防システムはサーバ４２３、４２５、４２７、４２９、４３１及び４３３を導入することにより４２１（これは秘密ｋで鍵がかけられる）を再表現する。図示システムは、3 out of 5システムであり、４２３、４２５、４２７、４２９及び４３１から選択されたサーバのいずれかの３台が４３３と協働して分散態様で値Fk(ｍ)を発生することができる。
以下の記述は、ＲＳＡシステムから落とし戸転置と呼ばれる一般化された集合への従前の実施の形態の一般化である。落とし戸転置群はW. Diffie及びM. Hellman著「暗号作成の新しい方法」IEEE Trans. on Information Theory, 22(6), 1976(“[DH]”)により導入され、以下に記載される。
定義１：落とし戸転置群Fhは入力１h（hは安全パラメータ）が与えられると、２つのｈビット列(pu,se)（puは公開鍵でseは秘密鍵）から成るランダムに描画された組を返す（ＷＬＯＧ）多項式時間発生器Ｇから構成される。fse(・)がfpu(・)の逆関数であり、pu(se)が当てられるとfpu(・)(fse(・))の印加が多項式時間であるように、鍵群はサンプル可能なメッセージ空間Dpuに対して転置fpu(・)及びfse(・)を定義する。
秘密鍵seを持たずにランダムに選択された転置のランダム値の逆数を見つけることは困難である。すなわち、すべての予防可能な多項式時間アルゴリズムＡに対して、何らかの多項式poly(・)に対して十分大きなすべてのｈに対して
0004312835.tif 000045
である。
p[x:e1;...,ej]はイベントeiがシーケンシャルに起こった（実行された）後断定されたｘの確立に対する標準的な表記である。
十分条件
以下は  以下は転置の十分条件である。以下の分散返還条件の表記は関数が供給可能であることを保証するための十分な算術的特質を与える。
定義２（分散変換）：秘密鍵をse=kとする。落とし戸（計算し難い）転置fk(・)は、以下の場合に変換可能である。１）ｋ∈kseの場合にアーベルの分散空間群kse(+)が存在する場合、２）f’k=fkであるような多項式時間「マッピング」f:kse x Dpu→Dpuが存在する場合、３）Dpuにおける１以上のランダムに選択されたpoly(h)エレメントに対して定義されない確立が無視できる場合、および４）k1, k2∈およびkseおよびα∈Dpuのいずれかに対してf’k1(α)＊f’k2(α)＝f’k1+k2(α)であるように集合Dpuに対する相関するバイナリ演算”＊”が存在する場合。
落とし戸転置群Fhは「その中のほとんどすべてのエレメントが分散変換可能であれば分散変換可能」である。原始関数を分散する関数におけるすべての演算がセキュリティパラメータの多項式時間に計算可能であるような十分条件はA. DeSantis, Y. Desmedt, Y. Frankel，およびM. Yung著「関数を安全に分散する方法」計算理論についての２６回年次シンポジウムの議事録、ACM、１９９４、pp. 522-533(“[DDFY]”)に定義され、以下のように述べることができる。
定義３（分散効率）  落とし戸転置は以下の場合に効率良く（多項式時間）分散変換可能である。１）puを与えられ、エレメントを乗算し、メッセージ空間Dpuの逆元を計算することがhの多項式時間であるとき、２）分散空間Kseがサンプル可能な集合であるとき、３）seを与えられて、ｈにおける多項式時間における「＋」及び逆元を計算することができるように分散空間Kse(+)がアーベルの群であるとき、および４）seを与えられて、Kseが予防多項式時間に発見できるときである。
落とし戸転置Fh群はその中にほとんどすべてのエレメントが存在する場合には、効率良く分散変換可能である。
分散変換および分散効率は、独力ではセキュリティを保証しない。安全にする関数分散プロトコルのためには、敵が受信するすべての情報はシステムを破壊することが可能であってはならない。安全を提供するためには、敵が受信するすべての情報はシミュレート可能な所定の公開情報である。
分散空間は、例えば、落とし戸転置の分散空間がKse=Zφ(n)(+)であり得るＲＳＡ関数としてサンプル可能ではないことがしばしばある。Φ（ｎ）についての情報の漏洩はセキュリティを包含しうる。{０、…、Φ（ｎ）−１｝における乱数を選択することは、分散配布をシミュレートする手段を提供するために公開情報のみを用いてDpu={0,...,n-1}によりシミュレート可能である。
シミュレート可能な性質は、公開情報のみを与えられた、多項式時間にｇ（分散関数）および関数z（シミュレート可能な関数）を介してKseを、およびZpu（シミュレート可能な分散空間）の行為をそれぞれシミュレートすることができることを示す。これは以下の如く述べることができる。
定義４（シミュレート可能）(pu, se)∈Fhを関数分散原始関数の入力とする。以下の場合にシャドウ関数生成フェーズはFhに対してシミュレート可能である。１）puが与えられると、（以下に定義する）Zpuの多項式空間記述及び多項式時間アルゴリズムZ: Zpu×Dpu→Dpuを返す予防多項式時間空間アルゴリズムＳ１が存在するとき、２）予防多項式時間アルゴリズムＳ２：K←S2(pu,se,k’)に対してf’k’=Zkであるような{0,1}h×{0,1}h×Kse→Zpuが存在するとき、および３）配布{x｜x∈RZpu}および{x｜y∈Rkse; x←S2(pu, se,y)}が統計的に区別できないとき。
落とし戸転置Fh群はほとんどすべてのエレメントがその中にある場合には、シミュレート可能である。
鍵空間の拡張
鍵空間の定義の拡張及びこの鍵空間上でどのように演算が行われるかについて以下に述べる。
定義５（鍵空間拡張）Z[u]を位数ｍの整数に対する代数学的拡張とする。拡張された分散空間はZ[u]に対するモジュールKq-1=Kse×...×Kse（すなわち、Kseのｍコピーの直積）である。lに対して有限のアーベルの群を均一にラグランジェ補間するための適当な代数学的構造を有するKseの拡張を作ることができる。ｑをｌ＋１以上の素数として、ｕを円分多項式
0004312835.tif 000046
の平方根とする。これはKseのｑ−１コピーの直積である、拡張鍵空間
0004312835.tif 000047
を定義する。
0004312835.tif 000048
に対するモジュール（すなわち、エレメントＵを有した整数の拡張）と考える。
補助定理１：ｑはｌ＋１以上の素数とし、ｕを円分多項式
0004312835.tif 000049
とする。
0004312835.tif 000050
とする。従って、(Xi-Xj)-1は
0004312835.tif 000051
に対して存在する。
証明：Z[u], u-1｜wj-1およびqにおける
0004312835.tif 000052
は素数であるので拡張ユークリッドアルゴリズム[HW](xi)-1を用いて
0004312835.tif 000053
が計算される。さらに、gcd(uq-1,ui)である。これから、あるq1に対して
0004312835.tif 000054
は
0004312835.tif 000055
に対する逆元を持つことが容易にわかる。それゆえ、このモジュールは、
0004312835.tif 000056
のときXi-Xj(i≠j)が逆元を持つスカラーを持つ。この性質はこのモジュールに対するしきい値方式を作るのに有効である。
0004312835.tif 000057
を観察する。エレメントKq-1を[k0,...kq-2]として書くことが出来ると共に単位元[0....0]と書くことが出来る。（ただし０はKse(+)の単位元である）。Kq-1(+)における加算は[k0,...kq-2]+[k’0,...,K’q-2]=[k0+K’0,...,kq-2+K’q-2]として定義される。スカラー演算(b0+…bq-2uq-2)・[k0,...kq-2]はb∈Zに対するｂ・[k0,...kq-2]=[b・k0,....,b・kq-2]及びu・[k0,...kq-2]=[0, k0,...,kq-3]+[-kq-2,...,-kq-2]からリカーシブに定義される。
定義６（公開ドメイン拡張）  Z[u]を位数ｍの整数に対する代数学的拡張とする。拡張された公開ドメインはZ[u]に対するモジュールDq-1=Dpu×...×Dpu（すなわち、Dpuのｍコピーの直接積）である。
ＷＬＯＧ、公開ドメインは乗法であると考えることが出来る。同様に、エレメントDq-1を[m0,...,mq-2]及び単位元を[1,...,1]と書くことが出来る。但し、１はDpu(*)の単位元である。Dq-1(*)の乗算は[m0,....,mq-2]*[m’0,....,m’q-2]=[m0*m’0,.....,mq-2*m’q-2]と定義される。スカラー演算
0004312835.tif 000058
はb∈Zに対する
0004312835.tif 000059
及び
0004312835.tif 000060
からリカーシブに定義される。
ＤＤＦＹしきい値暗号系
上述した理論的根拠に基づいて、一般的なプロトコルは以下のように実現可能である。代数学的拡張の使用の態様における種々の変更が可能であり、有限幾何学の使用の場合と類似した技術も可能である。例えば、xiとxi-xi（但しi≠j）がすべての必要な補間点に対して整数拡張の逆元を有するように十分な補間点が存在する整数に対する拡張が使用可能である。
セットアップ：fk(*)を分散すべき関数とする。ｑ＞１を素数とし、ｕを円分多項式
0004312835.tif 000061
とする。
0004312835.tif 000062
とする。
分散配布フェーズ：ランダム「多項式」
0004312835.tif 000063
0004312835.tif 000064
はr([0,...,0])=[k,0,...0]であるように、さもなければ乱数であるように選択される。S’i=[C’i,0,....,C’i,q-2]=r(xi)を計算する。次に(Z-1,Zpu)←S1(pu)を発行し、ｉのプライベート共存はSi=[Ci,0,...Ci,q-2]（但しCi,j=S2(pu,se,C’i,j)である。
分散関数評価フェーズ：メッセージｍに対して共同で署名するために、サーバｉは部分結果である
0004312835.tif 000065
を結合関数に送信する。次に結合関数は、
0004312835.tif 000066
を計算し、
0004312835.tif 000067
0004312835.tif 000068
の結果を計算する。
定義２、３、及び４を満足する関数に対して上述の式は安全でかつ正しい関数分散プロトコルである。A.De Santis, Y. Desmedt, Y. Frankel及びM. Yung著「関数を安全に分散する方法」、計算論についての２６回年次シンポジウムの議事録、ＡＣＭ  １９９４、ｐｐ．５２２−５３３
この利点は、このプロトコルが完全に非対話型であるという点である。シャドウ保持者は直接あるいは間接に互いに通信する必要は一切無い。これはシャドウ保持者が分散関数分散動作を行うシャドウ保持者の個人情報を知る必要が無いという事実による。実際には、これは非常に有益である。
予防化
以下にシミュレート可能性状態で始まる、一般化された関数のための好適実施の形態としてプロトコルが予防化される方法について述べる。
定義７（加算的シミュレート可能性）Z’puを、Zpuを含む整数の集合とする。さらに、Ｍｅｍ（ａ）＝a∈Zpuである場合のみ真
注）Zpu及びZ’pu（ｐｕにより示される）はｎを法として整数であるZnとは異なる。
予防化技術は多から和（上記分散の分散（多から和）のタイトルが付されたセクション参照）への更新フェーズの後に和から多へのフェーズ（上記「安全予防ＲＳＡ」参照）が続く場合を除いて上述した関数アプリケーションを使用することである。堅固性のために、Y. Frankel, P. Gemmell, P. Mackenzie及びM. Yung著「証人ベースの暗号作成プログラムチェック及び堅固な関数分散」計算理論についての２８回年次シンポジウムの議事録（”［ＦＧＹ」”］
定義８（シミュレート可能な空間拡張）Z[u]を位数ｍの整数に対する代数学的拡張とする。拡張された公開ドメインはバイナリ演算Zq-1(+)=Z’pu×...×Z’pu（すなわち、Z[u]に対するZ’puのｍコピーの直積）を有した集合である。
ＷＬＯＧ、シミュレート可能な空間は加算的であると考えることができる。同様にエレメントZq-1を[S0,....Sq-2]と書くことが出来る。Zq-1(+)の加算は[S0,....,Sq-2]+[S’0,....,S’q-2]=[S0+S’0,...,Sq-2+S’q-2]として定義される。スカラー演算(b0+....+bq-2uq-2)[s0,...,sq-2]は、b∈Z及びu・[s0,....,sq-2]=[0,s0,...,sq-3]+[-sq-2,...,-sq-2]に対するb・[s0,...,sq-2]=[b・s0,...,b・sq-2]からリカーシブに定義される。
他の関数
予防的暗号作成システムはさらに合成関数に対して定義されたものを含む離散対数を用いた暗号作成関数に基づくことができる。それゆえ、例えばEl Gamal暗号化は最適復元力を有した予防システムを持つことができる。楕円曲線のようなＲＳＡベースの異形もまたこの発明に従って予防するための十分な代数学的性質を有する。
ＤＤＦＹを有した多から和
以下に述べるのは［ＤＤＦＹ］・・σi([S70,...,S’q-2])=S’iである定義選択関数σiに基づく予防化のための多から和の方法である。
セットアップ：g’∈Dpuが最大位数であり、すべてのｉに対してSi=gsiを発行するように、分散配布中にディーラがエレメントg=[g’,1,...1]を発行すると仮定する。Λを｜Λ｜=tであるΛを分散の分散プロトコルに参加する分散保持者（サーバ）であるとする。
分散を分散する：サーバｉ
・ri,j∈Rzpuを生成する。
・私的にに、公開チャンネルri,j（公開にメッセージに委託する行為）に対する予防暗号化を用いてサーバｊに送信する。
・自己が保持する分散を
0004312835.tif 000069
（式（２）のようなyi,Λ）に設定する。
0004312835.tif 000070
を発行
分散の検証と生成：ri,jをｉからｊにより受け取った分散とする。
１．各サーバｊはすべてのｉ∈Λ｜{j}に対して
0004312835.tif 000071
であることを検証する。検証が通らなければ、サーバｉは除去され新しいΛが選択される。
・i≠jに対して
0004312835.tif 000072
検証がｊにより論争されるならri,jは明らかにされ（委託中止され）、ｉまたはｊのいずれかが適切に除去される。プロトコルは停止される。
２．すべての検証が通ると、新しいシャドウであるシャドウ保持者のｊは
0004312835.tif 000073
である。
予防化されたＤＤＦＹプロトコル
分散配布（セットアップ）Ｕ＝０とする。
ｋ∈Kseを秘密にしfk(’)を共有すべき関数とする。ｑ＞１を素数とし、ｕを円分多項式
0004312835.tif 000074
とする。
ディーラはr({0,...,0})=[k,0,...0]、さもなければ乱数であるようなランダム「多項式」
0004312835.tif 000075
を選択する。s’i=[c’i,0,....,c’i,q-2]=r(xi)を計算する。(z-1,Zpu)←S1(pu)を発行して、プライベートにサーバｉに対して分散Si=[ci,0,...ci,q-2]（但しS’i=[C’i,0,...,C’i,q-2]及びCi,j=S2(pu,se,C’i,j)）を送信する。ディーラはｇ’∈Dpuが最大位数であり、すべてのｉに対して
0004312835.tif 000076
を発行するようなエレメントg=[g’,1,...,1]を発行する。
更新期間：Ｕ←Ｕ＋１とする。
１．Λにより定義されるｔのシャドウ保持者の集合が論争を有さず、各々のS’iであり分散に同意する迄時間U-1,Si,U-1から分散により分散プロトコルの「多から和」分散（「ＤＤＦＹを有した多から和」のタイトルが付されたセクション）を実行する。
２．分散プロトコルの「和から多」分散を実行
（ａ）各I∈Λは係数
0004312835.tif 000077
を有した位数ｔ＝１のランダム多項式
0004312835.tif 000078
を発生することによりS’iを共有する。
（ｂ）次にサーバi∈Λはすべての
0004312835.tif 000079
を発行し、私的にj∈{1,...,1}に対してWi,j=r’i(xj)を送信する。
（ｃ）各サーバｉは検証する：
・［Ｆ］検証に類似
0004312835.tif 000080
（但し、証人
0004312835.tif 000081
は公開値ｉ（分散の分散「多から和」のタイトルが付けられたセクション）から生成される。
（ｄ）次に、論争の決議が行われる。検出された欠陥および改悪されたシステムがリブートされ分散更新プロセスが最初から論争がなくなるまで続く。
（ｅ）この結果、
0004312835.tif 000082
となる。従前のヒストリーを消去し、新しい現在のシャドウsi,Uを維持する。
0004312835.tif 000083
は
0004312835.tif 000084
を用いて計算される。
wi,jのサイズは、分散保持者が効率よく計算できないような大きな分散を敵が送る攻撃を防止するために十分な大きさの固定サイズのパケット（フィールド）を介して送られる。
分散関数アプリケーション：時間をＵとする。サーバ鍵がZpu×...×ZpuよりはむしろZ’pu×...×Z’puにサーバ鍵がある場合を除いて、シャドウSi,Uを用いて「ＤＤＦＹしきい値暗号作成システム」のタイトルが付されたセクションに呈示された［ＤＤＦＹ］方式として実行される。堅固性のために証人
0004312835.tif 000085
を用いた［ＦＧＹ］プロトコルを使用する。
ここに記載した実施の形態は、暗号作成関数の値を評価し送信するサーバに基づく相対的に効率のよい構成を用いている。この発明の技術はさらに、通信が暗号作成関数を計算する回路の規模に比例した「安全回路評価」の理論的概念により特徴づけられる効率が良くない通信構成にも適用可能である。
「予防モデル」の他のアプリケーションは関数分散方式における分散保持者の柔軟性のある鍵管理である。復元された新しい分散を古いサーバよりも新しいサーバに与えることによりリフレッシュ期間に分散保持者群を変更することが可能である。この発明のプロトコルはこの能力を拡張し、その上しきい値の動的変化を可能にする。
上述の説明はある「サイズパラメータ」（例えば、鍵長および鍵の分散の長さ等）について言及した。「セキュリティレベル」の概念および「性能レベル」に対するトレードオフに従って鍵の、サイズあるいは相対サイズを選択することが熟考される。安全性を高めたい場合には、より長い鍵群を選択し、より長い鍵群はより多くのメモリ空間を取り、計算するのにより多くの計算時間がかかる。サイズパラメータは、増大させると、より高い安全性を提供するシステムのパラメータとして、減少させると、より高い性能を提供するシステムパラメータとして変更可能である。
この発明の他のアプリケーション例としては、１）配布されたシステムが、認可された入力に基づいて証明書を生成するのに使用される証明書の認可、及び２）分散保持者がエスクロウエージェントであり、エスクロウから取るべき認可された暗号文の復号を作るのに複数のエスクロウエージェントが必要であるエスクロウエージェンシを含む。
ここに記載した実施の形態は例示に過ぎず限定するものではない。この発明の範囲と精神を逸脱することなく多くの変更が可能であることが理解される。
【図１】
0004312835.tif 000086
【図２】
0004312835.tif 000087
【図３】
0004312835.tif 000088
【図４】
0004312835.tif 000089
【図５】
0004312835.tif 000090
【図６】
0004312835.tif 000091
【図７】
0004312835.tif 000092
【図８】
0004312835.tif 000093
【図９】
0004312835.tif 000094
【図１０】
0004312835.tif 000095
【図１１】
0004312835.tif 000096
【図１２】
0004312835.tif 000097