(57)【要約】【課題】本発明によれば、非同期式ネットワークを介してｎ台の参加ネットワーク装置間でシークレット値ｘを共有する方法が提供される。【解決手段】ｎ台の参加ネットワーク装置は、ｔ台の障害のある装置、およびシークレット値ｘを再構築することが可能なｋ台の副次装置を備えており、ここでｔ＜ｎ／３かつｋ＜ｎである。シークレット値ｘはディストリビュータにより提供される。本方法は、そのディストリビュータが、リニア・シークレット共有スキームを適用することにより、シークレット値ｘの共有値ｓｉおよび副次共有値ｓｉｊを導き出し、共有値ｓｉおよび副次共有値ｓｉｊの妥当性を検証するために使用可能な検証値【数１】2004525466.tif 000047を導き出すステップと、対応する副次共有値ｓＡｉ、ｓｉＡ、ｓＢｉ、ｓｉＢ、ｓＣｉ、ｓｉＣを含む共有メッセージを、各参加ネットワーク装置に送信するステップと、その検証値【数２】2004525466.tif 000048を含む検証メッセージを同報通信するステップと、少なくともｌ台（ｎ−ｔ≧ｌ≧２ｔ＋１）の参加ネットワーク装置により、検証値【数３】2004525466.tif 000049を含む検証メッセージを受信するステップと、各受信側ネットワーク装置について以下のステップ１）ないし４）、すなわち１）副次共有値ｓｉｊを含む共有メッセージが受信される場合に、検証値【数４】2004525466.tif 000050に基づいて副次共有値ｓｉｊの妥当性を判定するステップと、２）判定が肯定的な場合に、合意値Ｙを含む合意メッセージを同報通信するステップと、３）合意値ＹＡ、ＹＢ、ＹＣを含むｌ個の合意メッセージを受信するステップと、４）ｌ個の受信済み合意メッセージがある場合に、ディストリビュータＤによって送信された共有メッセージ、または参加ネットワーク装置から受信した副次共有値ｓｉｊのいずれかから共有値ｓｉを得て、検証値【数５】2004525466.tif 000051に基づいて副次共有値ｓｉｊの妥当性を判定するステップとを実施するステップを含む。本発明の第２の態様として、同報通信のない方法が開示されている。【選択図】図２
2004525466.tif 000002
【特許請求の範囲】
【請求項１】
非同期式ネットワークを介してｎ台の参加ネットワーク装置（Ａ、Ｂ、Ｃ）間でシークレット値（ｘ）を共有する方法であって、前記ｎ台の参加ネットワーク装置（Ａ、Ｂ、Ｃ）が、ｔ台の障害のある装置と、前記シークレット値（ｘ）を再構築することが可能なｋ台の副次装置とを備え、ｔ＜ｎ／３かつｋ＜ｎであり、前記シークレット値（ｘ）がディストリビュータ（Ｄ）によって提供され、
前記ディストリビュータ（Ｄ）が、リニア・シークレット共有スキームを適用することにより前記シークレット値（ｘ）の共有値（ｓｉ）および副次共有値（ｓｉｊ）を導き出し、前記共有値（ｓｉ）および前記副次共有値（ｓｉｊ）の妥当性の検証のために使用可能な検証値
【数１】
2004525466.tif 000030
を導き出すステップと、
各参加ネットワーク装置（Ａ、Ｂ、Ｃ）に対して前記対応する副次共有値（ｓＡｉ、ｓｉＡ、ｓＢｉ、ｓｉＢ、ｓＣｉ、ｓｉＣ）を含む共有メッセージを送信するステップと、
前記検証値
【数２】
2004525466.tif 000031
を含む検証メッセージを同報通信するステップと、
少なくともｌ台（ｎ−ｔ≧ｌ≧２ｔ＋１）の参加ネットワーク装置（Ａ、Ｂ、Ｃ）が前記検証値
【数３】
2004525466.tif 000032
を含む前記検証メッセージを受信し、各参加ネットワーク装置（Ａ、Ｂ、Ｃ）について、以下のステップ１）ないし４）、すなわち
１）副次共有値（ｓｉｊ）を含む前記共有メッセージを受信した場合に、前記検証値
【数４】
2004525466.tif 000033
に基づいて前記副次共有値（ｓｉｊ）の妥当性を判定するステップと、
２）判定結果が肯定的な場合に、合意値（Ｙ）を含む合意メッセージを同報通信するステップと、
３）前記合意値（ＹＡ、ＹＢ、ＹＣ）を含むｌ個の合意メッセージを受信するステップと、
４）ｌ個の合意メッセージを受信した場合に、前記ディストリビュータ（Ｄ）によって送信された前記共有メッセージ、または参加ネットワーク装置（Ａ、Ｂ、Ｃ）から受信した副次共有値（ｓｉｊ）のいずれかから前記共有値（ｓｉ）を得て、前記検証値
【数５】
2004525466.tif 000034
に基づいて前記副次共有値（ｓｉｊ）の妥当性を判定するステップと
を実施するステップとを含む方法。
【請求項２】
非同期式ネットワークを介してｎ台の参加ネットワーク装置（Ａ、Ｂ、Ｃ）間でシークレット値（ｘ）を共有する方法であって、前記ｎ台の参加ネットワーク装置（Ａ、Ｂ、Ｃ）が、ｔ台の障害のある装置と、前記シークレット値（ｘ）を再構築することが可能なｋ台の副次装置とを備え、ｔ＜ｎ／３かつｋ≦ｎ−ｔであり、前記シークレット値（ｘ）がディストリビュータ（Ｄ）によって提供され、
前記ディストリビュータ（Ｄ）が、リニア・シークレット共有スキームを適用することにより前記シークレット値（ｘ）の共有値（ｓｉ）および副次共有値（ｓｉｊ）を導き出し、前記共有値（ｓｉ）および前記副次共有値（ｓｉｊ）の妥当性の検証のために使用可能な検証値
【数６】
2004525466.tif 000035
を導き出すステップと、
各参加ネットワーク装置（Ａ、Ｂ、Ｃ）に対して前記対応する副次共有値（ｓＡｉ、ｓｉＡ、ｓＢｉ、ｓｉＢ、ｓＣｉ、ｓｉＣ）と前記検証値
【数７】
2004525466.tif 000036
とを含む第１のメッセージを送信するステップと、
少なくとも２ｔ＋１台の参加ネットワーク装置（Ａ、Ｂ、Ｃ）について、各参加ネットワーク装置（Ａ、Ｂ、Ｃ、指標ｉ付き）ごとに以下のステップ、すなわち
ｉ）副次共有値（ｓｉｊ、ｓｊｉ）を含む前記第１のメッセージを受信した場合に、前記検証値
【数８】
2004525466.tif 000037
に基づいて前記副次共有値（ｓｉｊ、ｓｊｉ）の妥当性を判定するステップと、
ｉｉ）判定結果が肯定的な場合に、前記受信した副次共有値（ｓｉｊ、ｓｊｉ）から、他の参加ネットワーク装置（Ａ、Ｂ、Ｃ、指標ｍ付き）と共通の関連した副次共有値（ｓｉm、ｓmｉ）を導き出し、各参加ネットワーク装置（Ａ、Ｂ、Ｃ、指標ｍ付き）に対して前記検証値
【数９】
2004525466.tif 000038
および前記関連した副次共有値（ｓｉm、ｓmｉ）を含む第２のメッセージを送信するステップと、
ｉｉｉ）１台の参加ネットワーク装置（Ａ、Ｂ、Ｃ、指標ｊ付き）から前記第２のメッセージを受信した場合に、前記検証値
【数１０】
2004525466.tif 000039
に基づいて前記受信した副次共有値（ｓｉｊ、ｓｊｉ）の妥当性を判定するステップと、
ｉｖ）２ｔ＋１個の受信した第２のメッセージについて判定結果が肯定的な場合に、各参加ネットワーク装置（Ａ、Ｂ、Ｃ、指標ｍ付き）に対して前記検証値
【数１１】
2004525466.tif 000040
および前記関連した副次共有値（ｓｉm、ｓmｉ）を含む第３のメッセージを送信し、第１のメッセージを受信していない場合には、前記受信した第２のメッセージから前記関連した副次共有値（ｓｉm、ｓmｉ）を導き出すステップと、
ｖ）１台の参加ネットワーク装置（Ａ、Ｂ、Ｃ、指標ｊ付き）から前記第３のメッセージを受信した場合に、前記検証値
【数１２】
2004525466.tif 000041
に基づいて前記受信した副次共有値（ｓｉｊ、ｓｊｉ）の妥当性を判定するステップと、
ｖｉ）ｔ＋１個の受信した第３のメッセージについて判定結果が肯定的で、かつ第３のメッセージをまだ送信していない場合に、各参加ネットワーク装置（Ａ、Ｂ、Ｃ、指標ｍ付き）に対して前記検証値
【数１３】
2004525466.tif 000042
および前記関連した副次共有値（ｓｉm、ｓmｉ）を含む１つの第３のメッセージを送信し、第１のメッセージをまだ受信していない場合には、前記受信した第２または第３のメッセージから前記関連した副次共有値（ｓｉm、ｓmｉ）を導き出すステップと、
ｖｉｉ）２ｔ＋１個の受信した第３のメッセージについて判定結果が肯定的な場合に、前記受信した第１、第２、または第３のメッセージから前記共有値（ｓｉ）を導き出すステップと
を実施するステップとを含む方法。
【請求項３】
ステップ１）が、各参加ネットワーク装置（Ａ、Ｂ、Ｃ）に対してその副次共有値（ｓｉｊ）および追加の検証値を送信するステップと、ｌ個の追加の検証値を受信するとすぐ、前記受信した追加の検証値に基づいて前記検証値
【数１４】
2004525466.tif 000043
を変更するステップとをさらに含む、請求項１に記載の方法。
【請求項４】
参加ネットワーク装置（Ａ、Ｂ、Ｃ）から受信した副次共有値（ｓｉｊ）から前記共有値（ｓｉ）を得るステップが、コンプレイン・メッセージを同報通信するステップと、前記コンプレイン・メッセージに応答して送信された前記副次共有値（ｓｉｊ）を受信するステップとをさらに含む、請求項１に記載の方法。
【請求項５】
前記検証値
【数１５】
2004525466.tif 000044
が、前記リニア・シークレット共有スキームに対応する暗号群Ｇから共通数（ｇ）を選択すること、および前記選択された共通数（ｇ）を、前記共有値（ｓｉ）の単調関数乗することによって、前記検証値
【数１６】
2004525466.tif 000045
を導き出すことにより導き出される、請求項１ないし４のいずれか一項に記載の方法。
【請求項６】
前記検証値
【数１７】
2004525466.tif 000046
がハッシュ関数を使用して導き出される、請求項１ないし５のいずれか一項に記載の方法。
【請求項７】
いくつかのシークレット値が同時に共有される、請求項１ないし６のいずれか一項に記載の方法。
【請求項８】
前記障害のある装置の台数ｔが、参加ネットワーク装置（Ａ、Ｂ、Ｃ；Ｐ１〜Ｐ１９）を含む集合の集合Ｔに拡張される、請求項１ないし７のいずれか一項に記載の方法。
【請求項９】
前記参加ネットワーク装置（Ａ、Ｂ、Ｃ；Ｐ１〜Ｐ１９）が、前記集合Ｔの異なる構造、または異なる閾値ｔｉ（ｉ＝１,２,...ｍ）を反映する複合障害（ＢＦ、ＣＦ、ＬＦ）を示す、請求項８に記載の方法。
【請求項１０】
請求項１ないし９のいずれか一項に記載の方法をコンピュータに実行させるプログラム。
【請求項１１】
請求項１ないし９のいずれか一項に記載の方法をコンピュータに実行させるプログラムを記録した、コンピュータ可読記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プロセッサ・ノードが非同期式に情報を交換するネットワークに関し、より詳細には、未検出の悪意のあるノードが存在しても、十分に大きなノードの部分集合は、シークレット値を再構築することができるが、それより小さな集合ではそれを何としても解決できないような方法で、ノード間でシークレット値を共有するための方法に関する。
【背景技術】
【０００２】
シークレット共有スキームは、情報をｎ個の異なるロケーションに分散させることによって、情報の機密性と保全性を保護する。この情報はある最小限数のロケーションにアクセスできる場合に限り、回復することができる。具体的に言うと、（ｋ，ｎ）閾値スキームにおいては、ｋ個のロケーションが一緒になってシークレット情報を再構築することができるが、ｋ−１個のロケーションでは、それに関する情報を得ることはできない。
【０００３】
H. Krawczyk et al. 「Proactive secretsharing or: How to cope with perpetual leakage」、In Crypto '95, 339〜352頁、SantaBarbara、1995年に、同期式の予防的なシークレット共有スキームが提示されている。このスキームでは、システムの存続時間を短い時間枠のみに分割し、したがって、敵が１つの時間枠中にｋ−１個を超えるロケーションに侵入できないと想定するのが妥当である。さらに、敵は一時的である、すなわち破壊されたサーバは識別することができ再ブートすることができるので、敵はそれらを制御できなくなると想定されるが、なおサーバの最後の状態を記憶している。各時間枠の最初に、敵が以前の時間枠で集めた情報が時代遅れになるように、システムをリフレッシュする。システムのリフレッシュとは、古いシークレットの共有部を新しく無作為に生成することである。
【０００４】
非同期式の検証可能なシークレット共有システムが、Ran Canettiand TalRabin、「Fast asynchronous Byzantine agreement with optimal resilience」、in STOC93、42〜51頁、NewYork、1993年に提案されたが、これはFeldman and Micali、「An Optimal Probabilistic Protocol forSynchronous Byzantine Agreement」、STOC 88、148〜161頁、New York、1988年のアイデアに基づいている。このスキームは、公開鍵暗号を使用していないが、メッセージは極めて複雑である。
【非特許文献１】
H. Krawczyk et al.、「Proactivesecret sharing or: How to cope with perpetual leakage」、In Crypto '95, 339〜352頁、SantaBarbara、1995年
【非特許文献２】
Ran Canettiand Tal Rabin、「Fastasynchronous Byzantine agreement with optimal resilience」、in STOC93、42〜51頁、NewYork、1993年
【非特許文献３】
Feldman and Micali、「An OptimalProbabilistic Protocol for Synchronous Byzantine Agreement」、STOC 88、148〜161頁、NewYork、1988年
【非特許文献４】
A.Shamir、「How to share a secret」、Communicationsof the ACM 22（1979年）、612〜613頁
【非特許文献５】
Cachin et al.、「Secure and EfficientAsynchronous Broadcast Protocols」、Joe Kilian編、Advance in Cryptology: CRYPTO 2001、LectureNotes in Computer Science、2139巻、524〜541頁、Springer、2001年
【非特許文献６】
Cachin et al.、「Random Oracles inConstantinople: Practical Byzantine Agreement using Cryptography」、in PODC00、Portland、Oregon、2000年
【非特許文献７】
T. Pedersen、「Non-interactive andinformation-theoretic secure verifiable secret sharing」、CRYPTO'91、Lecture Notesin Computer Science 576巻、129〜140頁、Springer-Verlag、1992年
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明の一目的は、最大ｔ個の障害のある装置、プロセッサ、またはパーティを許容することのできる潜在的に非同期式のネットワーク用の検証可能なシークレット共有スキームを作成することである。この意味での部分的に非同期式のネットワークとは、ネットワークが状況および所与の仮定に応じて同期モードまたは非同期モードのいずれでも動作することができることを意味する。
【０００６】
本発明の他の目的は、ｎ個のプロセッサまたはパーティの間で動作可能であり、多くてもｔ個（ｔ＜ｎ／３）のプロセッサに障害があり、さらに一定時間共有が実現でき、交換されるメッセージ数がｎの２乗程度である方法を提供することである。
【０００７】
用語解説
以下は、説明の理解を助けるための非公式の定義である。
【０００８】
非同期の検証可能なシークレットの共有（ＡＶＳＳ）においては、ｋ個以上のどのような連携パーティでも効率的にｘを構築できるのに、ｋ−１個のパーティが連携してもｘを得ることができないように、シークレット値ｘが、ディーラまたはディストリビュータによりＰ１、．．．、Ｐｎのｎパーティ間で共有される。このことを（ｋ，ｎ）共有とも呼び、シークレット値ｘを再構築するのにｎパーティ中のｋパーティが必要とされることを示す。
【０００９】
群：暗号法の意味における群は、元または数の集合と、いくつかの指定された属性を備えた群演算（＊）から成る代数系（Ｇ，＊）であり、ここで（＊）は結合法（associative）であり、単位元をもち、Ｇのすべての元が逆元を有している。記号（＊）の選択は任意である。実際には、大部分の群の演算は、＋または・のいずれかで示され、このような群は、それぞれ加法群または乗法群と呼ばれる。
【００１０】
例えば、任意の正整数ｑについて、集合Ｚｑは、整数０、．．．、ｑ−１から成り、それは、ｑを法とする加法演算の群を形成する。さらに、ａに対して互いに素な整数からなるＺｑの部分集合は、ｑを法とする乗法群を形成し、Ｚｑ＊で示される。特に、ｐが素な場合には、Ｚｑ＊は｛１,...,ｐ−１｝からなり、ｐ−１個の元を有する群である。
【００１１】
ハッシュ関数：ハッシュ関数は、任意長の２進ストリングを、ある固定長の２進ストリングに写像する計算効率のよい関数である。
【００１２】
複合障害
ビザンチン合意（Byzantine Agreement）を実現するための方法では、ネットワーク装置に障害の起こる可能性のあるいくつかの異なる方法を区別することができる。この例を以下に示す。
【００１３】
ビザンチン障害ＢＦ（Byzantine Failure）：ビザンチン障害ＢＦが起こる場合には、敵は対応するマシンを完全に制御してしまっている。このマシンが有するすべてのシークレットが敵の手に渡り、敵は今やその動作のすべてを制御する。
【００１４】
クラッシュ障害ＣＦ（Crash Failure）：クラッシュ障害ＣＦは、単に対応するマシンが動作を停止することを意味する。これは、いつでも、すなわち同報通信の最中またはメッセージの送信中でさえ、起こる可能性がある。他のパーティがこのようなクラッシュを確実に検出できるメカニズムはないと考えられている。
【００１５】
リンク障害ＬＦ（Link Failure）：リンク障害ＬＦは、パーティではなくて相互接続リンクに障害が起こるときに起こる。リンクは、認証鍵に対するアクセス権がないので、リンクがメッセージを修正したり、挿入したりするのを防ぐのは容易である。しかしながら、障害のあるリンクはメッセージを除去してしまう可能性があり、それによって２つのパーティ間の接続を完全に切ることもある。
【００１６】
敵構造（Adversary structure）
敵構造Ｔは、その破壊をシステムが許容すべきパーティの集合（連合）の１つの集合である。これによって、閾値スキームが一般化されて、より柔軟になり環境構造に適合できるようになる。
【課題を解決するための手段】
【００１７】
本発明によれば、私用リンクを備えた非同期式ネットワークを介してｎ台の参加ネットワーク装置間でシークレット値ｘを共有する、すなわち正直な参加者間の通信が敵によって読み取ることができないようにするための、マシン実装可能な方法が提供される。ｎ台の参加ネットワーク装置は、ｔ台の障害のある装置、およびシークレット値ｘを再構成することの可能なｋ台の副次装置（sub-device）を含んでおり、ここで、ｔ＜ｎ／３かつｋ＜ｎである。このシークレット値ｘは、ディストリビュータによって提供される。本方法は、そのディストリビュータにより、リニアなシークレット共有スキームを適用することにより、シークレット値ｘの共有値ｓｉおよび副次共有値（subsharevalue）ｓｉｊを導き出し、共有値ｓｉおよび副次共有値ｓｉｊの妥当性を検証するために使用可能な検証値
【００１８】
【数１】
2004525466.tif 000003
を導き出すステップと、対応する副次共有値ｓＡｉ、ｓｉＡ、ｓＢｉ、ｓｉＢ、ｓＣｉ、ｓｉＣを含む共有メッセージを、各参加ネットワーク装置に送信するステップと、その検証値
【００１９】
【数２】
2004525466.tif 000004
を含む検証メッセージを同報通信するステップと、少なくともｌ台（ｎ−ｔ≧ｌ≧２ｔ＋１）の参加ネットワーク装置により、検証値
【００２０】
【数３】
2004525466.tif 000005
を含む検証メッセージを受信するステップと、各受信側ネットワーク装置について以下のステップ１）ないし４）、すなわち１）副次共有値ｓｉｊを含む共有メッセージが受信される場合に、検証値
【００２１】
【数４】
2004525466.tif 000006
に基づいて副次共有値ｓｉｊの妥当性を判定するステップと、２）判定が肯定的な場合には、合意値Ｙを含む合意メッセージを同報通信するステップと、３）合意値ＹＡ、ＹＢ、ＹＣを含むｌ個の合意メッセージを受信するステップと、４）ｌ個の受信済み合意メッセージがある場合に、ディストリビュータＤによって送信された共有メッセージ、または参加ネットワーク装置から受信した副次共有値ｓｉｊのどちらかから共有値ｓｉを得て、検証値
【００２２】
【数５】
2004525466.tif 000007
に基づいて副次共有値ｓｉｊの妥当性を判定するステップとを実施するステップを含む。
【００２３】
本発明の第２の態様においては、非同期ネットワークを介してｎ台の参加ネットワーク装置Ａ、Ｂ、Ｃ間でシークレット値ｘを共有するマシン実装可能な方法が提供され、ｎ台の参加ネットワーク装置Ａ、Ｂ、Ｃは、ｔ台の障害のある装置、およびシークレット値ｘを再構築可能なｋ台の副次装置を備えており、ここでｔ＜ｎ／３かつｋ≦ｎ−ｔであり、シークレット値ｘは、ディストリビュータＤによって提供される。この方法は、同報通信することなしに実施される。
【００２４】
本方法は、効率がよく、最大数のパーティの破壊に耐えるという意味で理論的にほぼ最良でもある。さらに、この方法は非同期式の環境に適用可能であり、ビザンチン障害を許容する。
【００２５】
何らかのシークレット値ｘがすでに共有されている場合、この方法を使用して、０であるシークレット値ｙを共有することができる。検証値を使用して、ｙの値が本当に０であることを検証することができる。
【００２６】
ｘの共有値ｘｉに０の共有値ｙｉを加えることにより、新しい共有値ｙｉ＋ｘｉはシークレットｘ＋０すなわちｘを共有する。
【００２７】
このようにすることにより、同じシークレット値の新しい共有値が生成され、この値を使用して敵に漏えいした可能性のある古い共有値が役に立たないようにすることができる。
【００２８】
有利なことには、この方法を修正して、指標ｉの付いたあらゆる参加ネットワーク装置がその副次共有値ｓｉ１〜ｓｉｎ、およびｓ１ｉ〜ｓｎｉをすべて導き出せるようにすることが可能である。このようにして、既知の副次共有値ｓ１ｉ〜ｓｎｉから対応する副次共有値Ｓ（ｎ＋１）ｉを再構築することにより、シークレット値ｘを共有する１群の参加ネットワーク装置に、追加のネットワーク装置を効率的に組み込むことが容易になる。
【００２９】
この副次共有値ｓｉｊおよび追加の検証値を、各参加ネットワーク装置に送信することができ、十分な追加の検証値を受信するとすぐに受信した追加の検証値に基づいて検証値
【００３０】
【数６】
2004525466.tif 000008
を変更することができる。これには、検証メッセージを同報通信するために使用される同報通信プリミティブが簡単になり、それによってネットワークの通信が少なくなるという利点がある。
【００３１】
参加ネットワーク装置が受信した副次共有値ｓｉｊから共有値ｓｉを得るステップが、コンプレイン・メッセージを同報通信するステップと、コンプレイン・メッセージに応答して送信された副次共有値ｓｉｊを受信するステップをさらに含む場合には、普通はそうであるがディストリビュータが正直な場合に、ネットワーク・トラフィックを低減することができるという利点がもたらされる。
【００３２】
リニア・シークレット共有スキームに対応する暗号群Ｇから共通の数ｇを選択すること、および選択した共通の数ｇを、共有値ｓｉの線形関数ｆ乗することによって、検証値
【００３３】
【数７】
2004525466.tif 000009
を導き出すことにより、この検証値
【００３４】
【数８】
2004525466.tif 000010
を導き出すことができる。そうすることにより、簡単な暗号プリミティブを使用して検証値
【００３５】
【数９】
2004525466.tif 000011
を生成することができる。
【００３６】
検証値
【００３７】
【数１０】
2004525466.tif 000012
は、ハッシュ関数を使用して導き出すことができる。これにより、検証値
【００３８】
【数１１】
2004525466.tif 000013
は小さくなる。したがって、ネットワークを介して転送しなければならないデータが少なくなる。
【００３９】
いくつかのシークレット値を同時に共有することができる。これは、相乗効果によって効率がより高くなる。
【００４０】
障害のある装置の台数ｔは、異なる参加ネットワーク装置、すなわち異なるオペレーティング・システムを実行し、異なるロケーションにある装置を含む複数の集合の集合Ｔと見ることができる。さらに、参加ネットワーク装置は、集合Ｔの異なる構造または異なる閾値ｔｉ（ｉ＝１、２、．．．）を反映して、例えばビザンチン障害、クラッシュ障害、およびリンク障害などの複合障害を示す可能性がある。このことは、このプロトコルの柔軟性を示している。
【００４１】
本発明の好ましい実施形態を、以下の概略図を参照して、例としてのみ以下に詳細に説明する。
【００４２】
図面は例示の目的で示したものにすぎず、また必ずしも、本発明の実際の例を一定の縮尺で表現してはいない。
【発明を実施するための最良の形態】
【００４３】
図１は、一般的なコンピュータ・システム８の一例を示すものであり、このシステムでシークレット値ｘが共有される。このシステムは、通信回線（１〜５）を介してネットワークに接続されたｎ＝４台の参加ネットワーク装置Ａ、Ｂ、Ｃ、およびＤから構成されている。このシステムはディストリビュータＤを含み、それが「Ｘ」で示される。各参加ネットワーク装置Ａ、Ｂ、Ｃ、Ｄは、チップ上のコンピュータまたはウェアラブル・コンピュータから大型コンピュータ・システムに至る当技術分野で知られるどのようなタイプのコンピュータ装置でもよい。通信回線は、１台の参加ネットワーク装置Ａ、Ｂ、Ｃ、Ｄから別の装置へデータまたはメッセージを伝送するための一般に知られたどんな通信手段でもよい。例えば、通信回線は、各対をなす参加ネットワーク装置Ａ、Ｂ、Ｃ、Ｄ間の１本の双方向通信回線５、または各対をなす参加ネットワーク装置Ａ、Ｂ、Ｃ、Ｄ間の各方向への単方向回線のどちらでもよい。かかるコンピュータ・システム８および通信回線５は、当技術分野において周知である。１台の参加ネットワーク装置Ａ、Ｂ、Ｃが情報をそれ自体に送信する場合には、その参加ネットワーク装置内で単にデータを移動することにより、通信回線上でそれ自体に情報を送信することなく、同等な結果を実現することができる。この一般的なコンピュータ・システム８は、以下の非同期式の検証可能なシークレット共有プロトコルの説明を容易にするために示したものである。同一または同様な部品を示すために同じ参照番号を使用している。
【００４４】
図２は、非同期式ネットワークを介して、ｎ台の参加ネットワーク装置Ａ、Ｂ、Ｃ間でシークレット値ｘを共有するためのプロトコルの全体的な流れを示すものであり、その中で、一連のメッセージが、各参加ネットワーク装置Ａ、Ｂ、Ｃ、Ｄによって送信または受信される。
【００４５】
ディストリビュータＤがシークレット値ｘを共有しようとしていると仮定する。まず、ボックス１０で示すように、ディストリビュータＤは、例えばA.Shamir、「How to share a secret」、Communications of the ACM 22（1979年）、612〜613頁に記載されているような標準のリニア・シークレット共有スキームに従って、シークレット値ｘの共有値ｓｉを導き出す。これに加えて、ディストリビュータＤは、副次共有値ｓｉｊとも呼ばれるいわゆる副次共有値も導き出す。これが意味するのは、共有値ｓｉごとにディストリビュータＤが、それぞれの副次共有値ｓｉｊを作成することである。この副次共有値ｓｉｊは、共有値ｓｉの作成とは独立の別のリニア・シークレット共有スキームによって実現できる。あるいは、２変数の多項式をもつShamirスキームを使用して、シークレット値ｘを共有することもできる。さらに、ディストリビュータＤは、ここで暗号群Ｇ内の簡単なべき乗演算によって検証値
【００４６】
【数１２】
2004525466.tif 000014
を導き出す。この検証値
【００４７】
【数１３】
2004525466.tif 000015
は、検証テーブルとして解釈される。この検証値
【００４８】
【数１４】
2004525466.tif 000016
は、共有値ｓｉおよび副次共有値ｓｉｊの妥当性を検証するために使用可能である。
【００４９】
【表１】
2004525466.tif 000017
【００５０】
表１に、各共有値ｓｉについての対応する副次共有値ｓｉｊを示す。特定行のすべての副次共有値ｓｉｊは、その行のいちばん左の値を共有するが、特定列のすべての副次共有値ｓｉｊは、いちばん上の値、共有値ｓｉを共有する。
【００５１】
値ｓ１１、ｓ１２．．．、ｓ１ｎによって共有される値が、値ｓ１０で示され、値ｓ１１、ｓ２１．．．、ｓｎ１によって共有される値が、ｓ０１で示されることに留意されたい。
【００５２】
このプロトコルの途中で、ディストリビュータＤのクラッシュ動作またはビザンチン動作を許容することができるのは、利点である。ｔ＋１台の正直な参加ネットワーク装置Ａ、Ｂ、Ｃが、シークレット値ｘの妥当な共有値ｓｉを受信したと思う場合、ディストリビュータＤからまったく知らされなかった場合でも、他のすべての正直な参加ネットワーク装置Ａ、Ｂ、Ｃは、そのｔ＋１台の参加ネットワーク装置Ａ、Ｂ、Ｃの助けを得て、シークレット値ｘのそれ自体の共有値ｓｉを再構築することができる。
【００５３】
しかしながら、不正直なディストリビュータＤが、不正な共有値ｓｉ、すなわち、組み合わせても固有のシークレット値ｘをもたらさない共有値ｓｉを配布することがそれでも可能である。この問題に対応するために、ディストリビュータＤは、すべての参加ネットワーク装置Ａ、Ｂ、Ｃが、シークレット値ｘについて何も知らなくても、受信した共有値ｓｉの妥当性をテストするのを可能にする検証情報を追加する。
【００５４】
ディストリビュータＤは、各参加ネットワーク装置Ａ、Ｂ、Ｃに、ボックス２０で示すような対応する副次共有値ｓＡｉ、ｓｉＡ、ｓＢｉ、ｓｉＢ、ｓＣｉ、ｓｉＣを含む共有メッセージｓｍを送信し、ボックス３０で示すような検証値
【００５５】
【数１５】
2004525466.tif 000018
を含む検証メッセージｖｍを同報通信する。この同報通信は、Cachin et al.、「Secureand Efficient Asynchronous Broadcast Protocols」、Joe Kilian編、Advance inCryptology: CRYPTO 2001、Lecture Notes in Computer Science、2139巻、524〜541頁、Springer、2001年に記載されているように、信頼性のある同報通信とすることができる。指標ｉをもつ参加ネットワーク装置Ａ、Ｂ、Ｃにとって、ディストリビュータＤが、この参加ネットワーク装置Ａ、Ｂ、Ｃに送信する副次共有値ｓｉｊは、表１の行ｉ、列ｉに相当する。ボックス１０、２０、および３０によって示されるステップは、Ｄのラベル付きのボックスで示すように、ディストリビュータＤによって実施される。
【００５６】
検証メッセージｖｍは、受信ネットワーク装置Ａ、Ｂ、Ｃがプロトコルの実行中に受信する共有値ｓｉおよび副次共有値ｓｉｊをすべて検証するのに十分な、より多くの情報を含んでいる。
【００５７】
検証メッセージｖｍは、ボックス４０で示すように、参加ネットワーク装置Ａ、Ｂ、Ｃによって受信される。次の諸ステップは、各受信ネットワーク装置Ａ、Ｂ、Ｃによって実施される。
【００５８】
副次共有値ｓｉｊを含む共有メッセージｓｍが以前のステップで受信された場合、ボックス５０で示すように、検証値
【００５９】
【数１６】
2004525466.tif 000019
に基づいて、副次共有値ｓｉｊの妥当性を判定する。判定結果が肯定的な場合には、ボックス６０に示すように、合意値Ｙを含む合意メッセージを同報通信する。次いで、合意値ＹＡ、ＹＢ、ＹＣを含むｌ個（ｎ−ｔ≧ｌ≧２ｔ＋１）の合意メッセージが、ボックス７０に示されるように、それぞれのネットワーク装置Ａ、Ｂ、Ｃによって受信される。ボックス７０およびボックス８０のステップもまた、９０のラベル付きの矢印で示すように、ボックス４０、５０、６０によって示したステップを実施していない１つの参加ネットワーク装置Ａ、Ｂ、Ｃによって実行することができる。
【００６０】
ｌ個の合意メッセージを受信した場合、各参加ネットワーク装置Ａ、Ｂ、Ｃは、ディストリビュータＤによって送信された共有メッセージｓｍ、または他の参加ネットワーク装置Ａ、Ｂ、Ｃから受信した副次共有値ｓｉｊのどちらかから、共有値ｓｉを得る。次いで検証値
【００６１】
【数１７】
2004525466.tif 000020
に基づいて、副次共有値ｓｉｊの妥当性を判定する。これがボックス８０に示されている。
【００６２】
コミットメントの使用
各共有値ｓｉおよび副次共有値ｓｉｊに対して、ディストリビュータＤは、コミットメント関数Ｃ（ｓｉ）またはＣ（ｓｉｊ）をそれぞれ計算する。それらのコミットメントには、共有値ｓｉおよび副次共有値ｓｉｊを組み合わせると１つのシークレット値ｘおよび共有値ｓｉが得られる場合には、Ｃ（ｓｉ）（またはＣ（ｓｉｊ））を組み合わせると１つのシークレットＣ（ｘ）（またはＣ（ｓｉ））が得られるという特徴がある。
【００６３】
１つの例は、Cachin et al.、「Random Oracles inConstantinople: Practical Byzantine Agreement using Cryptography」、in PODC00、Portland、Oregon、2000年で示されたように、素数オーダの有限群の中で指数を使用する、すなわちＣ（ｓｉ）＝
【００６４】
【数１８】
2004525466.tif 000021
とするものである。
【００６５】
しかし、もっと高度なコミットメント、例えばT. Pedersen、「Non-interactiveand information-theoretic secure verifiable secret sharing」、CRYPTO'91、LectureNotes in Computer Science 576巻、129〜140頁、Springer-Verlag、1992年に記載されているようなPedersenコミットメントを使用することも可能である。
【００６６】
それらのコミットメントは、Cachin et al.、「Secure anEfficient Asynchronous Broadcast Protocols」、Joe Kilian編、Advances in Cryptology:CRYPTO 2001、Lecture Notes in Computer Science 2139巻、524〜541頁、Springer、2001年に記載されているように、一貫した同報通信を使用して、すべての参加ネットワーク装置Ａ、Ｂ、Ｃに配布される。すなわち、すべての参加ネットワーク装置ＡＢＣは同じコミットメントを受信する。以下で通信の複雑さの最適化について説明するときに示すように、プロトコルに新しいステップを追加して、この同報通信を簡単にすることができる。
【００６７】
プロトコルは、次いで以下のように進む。
１．ディストリビュータＤが、指標ｉをもつ参加ネットワーク装置Ａ、Ｂ、Ｃに、共有値ｓｉおよび副次共有値ｓｉｊをすべて配布し、それぞれのメッセージ中で検証テーブルを同報通信する。
【００６８】
２．ディストリビュータＤから上記メッセージを受信した各参加ネットワーク装置Ａ、Ｂ、Ｃが、以下についてテストする。
・その共有値ｓｉおよび副次共有値ｓｊｉは検証テーブル中のＣ（ｓｉ）およびＣ（ｓｊｉ）に対応するか
・検証テーブル中のＣ（ｓｉｊ）を組み合わせて１つの固有なＣ（ｓｉ）が得られるか
・検証テーブル中のＣ（ｓｊｉ）を組み合わせてなにか固有な値が得られるか
【００６９】
３．指標ｉをもつ１つの参加ネットワーク装置Ａ、Ｂ、Ｃが、共有値ｓｉおよび副次共有値ｓｊｉをすべて受信し、すべてのテストがＯＫである場合、この装置は１つの「ＯＫメッセージ」を同報通信する。
【００７０】
４．十分に多くの、すなわち少なくとも２ｔ＋１個のＯＫメッセージを受信したとき、指標ｉをもつそれぞれの参加ネットワーク装置Ａ、Ｂ、Ｃが、ディストリビュータＤおよびその共有値ｓｉを受け入れる。
【００７１】
５．１つの指標ｉをもつ参加ネットワーク装置Ａ、Ｂ、Ｃが妥当な共有値ｓｉをまだ受信していない場合、その装置はコンプレイン・メッセージをすべての参加ネットワーク装置Ａ、Ｂ、Ｃに送信する。そのようなコンプレイン・メッセージを受信するとすぐ、指標ｊをもつ受信参加ネットワーク装置Ａ、Ｂ、Ｃは、コンプレインしている指標ｉをもつ参加ネットワーク装置Ａ、Ｂ、Ｃにその副次共有値ｓｉｊを送信する。次いでこの参加ネットワーク装置Ａ、Ｂ、Ｃは、検証テーブルを使用して副次共有値ｓｉｊを検証し、妥当な共有値を組み合わせてｓｉを得る。
【００７２】
通信の複雑さの最適化
ディストリビュータＤによって同報通信された検証テーブルを含む検証メッセージｖｍは、比較的大きいものであり、いくつかの方法で最適化することができる。以下に、より廉価な同報通信プリミティブ、ならびにより小さな検証値を使用するために、どのようにプロトコルが修正できるかを説明する。
【００７３】
・指標ｉをもつ各参加ネットワーク装置Ａ、Ｂ、Ｃは、表１の行ｉおよび列ｉだけ、すなわちすべてのｊに対するｓｉｊおよびｓｊｉと、対応する検証値Ｃ（ｓｉｊ）およびＣ（ｓｊｉ）を受け取る。さらに、各参加ネットワーク装置ＡＢＣは、各行および各列上のハッシュ値、ならびにＣ（ｓｊ０）およびＣ（ｓ０ｊ）（ｓｊ０は、ｓｊ１,...,ｓｊｎによって共有される値）を受け取る。これらの値は、一貫した形で同報通信されないこともある。すなわち、ディストリビュータＤが不正直な場合、すべての参加ネットワーク装置Ａ、Ｂ、Ｃは、異なる値を取得する可能性がある。
【００７４】
・共有メッセージｓｍおよび検証メッセージｖｍを受信するとすぐに、各参加ネットワーク装置Ａ、Ｂ、Ｃは、受信したハッシュ値および検証値を検証し、必要なら、すなわちそれらの値が共有値ｓｊ０およびｓ０ｊ、ならびに副次共有値ｓｉｊおよびｓｊｉに対応しない場合には、検証値Ｃ（ｓｊ０）、Ｃ（ｓ０ｊ）、Ｃ（ｓｉｊ）およびＣ（ｓｊｉ）を再計算する。
【００７５】
・それぞれの参加ネットワーク装置Ａ、Ｂ、Ｃは、指標ｊをもつ参加ネットワーク装置Ａ、Ｂ、Ｃに対して、副次共有値ｓｉｊおよびｓｊｉをすべてのハッシュ値および（たぶん再計算済みの）検証値と一緒に送信する。
【００７６】
・それぞれの参加ネットワーク装置Ａ、Ｂ、Ｃは、十分に多くの、すなわち少なくとも２ｔ＋１個の、ハッシュ値に一致し前記ハッシュ値に対応する妥当な副次共有値ｓｉｊおよびｓｊｉを含む上記メッセージを受信するまで待つ。次いで、その装置は、各参加ネットワーク装置Ａ、Ｂ、ＣにＯＫメッセージを送信する。
【００７７】
・十分に多くの、すなわち少なくとも２ｔ＋１個のＯＫメッセージを受信するとすぐに、各参加ネットワーク装置Ａ、Ｂ、Ｃは、ディストリビュータＤを受け入れる。必要なら副次共有値ｓｉｊから共有値ｓｉを計算する。
【００７８】
通信の複雑さを最適化する上記方法は、ディストリビュータＤが受け入れられたかどうかの合意を保証するものでないことに留意されたい。参加ネットワーク装置Ａ、Ｂ、Ｃのあるものは、プロトコルを終了していないが、あるものは終了している可能性がある。しかしながら、現在のプロトコルの終わりにビザンチン合意プロトコルを追加し、１つの参加ネットワーク装置Ａ、Ｂ、ＣがディストリビュータＤおよびその共有値ｓｉを受け入れる場合、指標ｊをもつすべての正直な参加ネットワーク装置Ａ、Ｂ、Ｃが、ディストリビュータＤを受け入れその共有値ｓｊを受信するようにするのが直截的である。
【００７９】
同報通信のない場合
同報通信なしでプロトコルを実施し、検証可能なシークレット共有のためのプロトコルを信頼性のある同報通信と統合することが可能である。この方法は、一貫した同報通信が使用されないので、通信負荷および計算負荷がさらに低減するという利点がある。一貫した同報通信には複雑なディジタル署名計算が必要となるが、それが回避される。
【００８０】
図３に、同報通信のない、かかる非同期式の検証可能なシークレット共有スキームの概略図を示す。同じ部品記号または参照番号を、同一または同様な部品を示すのに使用している。
【００８１】
この場合、プロトコルは、３回のメッセージ交換を使用している。
ボックス１０に示すように、ディストリビュータＤは、リニア・シークレット共有スキームを適用することにより、シークレット値ｘの共有値ｓｉおよび副次共有値ｓｉｊを導き出す。さらに、ディストリビュータＤは、共有値ｓｉおよび副次共有値ｓｉｊの妥当性の検証に使用可能な検証値
【００８２】
【数１９】
2004525466.tif 000022
を導き出す。次のステップ、ボックス２２で、対応する副次共有値ｓＡｉ、ｓｉＡ、ｓＢｉ、ｓｉＢ、ｓＣｉ、ｓｉＣと検証値
【００８３】
【数２０】
2004525466.tif 000023
とを含む第１のメッセージ（１ｓｔ）が、各参加ネットワーク装置Ａ、Ｂ、Ｃに送信される。
【００８４】
少なくとも２ｔ＋１台の参加ネットワーク装置Ａ、Ｂ、Ｃについて、指標ｉをもつ各参加ネットワーク装置Ａ、Ｂ、Ｃごとに以下のステップｉ）ないしｖｉｉ）が実施される。
【００８５】
ｉ）ディストリビュータＤから第１のメッセージ（１ｓｔ：）を受信した、指標ｉをもつ各参加ネットワーク装置Ａ、Ｂ、Ｃは、ボックス３２に示すように、検証値
【００８６】
【数２１】
2004525466.tif 000024
に基づいて、ｉ＝１,...,ｎおよびｊ＝１,...,ｎに対する副次共有値ｓｉｊ、ｓｊｉすべての妥当性を判定する。
【００８７】
ｉｉ）判定結果が肯定的な場合、指標ｉをもつ参加ネットワーク装置は、受信した副次共有値ｓｉｊ、ｓｊｉから、指標ｍをもつ他の参加ネットワーク装置Ａ、Ｂ、Ｃと共通の関連した副次共有値ｓｉｍ、ｓｍｉを導き出す。次いで、ボックス３４に示すように、指標ｉをもつ参加ネットワーク装置は、指標ｍをもつ各参加ネットワーク装置Ａ、Ｂ、Ｃに、ｒ＝１,...,ｎおよびｊ＝１,...,ｎに対する検証値
【００８８】
【数２２】
2004525466.tif 000025
および関連した副次共有値ｓｉｍ、ｓｍｉを含む第２のメッセージ（２ｎｄ）を送信する。
【００８９】
ｉｉｉ）指標ｊをもつ１つの参加ネットワーク装置Ａ、Ｂ、Ｃから第２のメッセージ（２ｎｄ：）を受信した場合、ボックス４２で示すように、指標ｉをもつ参加ネットワーク装置Ａ、Ｂ、Ｃは、検証値
【００９０】
【数２３】
2004525466.tif 000026
に基づいて、受信した副次共有値ｓｉｊ、ｓｊｉの妥当性を判定する。
【００９１】
ｉｖ）ボックス４４に示すように、２ｔ＋１個の受信した第２のメッセージ（２ｎｄ：）に対する判定結果が肯定的な場合には、ボックス４６に示すように、検証値
【００９２】
【数２４】
2004525466.tif 000027
および関連した副次共有値ｓｉｍ、ｓｍｉを含む第３のメッセージ（３ｒｄ）が、指標ｍをもつ各参加ネットワーク装置Ａ、Ｂ、Ｃに送信される。第１のメッセージ（１ｓｔ：）が受信されない場合には、９２のラベル付きの矢印で示すように、関連した副次共有値ｓｉｍ、ｓｍｉは、受信した第２のメッセージ（２ｎｄ：）から導き出される。
【００９３】
ｖ）第３のメッセージ（３ｒｄ：）を、指標ｊをもつ１つの参加ネットワーク装置Ａ、Ｂ、Ｃから受信した場合、ボックス５２に示すように、検証値
【００９４】
【数２５】
2004525466.tif 000028
に基づいて受信した副次共有値ｓｉｊ、ｓｊｉの妥当性を判定する。
【００９５】
ｖｉ）ボックス５４に示すように、ｔ＋１個の受信した第３のメッセージ（３ｒｄ：）について判定結果が肯定的で、第３のメッセージ（３ｒｄ）をまだ送信していない場合には、ボックス５６に示すように、検証値
【００９６】
【数２６】
2004525466.tif 000029
および関連した副次共有値ｓｉｍ、ｓｍｉを含む１つの第３のメッセージ（３ｒｄ）が指標ｍをもつ各参加ネットワーク装置Ａ、Ｂ、Ｃに送信される。第１のメッセージ（１ｓｔ：）をまだ受信していない場合には、受信した第３のメッセージ（３ｒｄ：）について９４のラベル付きの矢印で示すように、関連した副次共有値ｓｉｍ、ｓｍｉが、受信した第２または第３のメッセージ（２ｎｄ：、３ｒｄ：）から導き出される。
【００９７】
ｖｉｉ）ボックス５８に示すように、２ｔ＋１個の受信した第３のメッセージについて判定結果が肯定的な場合には、ボックス８０に示すように、共有値ｓｉが、受信した第１、第２、または第３のメッセージ（１ｓｔ：、２ｎｄ：、３ｒｄ：）から導き出される。これは、ディストリビュータＤからの共有値ｓｉが受け入れられたことを意味する。
【００９８】
このより効率の良いプロトコルを、コミットメントを使用する方法、および通信の複雑さを最適化する方法と組み合わせることができる。その結果もたらされるプロトコルには、通信および計算の複雑さがさらに低減するという利点がある。それにはまた、ディストリビュータＤが受け入れられたかどうかの合意を確実にし、その結果、他のすべての参加ネットワーク装置Ａ、Ｂ、Ｃが終了する場合に限って、各参加ネットワーク装置Ａ、Ｂ、Ｃが、終了するという利点がある。
【００９９】
複合的な敵構造
破壊されたｎのうちのｔを固定閾値にする代わりに、現実の世界の構造を反映させることにより柔軟性をより高めることが可能である。
【０１００】
例えば、敵がある種のオペレーティング・システムをもつすべての参加ネットワーク装置を制御できる場合もあり、あるいは敵がシステム管理者を買収して特定のサイトのすべての参加ネットワーク装置に対するアクセス権を取得する場合もある。敵構造は、かかる攻撃スキームに対処している。
【０１０１】
敵構造Ｔを定義するには、システムがその破壊を許容すべきあらゆるパーティの連携、例えば同じオペレーティング・システムをもつすべての参加ネットワーク装置の連携を定義しなければならない。そうした場合、これらの集合すべての集合が敵構造Ｔになる。
【０１０２】
図４は、構造化された形で分布する１９サイトの参加ネットワーク装置Ｐ１〜Ｐ１９のシナリオ、すなわち各参加ネットワーク装置Ｐ１〜Ｐ１９が、オペレーティング・システムＯＳ−１〜ＯＳ−４を有し、国Ｃ１〜Ｃ４内にロケーションを有することを示すものである。従来のｎのうちのｔという構造によって、６台の（ビザンチン）障害をもつ参加ネットワーク装置からなるどんな集合も、許容することができる。対応する敵構造を使用して、１つのオペレーティング・システムおよび１つのロケーションの同時障害を許容することができる。この例では、これは最高１０台までの参加ネットワーク装置（例えば、第４の国Ｃ４内の、または第１のオペレーティング・システムＯＳ−１をもつ参加ネットワーク装置すべての障害）となることがあり、あるいは破壊の分布が良い場合、すなわち４台の参加ネットワーク装置がすべての国とすべてのオペレーティング・システムをカバーする場合には、４台未満となることもある。
【０１０３】
シークレットｘを共有するためのプロトコルでは、いくつかの種類の障害が同時に起こる可能性がある。例えば、クラッシュ障害ＣＦ、ビザンチン障害ＢＦ、およびリンク障害ＬＦの間では違いがある。これにより、より大きい障害の全体数が許容される。
【０１０４】
本発明は、ハードウェア、ソフトウェア、またはハードウェアとソフトウェアの組合せの形で実現することができる。どのようなコンピュータ・システム（または本明細書に記載の方法を実施するようになされた他の機器）にも適用可能である。典型的なハードウェアとソフトウェアの組合せは、ロードされ実行されると、本明細書に記載の方法を実行するようにコンピュータ・システムを制御するコンピュータ・プログラムを備える汎用コンピュータ・システムであろう。本発明はまた、本明細書に記載の方法の実施を可能にするすべての特徴を備え、（コンピュータ・システムにロードされたとき）これらの方法を実行することのできるコンピュータ・プログラム製品に埋め込むこともできる。
【０１０５】
コンピュータ・プログラム手段あるいは本発明の文脈中のコンピュータ・プログラムは、情報処理能力を有するシステムに、そのまま、あるいはａ）他の言語、コードまたは表記法への変換、ｂ）異なる材料形態への複製のいずれかまたは両方の後で、特定の機能を実施させるように意図した命令セットの任意の言語、コード、または表記法による任意の表現を意味する。
【図面の簡単な説明】
【０１０６】
【図１】複数の参加ネットワーク装置およびディストリビュータを含む典型的な非同期式ネットワークを示す図である。
【図２】非同期式の検証可能なシークレット共有スキームの概略図である。
【図３】同報通信なしの非同期式の検証可能なシークレット共有スキームの概略図である。
【図４】参加ネットワーク装置が構造化された形で分布するシナリオを示す図である。
【図１】
2004525466.tif 000052
【図２】
2004525466.tif 000053
【図３】
2004525466.tif 000054
【図４】
2004525466.tif 000055
【国際公開パンフレット】
2004525466.tif 000056
2004525466.tif 000057
2004525466.tif 000058
2004525466.tif 000059
2004525466.tif 000060
2004525466.tif 000061
2004525466.tif 000062
2004525466.tif 000063
2004525466.tif 000064
2004525466.tif 000065
2004525466.tif 000066
2004525466.tif 000067
2004525466.tif 000068
2004525466.tif 000069
2004525466.tif 000070
2004525466.tif 000071
2004525466.tif 000072
2004525466.tif 000073
2004525466.tif 000074
2004525466.tif 000075
2004525466.tif 000076
2004525466.tif 000077
2004525466.tif 000078
2004525466.tif 000079
2004525466.tif 000080
2004525466.tif 000081
2004525466.tif 000082
2004525466.tif 000083
【国際調査報告】
2004525466.tif 000084
2004525466.tif 000085
2004525466.tif 000086