(57)【特許請求の範囲】
【請求項１】
暗号化のための値のシェアを生成する方法であって、前記方法は、複数のサーバを含むシステムによって実行され、
前記方法は、
（ａ）前記暗号化のための値のシェアを生成するために前記複数のサーバの中から複数の参加サーバのグループを確立することと、
（ｂ）前記複数の参加サーバが、第１、第２、第３のプロトコルのプロセスを起動することであって、（ｉ）前記第１のプロトコルは、前記複数の参加サーバに、数Ｎを計算させ、（ｉｉ）前記第２のプロトコルは、前記複数の参加サーバに、Ｎの素因数を前記複数の参加サーバに見せることなく、二重素数性条件に対して値Ｎをテストさせ、（ｉｉｉ）前記第３のプロトコルは、前記複数の参加サーバに、前記暗号化のための値を前記複数の参加サーバに見せることなく、前記暗号化のための値のシェアを計算させ、（ｉｖ）前記プロセスは、前記複数のサーバのうちの少なくとも１つがプロトコルから逸脱したか否かを検出するための手続を含む、ことと、
（ｃ）前記複数の参加サーバが、前記プロトコルを実行する前記プロセスを開始することと、
（ｄ）前記複数の参加サーバが、前記複数の参加サーバのうちの少なくとも１つが前記第１、第２、第３のプロトコルのうちのいずれから逸脱したか否かをチェックすることと
を含み、
前記第１、第２、第３のプロトコルは、前記複数の参加サーバのうちの各参加サーバに、少なくとも１つの検証シェアを前記複数の参加サーバのうちのその他の参加サーバに提供させる、方法。
【請求項２】
リバイズされた複数のサーバは、前記初期の複数の参加サーバが前記第３のプロトコルを完了する前に、前記プロセスを再スタートする、請求項１に記載の方法。
【請求項３】
Ｎは、ＲＳＡモデュラスであり、前記暗号化のための値は、ＲＳＡ鍵である、請求項１に記載の方法。
【発明の詳細な説明】
【０００１】
本出願は、エレクトロニクスおよびデータプロセシングの分野に関し、特に暗号鍵を生成する方法および装置に関する。
【０００２】
（背景）
分散型暗号プロトコルという考え方は、暗号化技術の分野において１５年間にわたって存在してきた。いくつかのプロトコルが、ｃｏｉｎ−ｆｌｉｐｐｉｎｇ  ｐｒｏｔｏｃｏｌプロトコル［Ｂ８２］およびｍｉｌｌｉｏｎａｉｒｅ−ｐｒｏｂｌｅｍプロトコル［Ｙ８２］などの情報理論の観点から見て不可能な通信の問題を解消するために設計されてきた。一般的な問題を解消するために設計されてきたプロトコルもある。これらのプロトコル（「汎用コンパイラプロトコル」と呼ばれる）は、セキュアな入力が行われる際、あらゆる公開関数（ｐｕｂｌｉｃ  ｆｕｎｃｔｉｏｎ）をセキュアに計算することができる。このようなプロトコルを最初に開発したのはＹａｏ［Ｙ８６］およびＧｏｌｄｒｅｉｃｈ、ＭｉｃａｌｉおよびＷｉｇｄｅｒｓｏｎ［ＧＭＷ］であり、その後の研究において［ＧＨＹ、Ｋ、ＢＧＷ、ＣＣＤ］などの様々な開発が行われた。
【０００３】
近年、暗号化関数（ｃｒｙｐｔｏｇｒａｐｈｉｃ）の分散型アプリケーション（ＧＷ９７中で調査）に関連する問題に対し、より効率的なプロトコルを構築しようという動きが活発になっている。関数シェア型プロトコルは、権限認証およびグループ署名のような重要な関数に関して、メモリのセキュリティの増強、分散した信頼性、および柔軟な管理（すなわち、管理担当者を増減すること）を提供する必要がある。
【０００４】
汎用コンパイラプロトコル（これは一応は信頼出来そうな結果として考えられはずである−［Ｇｒ９７］を参照のこと）と関数シェア型プロトコルとの間の主な効率差は、前者の通信複雑性が暗号関数を計算する回路の実際のサイズに直線的に依存するのに対し、後者の通信複雑性は回路サイズの影響を受けない（そして、典型的には入力／出力サイズおよび参加者数を用いた多項式である）という点から生じる。この差（最初に指摘したのはＦＹ９３およびＤＤＦＹ９４である）は、効率的なプロトコルを必要とする実務家にとって極めて重要である。関数シェア型プロトコルは、（分散したシェアに基づいて）関数を用いるプロトコルを含み、時には（いわゆる「事前対応型（ｐｒｏａｃｔｉｖｅ）モデル」において）関数シェアを再度乱数化するプロトコルも含む。
【０００５】
「分散型暗号関数」に関する別の重要な工程は、関数（鍵シェア）を（効率的に）分散型生成することである。フィールド（この逆関数が一方向関数であると仮定される離散対数である）をモジュラー指数関数化する工程に基づく暗号化関数に対して、鍵を分散型生成するプロトコルは公知であった［Ｐ２］。しかし、以下に説明するＲＳＡ関数および関連する暗号化関数は、２つの素数の積および公開指数（ｐｕｂｌｉｃ  ｅｘｐｏｎｅｎｔ）の逆数を生成する工程を必要とし、これにより、上記工程は長年未解決の問題であった。Ｙａｏ［Ｙ８６］の主たる動機は、「コンピュータ回路をセキュアに通信させる」ことがＲＳＡ鍵を分散生成する際の争点（ｉｓｓｕｅ）であった汎用コンパイラプロトコルを導入することである点に留意されたい。実際、［Ｙ８６、ＧＭＷ］の結果は、この課題に対して一応は信頼できそうな結果を示している。
【０００６】
別の工程が、ＢｏｎｅｈおよびＦｒａｎｋｌｉｎ［ＢＦ９７］により達成された。彼らは、一組の参加者がＲＳＡ関数を効率的に生成することが可能な方法を示し、これにより非効率的なコンパイラを回避した。ＢｏｎｅｈおよびＦｒａｎｋｌｉｎは、自身によるプロトコルが「信用されているが好奇心に富む」当事者の限定されたモデルにおいてセキュアであることを実証した。ＢｏｎｅｈおよびＦｒａｎｋｌｉｎは、ロバスト性の問題（すなわち不正を働く（悪意を有する）当事者の面前で生成を行う際の問題）を未解決のまま放置した。敵対者が自由に不正を行えば、Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎプロトコルは（ロバスト性の欠如が理由で）シェア型ＲＳＡキーを生成することができなくなり得る。
【０００７】
以下の参考文献は、本発明についてのさらなる背景を提供する。
【０００８】
［ＡＣＧＳ］  Ｗ．Ａｌｅｘｉ、Ｂ．Ｃｈｏｒ、Ｏ．ＧｏｌｄｒｅｉｃｈおよびＣ．Ｓｃｈｎｏｒｒ、ＲＳＡ  ａｎｄ  Ｒａｂｉｎ  Ｆｕｎｃｔｉｏｎｓ：  Ｃｅｒｔａｉｎ  Ｐａｒｔｓ  ａｒｅ  ａｓ  Ｈａｒｄ  ａｓ  ｔｈｅ  Ｗｈｏｌｅ、ＳＩＡＭ  Ｊｏｕｎａｌ  ｏｆ  Ｃｏｍｐｕｔｉｎｇ、ｖｏｌｕｍｅ１７、ｎ．２、１９４−２０９頁、  １９８８年４月．
［Ｂ８４］  Ｅ．Ｂａｃｈ、「Ｄｉｓｃｒｅｔｅ  Ｌｏｇａｒｉｔｈｍｓ  ａｎｄ  Ｆａｃｔｏｒｉｎｇ」、Ｔｅｃｈ．  Ｒｅｐｏｒｔ  Ｎｏ．ＵＣＢ／ＣＳＯ  ８４／１８６、Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  Ｄｉｖｉｓｉｏｎ  （ＥＥＣＳ）、Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｃａｌｉｆｏｒｎｉａ、Ｂｅｒｋｅｌｅｙ、ＣＡ、  １９８４年６月
［ＢＧＷ］  Ｂｅｎ−Ｏｒ  Ｍ．、  Ｓ．Ｇｏｌｄｗａｓｓｅｒ  および  Ａ．  Ｗｉｇｄｅｒｓｏｎ、  Ｃｏｍｐｌｅｔｅｎｅｓｓ  Ｔｈｅｏｒｅｍ  ｆｏｒ  Ｎｏｎ  ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｆａｕｌｔ−ｔｏｌｅｒａｎｔ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｃｏｍｐｕｔｉｎｇ、  ＳＴＯＣ  １９８８、  ＡＣＭ、  ｐｐ．１−１０．
［Ｂ８２］  Ｍ．Ｂｌｕｍ、  「Ｃｏｉｎ  ｆｌｉｐｐｉｎｇ  ｂｙ  ｔｅｌｅｐｈｏｎｅ：  ａ  ｐｒｏｔｏｃｏｌ  ｆｏｒ  ｓｏｌｖｉｎｇ  ｉｍｐｏｓｓｉｂｌｅ  ｐｒｏｂｌｅｍｓ」、  ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ  Ｃｏｎｆｅｒｅｎｃｅ  １９８２、  １３３−１３７
［ＢＦ９７］  Ｄ．Ｂｏｎｅｈ  および  Ｍ．  Ｆｒａｎｋｌｉｎ、  Ｅｆｆｉｅｃｉｅｎｔ  Ｇｅｎｅｒａｔｉｏｎ  ｏｆ  Ｓｈａｒｅｄ  ＲＳＡ  Ｋｅｙｓ、  Ｃｒｙｐｔｏ  ９７、  ｐｐ．４２５−４３９．
［Ｂ８８］  Ｃ．Ｂｏｙｄ、  Ｄｉｇｉｔａｌ  Ｍｕｌｔｉｓｉｇｎａｔｕｒｅｓ、  ＩＭＡ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｒｙｐｔｏｇｒａｐｈｙ  ａｎｄ  Ｃｏｄｉｎｇ、  Ｃｌａｒｅｄｏｎ  Ｐｒｅｓｓ、  ２４１−２４６  （ｅｄｓ．  Ｈ．  Ｂａｋｅｒ  および  Ｆ．  Ｐｉｅｒ）、  １９８６．
［ＢＣＬＬ］  Ｇ．  Ｂｒａｓｓａｒｄ、  Ｃ．  Ｃｒｅｐｅａｕ、  Ｓ．  Ｌａｐｌａｎｔｅ、  Ｃ．  Ｌｅｇｅｒ、  Ｃｏｍｐｕｔａｔｉｏｎａｌｌｙ  Ｃｏｎｖｉｎｃｉｎｇ  ｐｒｏｏｆｓ  ｏｆ  ｋｎｏｗｌｅｄｇｅ、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ８th  Ｓｙｍｐ．  Ｏｎ  Ｔｈｅｏｒｅｔｉｃａｌ  Ａｓｐｅｃｔｓ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  （Ｓｐｒｉｎｇｅｒ、  Ｂｅｒｌｉｎ、  １９９１）、  ｐｐ．  ２５１−２６２
［ＢＧＭ］  Ｅ．  Ｂｒｉｋｅｌｌ、  Ｄ．  ＧｏｒｄｏｎおよびＫ．  ＭｃＣｕｒｌｒｙ、  Ｆａｓｔ  Ｅｘｐｏｎｅｎｔｉａｔｉｏｎ  ｗｉｔｈ  Ｐｒｅｃｏｍｐｕｔａｔｉｏｎ  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −  Ｅｕｒｏｃｒｙｐｔ  ９２  Ｐｒｏｃｅｅｄｉｎｇｓ、  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ、  Ｖｏｌ．６５８、  Ｒ．  Ｒｕｅｐｐｅｌ  ｅｄ．、  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ、  １９９２  ［ＣＣＤ］  Ｄ．  Ｃｈａｕｍ、  Ｃ．  ＣｒｅｐｅａｕおよびＩ．  Ｄａｍｇａｒｄ、  Ｍｕｌｔｉｐａｒｔｙ  Ｕｎｃｏｎｄｉｔｉｏｎａｌｌｙ  Ｓｅｃｕｒｅ  Ｐｒｏｔｏｃｏｌｓ、  ＳＴＯＣ  １９８８、  ＡＣＭ、  ｐｐ．１１−１９．
［ＣＥＧ］  Ｄ．  Ｃｈａｕ、  Ｍ．−Ｈ．  ＥｖｅｒｔｓｅおよびＪ．ｖａｎ  ｄｅ  Ｇｒａｆｆ、  Ｍｕｌｔｉｐａｒｔｙ  ｃｏｍｐｕｔａｔｉｏｎｓ  ｅｎｓｕｒｉｎｇ  ｐｒｉｖａｃｙ  ｏｆ  ｅａｃｈ  ｐａｒｔｙ’ｓ  ｉｎｐｕｔ  ａｎｄ  ｃｏｒｒｅｃｔｎｅｓｓ  ｏｆ  ｔｈｅ  ｒｅｓｕｌｔ、  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −  Ｅｕｒｏｐｃｒｙｐｔ  ８８  Ｐｒｏｃｅｅｄｉｎｇｓ、  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ、  Ｖｏｌ．  ３３０、  Ｃ．  Ｇｕｎｔｈｅｒ  ｅｄ．、  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ、１９８８  ｐｐ．  ８７−１１９
［ＣＥＧＰ］  Ｄ．  Ｃｈａｕｍ、  Ｊ．−Ｈ．  Ｅｖｅｒｔｓｅ、  Ｊ  ｖａｎ  ｄｅ  ＧｒａａｆおよびＲ．  Ｐｅｒａｌｔａ、  Ａｎ  ｉｍｐｒｏｖｅｄ  ｐｒｏｔｏｃｏｌ  ｆｏｒ  ｄｅｍｏｎｓｔｒａｔｉｎｇ  ｐｏｓｓｅｓｓｉｏｎ  ｏｆ  ｄｉｓｃｒｅｔｅ  ｌｏｇａｒｉｔｈｍｓ  ａｎｄ  ｓｏｍｅ  ｇｅｎｅｒａｌｉｚａｔｉｏｎｓ、  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −  Ｃｒｙｐｔｏ  ８６  Ｐｒｏｃｅｅｄｉｎｇｓ、  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ、  Ｖｏｌ．  ２６３、  Ａ．  Ｏｄｌｙｚｋｏ  ｅｄ．、  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ、  １９８６、  ｐｐ．  ２００−２１２．
［ＣＧＭＡ］  Ｂ．  Ｃｈｏｒ、  Ｓ．  Ｇｏｌｄｗａｓｓｅｒ、  Ｓ．  ＭｉｃａｌｉおよびＢ．  Ａｗｅｒｂｕｃｈ、  Ｖｅｒｉｆｉａｂｌｅ  Ｓｅｃｒｅｔ  Ｓｈａｒｉｎｇ  ａｎｄ  Ａｒｃｈｉｖｉｎｇ  Ｓｉｍｕｌｔａｎｅｏｕｓ  Ｂｒｏａｄｃａｓｔ、  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２６th  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｆｏｕｎｄａｔｉｏｎｓ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ、  ＩＥＥＥ、  １９８５、  ｐｐ．  ３３５−３４４．
［ＤＤＦＹ９４］  Ａ．  Ｄｅｓａｎｔｉｓ、  Ｙ．  Ｄｅｓｍｅｄｔ、  Ｙ．  ＦｒａｎｋｅｌおよびＭ．  Ｙｕｎｇ、  Ｈｏｗ  ｔｏ  Ｓｈａｒｅ  ａ  Ｆｕｎｃｔｉｏｎ  Ｓｅｃｕｒｅｌｙ、  ＡＣＭ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２６th  Ａｎｎｕａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｔｈｅｏｒｙ  ｏｆ  Ｃｏｍｐｕｔｉｎｇ、  ＡＣＭ、  １９９４、  ｐｐ．  ５２２−５３３．
［ＤＦ８９］  Ｙ．  ＤｅｓｍｅｄｔおよびＹ．  Ｆｒａｎｋｅｌ、  Ｔｈｒｅｓｈｏｌｄ  ｃｒｙｐｔｏｓｙｓｔｅｍｓ、  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −  Ｃｒｙｐｔｏ  ８９  Ｐｒｏｃｅｅｄｉｎｇｓ、  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ、  Ｖｏｌ．  ４３５、  Ｇ．  Ｂｒａｓｓａｒｄ  ｅｄ．、  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ、  １９８９、  ｐｐ．  ３０７−３１５．
［ＤＨ］  Ｗ．  ＤｉｆｆｌｅおよびＭ．  Ｈｅｌｌｍａｎ、  Ｎｅｗ  Ｄｉｒｅｃｔｉｏｎｓ  ｉｎ  Ｃｒｙｐｔｏｇｒａｐｈｙ、  ＩＥＥＥ  Ｔｒａｎｓ、  Ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ  ２２（６）、  １９７６、  ｐｐ．  ６４４−６５４．
［ＦＦＳ］  Ｕ．  Ｆｅｉｇｅ、  Ａ．  Ｆｉａｔ  ａｎｄ  Ａ．  Ｓｈａｍｉｒ、  Ｚｅｒｏ−Ｋｎｏｗｌｅｄｇｅ  Ｐｒｏｏｆ  ｏｆ  Ｉｄｅｎｔｉｔｙ、  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｎｉｎｅｔｅｅｎｔｈ  ａｎｎｕａｌ  ＡＣＭ  ｓｙｍｐ．  Ｔｈｅｏｒｙ  ｏｆ  Ｃｏｍｐｕｔｉｎｇ、  １９８７、  ｐｐ．  ２１０−２１７．
［Ｆ］  Ｐ．  Ｆｅｌｄｍａｎ、  Ａ  Ｐｒａｃｔｉｃａｌ  Ｓｃｈｅｍｅ  ｆｏｒ  Ｎｏｎ−Ｉｎｔｅｒａｃｔｉｖｅ  Ｃｅｒｔｉｆｉａｂｌｅ  Ｓｅｃｒｅｔ  Ｓｈａｒｉｎｇ、  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２８th  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｆｏｕｎｄａｔｉｏｎｓ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ、  ＩＥＥＥ、  １９８７、  ｐｐ．  ４２７−４３７．
［ＦＳ８６］  Ａ．  Ｆｉａｔ  ａｎｄ  Ａ．  Ｓｈａｍｉｒ、  「Ｈｏｗ  ｔｏ  ｐｒｏｖｅ  ｙｏｕｒｓｅｌｆ：  Ｐｒａｃｔｉｃａｌ  ｓｏｌｕｔｉｏｎｓ  ｔｏ  ｉｄｅｎｔｉｆｉｃａｔｉｏｎ  ａｎｄ  ｓｉｇｎａｔｕｒｅ  ｐｒｏｂｌｅｍｓ」、  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −  ＣＲＹＰＴＯ  ’８６  Ｐｒｏｃｅｅｄｉｎｇｓ  （Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ、  Ｖｏｌ．  ２６３）、  ｅｄ．  Ａ．  Ｏｄｌｙｚｋｏ  １８６−１９４、  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ、  Ｎｅｗ  Ｙｏｒｋ、  １９８７．
［ＦＧＹ］  Ｙ．  Ｆｒａｎｋｅｌ、  Ｐ．  ＧｅｍｍｅｌｌおよびＭ．  Ｙｕｎｇ、  Ｗｉｔｎｅｓｓ  Ｂａｓｅｄ  Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｐｒｏｇｒａｍ  Ｃｈｅｃｋｉｎｇ  ａｎｄ  Ｒｏｂｕｓｔ  Ｆｕｎｃｔｉｏｎ  Ｓｈａｒｉｎｇ、  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２８th  Ａｎｎｕａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｔｈｅｏｒｙ  ｏｆ  Ｃｏｍｐｕｔｉｎｇ、  ＡＣＭ  １９９６、  ｐｐ．  ４９９−５０８．
［ＦＧＭＹ］  Ｙ．  Ｆｒａｎｋｅｌ、  Ｐ．  Ｇｅｍｍｅｌ、  Ｐ．  ＭａｃＫｅｎｚｉｅおよびＭ．  Ｙｕｎｇ、  Ｐｒｏａｃｔｉｖｅ  ＲＳＡ、  Ｃｒｐｔｏ  ９７．
［ＦＧＭＹａ］  Ｙ．  Ｆｒａｎｋｅｌ、  Ｐ．  Ｇｅｍｍｅｌ、  Ｐ．  ＭａｃＫｅｎｚｉｅおよびＭ．  Ｙｕｎｇ、  Ｏｐｔｉｍａｌ  Ｒｅｓｉｌｉｅｎｃｅ  Ｐｒｏａｃｔｉｖｅ  Ｐｕｂｌｉｃ−Ｋｅｙ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ、  ＦＯＣＳ  ９７．
［ＦＳ８９］  Ｕ．  ＦｅｉｇｅおよびＡ．  Ｓｈａｍｉｒ、  Ｚｅｒｏ  Ｋｎｏｌｅｄｇｅ  ｐｒｏｏｆ  ｏｆ  ｋｎｏｗｌｅｄｇｅ  ｉｎ  ｔｗｏ  ｐｏｕｎｄｓ、  ＣＲＹＰＴＯ  １９８９、  ２０−２４．
［ＦＹ９３］  Ｍ．  ＦｒａｎｋｌｉｎおよびＭ．  Ｙｕｎｇ、  Ｓｅｃｕｒｅ  ａｎｄ  Ｅｆｆｉｅｃｉｅｎｔ  Ｏｆｆｌｉｎｅ  Ｄｉｇｉｔａｌ  Ｍｏｎｅｙ、  Ｐｏｒｃｈ．  Ｏｆ  ｔｈｅ  ２０th  Ｉｎｔ．  Ｃｏｌ．  Ｏｎ  Ａｕｔｏｍａｔａ、  Ｌａｎｇｕａｇｅｓ  ａｎｄ  Ｐｒｏｇｒａｍｍｉｎｇ  （ＩＣＡＬＰ）、  １９９３、  ＬＮＣＳ  ７００、  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ、  ｐｐ．  ２６５−２７６．
［ＧＨＹ］  Ｚ．  Ｇａｌｉｌ、  Ｓ．  Ｈａｂｅｒ、およびＭ．  Ｙｕｎｇ、  Ｍｉｎｉｍｕｍ  −Ｋｎｏｗｌｅｄｇｅ  Ｉｎｔｅｒａｃｔｉｖｅ  Ｐｒｏｏｆ  ｆｏｒ  Ｄｅｃｉｓｉｏｎ  Ｐｒｏｂｌｅｍｓ、  ＳＩＡＭ  ｊ、  Ｃｏｍｐ．、  １８、  ９１８９、  ｐｐ．  ７１１−７３９．
［ＧＨＹ８５］  Ｚ．  Ｇａｌｉｌ、  Ｓ．  ＨａｂｅｒおよびＭ．  Ｙｕｎｇ、Ｓｙｍｍｅｔｒｉｃ  Ｐｕｂｌｉｃ−Ｋｅｙ  Ｃｒｙｐｔｏｇｒａｐｈｙ，Ｃｒｙｐｔｏ  ８５．
［ＧＨＹ８７］  Ｚ．  Ｇａｌｉｌ、  Ｓ．  Ｈａｂｅｒ、およびＭ．  Ｙｕｎｇ、Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｃｏｍｐｕｔａｔｉｏｎｓ：  Ｓｅｃｕｒｅ  Ｆａｕｌｔ  Ｔｏｌｅｒａｎｔ  Ｐｒｏｔｏｃｏｌｓ  ｉｎ  ｔｈｅ  Ｐｕｂｌｉｃ  Ｋｅｙ  Ｍｏｄｅｌ、  Ｃｒｙｐｔｏ  ８７、  ｐｐ．  １３５−１５５．
［ＧＪＫＲ］  Ｒ．  Ｇｅｎｎａｒｏ、  Ｓ．  Ｊａｒｅｃｋｉ、  Ｈ．  Ｋｒａｗｃｚｙｋ、  Ｔ．  Ｒａｂｉｎ、  Ｒｏｂｕｓｔ  Ｔｈｅｓｈｏｌｄ  ＤＳＳ  Ｓｉｇｎａｔｕｒｅｓ、  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −  Ｅｕｒｏｃｒｙｐｔ  ９６  Ｐｒｏｃｅｅｄｉｎｇｓ、  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ、  Ｖｏｌ．  １０７０、  Ｕ．  Ｍａｕｒｅｒ  ｅｄ．、  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ、  １９９６、  ｐｐ．  ３５４−３７１．
［Ｇｒ９７］  Ｏ．  Ｇｏｌｄｒｅｉｃｈ、  Ｏｎ  Ｆｏｕｎｄａｔｉｏｎｓ  ｏｆ  Ｍｏｄｅｒｎ  Ｃｒｙｐｔｏｇｒａｐｈｙ、  ａｎ  ｉｎｖｉｔｅｄ  ｐａｐｅｒ、  Ｃｒｙｐｔｏ  ９７．
［ＧＭＷ８６］  Ｏ．  Ｇｏｌｄｒｅｉｃｈ、  Ｓ．  ＭｉｃａｌｉおよびＡ．  Ｗｉｇｄｅｒｓｏｎ、  「Ｐｒｏｏｆｓ  ｔｈａｔ  ｙｉｅｌｄ  ｎｏｔｈｉｎｇ  ｂｕｔ  ｔｈｅｉｒ  ｖａｉｌｉｄｉｔｙ  ａｎｄ  ａ  ｍｅｔｈｏｄｏｌｏｇｙ  ｏｆ  ｃｒｙｐｔｏｇｒａｐｈｉｃ  ｐｒｏｔｏｃｏｌ  ｄｅｓｉｇｎ」、  ＩＥＥＥ  ＦＯＣＳ  １９８６、  ｐｐ．  １７４−１８７．
［ＧＭＷ］  Ｏ．  Ｇｏｌｄｒｅｉｃｈ、  Ｓ．  ＭｉｃａｌｉおよびＡ．  Ｗｉｇｄｅｒｓｏｎ、Ｈｏｗ  ｔｏ  ｐｌａｙ  ａ  ｍｅｎｔａｌ  ｇａｍｅ，  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｎｉｎｅｔｅｅｔｈ  ａｎｎｕａｌ  ＡＣＭ  Ｓｙｍｐ．  Ｔｈｅｏｒｙ  ｏｆ  Ｃｏｍｐｕｔｉｎｇ，  １９８７，  ｐｐ．２１８−２２９．
［Ｇｗ９７］  Ｓ．  Ｇｏｌｄｗａｓｓｅｒ、  Ａ  Ｎｅｗ  Ｄｉｒｅｃｔｉｏｎ  ｉｎ  Ｃｒｙｐｔｏｇｒａｐｈｙ：  Ｔｗｅｎｔｙ  ｓｏｍｅｔｈｉｎｇ  ｙｅａｒｓ  ａｆｔｅｒ、  ａｎ  ｉｎｖｉｔｅｄ  ｐａｐｅｒ、  ＦＯＣＳ  ９７．
［ＧＭＲ］  Ａ．  Ｇｏｌｄｗａｓｓｅｒ、  Ｓ．  ＭｉｃａｌｉおよびＣ．  Ｒａｃｋｏｆｆ、  Ｔｈｅ  Ｋｎｏｗｌｅｄｇｅ  Ｃｏｍｐｌｅｘｉｔｙ  ｏｆ  Ｉｎｔｅｒａｃｔｉｖｅ  Ｐｒｏｏｆ−Ｓｙｓｔｅｍｓ、  Ｓｉａｍ  Ｊ．  ｏｎ  Ｃｏｍｐｕｔｉｎｇ、  １８（１）  （１９８９）、  ｐｐ．  １８６−２０８
［ＨＷ］  Ｇ．  ＨａｒｄｙおよびＥ．  ｗｒｉｇｈｔ、  Ａｎ  ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  ｔｈｅ  ｔｈｅｏｒｙ  ｏｆ  ｎｕｍｂｅｒｓ、  Ｏｘｆｏｒｄ  Ｓｃｉｅｎｃｅ  Ｐｕｂｌｉｃａｔｉｏｎｓ、  Ｌｏｎｄｏｎ、  Ｇｒｅａｔ  Ｂｒｉｔａｉｎ、  ｆｉｆｔｈ  ｅｄ．、  １９８５．
［ＨＪＪＫＹ］  Ａ．  Ｈｅｒｚｂｅｒｇ、  Ｍ．  Ｊａｋｏｂｓｓｏｎ、  Ｓ．  Ｊａｒｅｃｋｉ、  Ｈ．  Ｋｒａｗｃｚｙｋ、  Ｍ．  Ｙｕｎｇ、  Ｐｒｏａｃｔｉｖｅ  Ｐｕｂｌｉｃ−Ｋｅｙ  ａｎｄ  Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅｓ、  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｆｏｕｒｔｈ  Ａｎｎｕａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｓｅｃｕｒｉｔｙ、  ＡＣＭ、  １９９６．
［ＩＹ８７］  Ｒ．  ＩｍｐａｇｌｉａｚｚｏおよびＭ．  Ｙｕｎｇ、  「Ｄｉｒｅｃｔ  ｍｉｎｉｍｕｍ−ｋｎｏｗｌｅｄｇｅ  ｃｏｍｐｕｔａｔｉｏｎ」、Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −  ＣＲＹＰＴＯ  ’８７  Ｐｒｏｃｅｅｄｉｎｇｓ  （Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｅｃｅ、  Ｖｏｌ．２９３）、  ｅｄ．  Ｃ．  Ｐｏｍｅｒａｎｃｅ、  ４０−５１、  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ、  Ｎｅｗ  Ｙｏｒｋ、  １９８８．
［Ｋ］  Ｊ．  Ｋｉｌｉａｎ、  「Ｆｏｕｎｄｉｎｇ  ｃｒｙｐｔｏｇｒａｐｈｙ  ｏｎ  ｏｂｌｉｖｉｏｕｓ  ｔｒａｎｓｆｅｒ」、  ＡＣＭ  ＳＴＯＣ  １９８８、  ２０−３１．
［Ｍ７６］  Ｇ．  Ｍｉｌｌｅｒ、  Ｒｉｅｍａｎｎ’ｓ  Ｈｙｐｏｔｈｅｓｉｓ  ａｎｄ  Ｔｅｓｔ  ｏｆ  Ｐｒｉｍａｌｉｔｙ、  Ｊ．  ｏｆ  Ｃｏｍｐ．  Ａｎｄ  Ｓｙｓｔ．  Ｓｃｉｅｎｃｅｓ、  １３、  ３００−３１７、  １９７６．
［ＯＫ９２］  Ｔ．  Ｏｋａｍｏｔｏ、  Ｐｒｏｖａｂｌｙ  Ｓｅｃｕｒｅ  ａｎｄ  Ｐｒａｃｔｉｃａｌ  Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ  ａｎｄ  Ｃｏｒｒｅｓｐｏｎｄｉｎｇ  Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅ、  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −  Ｃｒｙｐｔｏ  ９２  Ｐｒｏｃｅｅｄｉｎｇｓ、  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  Ｖｏｌ．  ７４０、  Ｅ．  Ｂｒｉｃｋｅｌｌ  ｅｄ．、  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ、  １９９２、  ｐｐ．  ３１−５３．
［ＯＹ９１］  Ｒ．  ＯｓｔｒｏｖｓｋｙおよびＭ．  Ｙｕｎｇ、  Ｈｏｗ  ｔｏ  ｗｉｔｈｓｔａｎｄ  ｍｏｂｉｌｅ  ｖｉｒｕｓ  ａｔｔａｃｋｓ、  Ｐｒｏｃ．  ｏｆ  ｔｈｅ  １０th  ＡＣＭ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  ｔｈｅ  Ｐｒｉｎｃｉｐｌｅｓ  ｏｆ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｃｏｍｐｕｔｉｎｇ、  １９９１、  ｐｐ．  ５１−６１．
［Ｐ］  Ｔ．  Ｐ．  Ｐｅｄｅｒｓｅｎ、  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｐｒｏｖｅｒｓ  ｗｉｔｈ  Ａｐｐｌｉｃａｔｉｏｎｓ  ｔｏ  Ｕｎｄｅｎｉａｂｌｅ  Ｓｉｇｎａｔｕｒｅｓ、  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −  Ｅｕｒｏｃｒｙｐｔ  ９１  Ｐｒｏｃｅｅｄｉｎｇｓ、  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  Ｖｏｌ．  ５４７、  Ｄ．  Ｄａｖｉｅｓ  ｅｄ．、  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｇｌａｇ、  １９９１、  ｐｐ．  ２２１−２４２．
［Ｐ２］  Ｔ．Ｐ．  Ｐｅｄｅｒｓｅｎ、  Ａ  ｔｈｒｅｓｈｏｌｄ  ｃｒｙｐｔｏｓｙｓｔｅｍ  ｗｉｔｈｏｕｔ  ａ  ｔｒｕｓｔｅｄ  ｐａｒｔｙ、  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −  Ｅｕｒｏｃｒｙｐｔ  ９１  Ｐｒｏｃｅｅｄｉｎｇｓ、  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  Ｖｏｌ．  ５４７、  Ｄ．  Ｄａｖｉｅｓ  ｅｄ．、  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ、  １９９１、  ｐｐ．  １２９−１４０
［Ｐ９１］  Ｔ．Ｐ．  Ｐｅｄｅｒｓｅｎ、  Ｎｏｎ−ｉｎｔｅｒａｃｔｉｖｅ  ａｎｄ  ｉｎｆｏｒｍａｔｉｏｎ  ｔｈｅｏｒｅｔｉｃ  ｓｅｃｕｒｅ  ｖｅｒｉｆｉａｂｌｅ  ｓｅｃｒｅｔ  ｓｈａｒｉｎｇ、  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −  Ｃｒｙｐｔｏ  ９１  Ｐｒｏｃｅｅｄｉｎｇｓ、  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  Ｖｏｌ．  ５７６、  Ｊ．  Ｆｅｉｇｅｎｂａｕｍ  ｅｄ．、  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ、  １９９１、  ｐｐ．  １２９−１４０．
［ＲＳＡ］  Ｒ．  Ｒｉｖｅｓｔ、  Ａ．  ＳｈａｍｉｒおよびＬ．  Ａｄｌｅｍａｎ、  Ａ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｏｂｔａｉｎｉｎｇ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  ａｎｄ  Ｐｕｂｌｉｃ  Ｋｅｙ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ、  Ｃｏｍｍ．  ｏｆ  ＡＣＭ、  ２１  （１９７８）、  ｐｐ．  １２０−１２６．
［Ｓｈ］  Ａ  ｓｈａｍｉｒ、  Ｈｏｗ  ｔｏ  ｓｈａｒｅ  ａ  ｓｅｃｒｅｔ、  Ｃｏｍｍ．  ｏｆ  ＡＣＭ、  ２２  （１９７９）、  ｐｐ．  ６１２−６１３．
［Ｙ８２ａ］  Ａ．  Ｃ．  Ｙａｏ、  Ｔｈｅｏｒｙ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ  ｏｆ  Ｔｒａｐｄｏｏｒ  ｆｕｎｃｔｉｏｎｓ、  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２３ｒｄ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  ｔｈｅ  Ｆｏｕｎｄａｔｉｏｎ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ、  １９８２、  ｐｐ．  ８０−９１．
［Ｙ８２］  Ａ．  Ｃ．  Ｙａｏ、  「Ｐｒｏｔｏｃｏｌｓ  ｆｏｒ  ｓｅｃｕｒｅ  ｃｏｍｐｕｔａｔｉｏｎｓ」、  ＩＥＥＥ  ＦＯＣＳ  １９８２、  １６０−１６４．
［Ｙ８６］  Ａ．  Ｃ．  Ｙａｏ、  「Ｈｏｗ  ｔｏ  ｇｅｎｅｒａｔｅ  ａｎｄ  ｅｘｃｈａｎｇｅ  ｓｅｃｒｅｔｓ」、  ＩＥＥＥ  ＦＯＣＳ  １９８６、  １６２−１６７．
（要約）
本発明の好適な実施形態は、非対称（例えば、公開／私用）な暗号システムで用いられる暗号鍵を生成するようオペレーションを行うコンピュータのネットワークである。本発明は、コンピュータ群を用いて秘密鍵を生成することを可能にする。このプロセスでは、鍵を分散型シェアの形態で生成し、これにより、（十分に多くの）コンピュータの部分セットが鍵を復号（ｒｅｃｏｖｅｒ）するのに十分な情報を有し、コンピュータのサブセットがそのシェア（例えば、証明書に署名するなど）を用いて暗号関数を実行することができる。しかし、鍵のシェア生成または鍵のシェア使用の間、秘密鍵は実際は形成されない。１つの好適なバージョンにおいて、本方法は複数の不正を行おうとする参加者に対してセキュアである。
【０００９】
本発明の好適な実施形態は、２つの大きな素数の積である数を必要とする暗号システム用途の鍵シェア（ｋｅｙ  ｓｈａｒｅ）を生成する。本方法は概括的には、以下の工程で進行する。
【００１０】
１．セットアップ；
２．値Ｎの分散型生成；
３．値Ｎについて、２重素数性（ｄｏｕｂｌｅ  ｐｒｉｍａｌｉｔｙ）のプロパティを評価
４．必要に応じて工程２および工程３を繰り返す；
５．鍵シェアの生成
本発明は、外部および内部の敵対者両方に対して最大限のセキュリティを必要とする暗号アプリケーションにおいて特定のユーティリティを有する。ロバスト性を有すれば、分散型システムが対応することとなるエラー、故障、攻撃などの多様なシステム条件下における適切なオペレーションが保証される。
【００１１】
（好適な実施形態の簡単な説明）
検証可能な秘密シェア（ｖｅｒｉｆｉａｂｌｅ  ｓｅｃｒｅｔ  ｓｈａｒｉｎｇ）  ［ＣＧＭＡ］および汎用ゼロ知識証明（ｇｅｎｅｒａｌ  ｚｅｒｏ−ｋｎｏｗｌｅｄｇｅ  ｐｒｏｏｆｓ）  ［ＧＭＲ］などの暗号化技術の分野において、ロバスト性は基本的な考え方の動機となった。本発明は、シェア型ＲＳＡ鍵（ｓｈａｒｅｄ  ＲＳＡ  ｋｅｙｓ）（またはより一般的には２つの大きな素数の乗算および指数化）を、ロバストで効率的かつセキュアに生成する方法を提供する。本発明では、暗号鍵のシェアを生成する工程に参加する参加者をｎ人と仮定している。参加者は、通信ネットワークで接続されたプログラムされたコンピュータであり得る。本方法は、ｎ≧２ｔ＋１の場合すなわちｔ人の当事者の最大数があらゆる悪意的かつ勝手な方法で不正を行った場合にも、鍵のシェアを正常に生成する。大多数の良質の参加者が必要不可欠なため、本方法は最適な回復性を達成する。ｎ≧３ｔ＋１の場合、少しだけ効率の良い変数のプロトコルが用いられ得る。
【００１２】
本発明の技術はその他の非常に多くの問題を解消する。なぜならば、本発明の技術は、合成ＥｌＧａｍａｌ暗号化／署名、識別スキームなどの（Ｆｅｉｇｅ、Ｆｉａｔ、Ｓｈａｍｉｒ［ＦＦＳ］に記載のような）Ｎの素因数分解について参加者が知ることが不可能である合成数と、より効率の良いバージョンのＹａｏによる同時ビット交換プロトコル［Ｙ８６］とに基づいて他の暗号スキームを分散的に開始することができるからである。
【００１３】
本発明の好適な実施形態は、以下の新規な技術に基づいて構築される。
【００１４】
１．（１）（離散対数の問題の困難性のみに基づいたロバスト性およびセキュリティ性を有する）素数フィールドまたは（２）（ＲＳＡ問題の困難性のみに基づいたロバスト性およびセキュリティ性を有するが、シェア型ＲＳＡモジュラスを必要としない）整数のサブセットから引用された値のシェア型「多項和（ｓｕｍ−ｏｆ−ｐｏｌｙ）」表現のための乗算プロトコル。本技術は、他のアプリケーションにおいても可能性を有する。なぜならば、本技術は情報理論的にセキュアであるだけでなく、「サーバ集団」により保管される公開で検証可能な証拠（ｗｉｔｎｅｓｓ）を生成するからである。
【００１５】
２．シェア型情報の「連鎖的整合性」およびそれに関連する検証情報のための技術、すなわち、その検証情報の表現が変化した場合にでも検証情報と多様な計算タスク（例えば、生成プロトコル、乗算プロトコル、および２重素数性（ｄｏｕｂｌｅ  ｐｒｉｍａｌｉｔｙ）テストなど）とを強制的に整合性を持たせる技術。
【００１６】
これは、以下を含む。
【００１７】
Ａ．「相互検証」情報という考え方。すなわち、検証情報を通じてシェア情報を検証することにより整合性を保持し、さらには、シェア情報を通じて新しい検証情報（恐らくは異なる表現）を検証する工程。この「検証して計算する」という双対性は、有望であり、かつこれ自体で興味深いものである。
【００１８】
Ｂ．効率的なゼロ知識独立引数により、検証情報が整合性を有することを検証する。
【００１９】
Ｃ．多数の検証情報ｗ．ｒ．ｔ個別鍵を用いることにより広範囲な検証を確実にするブートストラップ技術。
【００２０】
実際、これらの技術は、多くの多様な指数化をベースとする暗号システムおよびこれらの関数を適用する分散型プロトコルに対応するのに十分な汎用性を有する。
【００２１】
３．シミュレータ多義性コミットメント（Ｓｉｍｕｌａｔｏｒ−Ｅｑｕｉｖｏｃａｌ  ｃｏｍｍｉｔｍｅｎｔ）と呼ばれるコミットメントメカニズム。このメカニズムは、通常のコミットメントと同じようにセキュアかつ効率的であるが、標準的なコミットメントでは達成不可能なコミットデータに対し、一定の同時性因数を考慮する。このメカニズムは、結果生成プロトコルのセキュリティのための新規な証拠技術へとつながる。
【００２２】
以下に説明するプロトコルは、ＲＳＡ関数（および上述の他の関数）を用いた分散型システムを分散的に開始することができることを保証する。本明細書の本技術は、［ＧＪＫＲ］に記載のようなロバスト性を有する閾値ＤＳＳを構築するために用いることができるが、最適な回復性を有し、さらなる暗号技術は想定していない。このプロトコルは、ハードウェアもしくはソフトウェアまたは両方において構築可能である。
【００２３】
このプロトコルは、比較的効率が良い（すなわち、汎用コンパイラのように素数性テストの回路のサイズに依存しない）。加えて、シェア所有者（ｓｈａｒｅｈｏｌｄｅｒ）およびセキュリティ要求事項の数が適切である場合、回数を非ロバスト性プロトコルにおける回数とほぼ同じ回数にすることができ、（モジュラー指数化の回数において測定された）計算複雑性を非ロバスト性プロトコルの計算複雑性よりも約１００倍にすることができる。効率性に関する変更例については、以下においても説明される。
【００２４】
このプロトコルは、システム立ち上げ（ｓｙｓｔｅｍ  ｉｎｉｔｉａｔｉｏｎ）および（上述したような）非常に多くのシステムにおけるキー交換ならびに信頼性を分散させる必要がある多様な設定を行う際に実行可能および利用可能である。例えば、権限認証におけるシェア型公開鍵の交換は、３ないし５年毎に行われ得、これにより「リアルタイム」オペレーションの必要がなくなる。したがって、或る程度長期（例えば、２〜３週間）のプロトコルが適当である。一方、それ自身が５年以上の期間を要する「汎用コンパイラ」プロトコルは不適当である。
【００２５】
（システムの一般的な説明）
本発明は好適には、コンピュータのネットワークにおいて構築される。本発明は多くの利点を有し、特に以下に説明するような或る種類の敵対者に対するセキュリティの観点から見て多くの利点を有する。
【００２６】
ネットワーク：  好適なシステムは、多様な最近の作業および［ＢＦ９７］に類似するいわゆる「モデル」を満たすプロパティを有するコンピュータのネットワーク（シェア所有者）を用いる。このシステムは、ｎ個からなる（確率的）サーバの群を有し、これらのサーバは全て、通信チャンネルと呼ばれる共通ブロードキャスト媒体Ｃに接続される。媒体Ｃで送信されたメッセージは、媒体Ｃに接続された各当事者に即時に到達すると仮定される。このシステムは、同期化される（そして、ｗ．ｌ．ｏ．ｇサーバは同期的に動作すると仮定することができる）。「モデル」の環境を満たす構築を行う際、ブロードキャストプロトコルおよびマルチキャストプロトコル、メッセージ送信プロトコル、暗号化および認証メッセージ送信プロトコル、ならびに承認プロトコルといった公知の構築に基づくことが可能である。これらの構築については、公知かつ慣例的なコンピュータ通信技術（例えば、Ｃｏｍｐｕｔｅｒ  Ｎｅｔｗｏｒｋｓ、  Ａｎｄｒｅｗ  Ｔａｎｅｎｂａｕｍ、  Ｐｒｅｎｔｉｃｅ−Ｈａｌｌ、  Ｉｎｃ．、  １９９６）に基づけば明らかである。
【００２７】
敵対者：  敵対者は、計算に制約があり（すなわち、敵対者は基礎をなす暗号プリミティブを破壊することができない）、破壊されるサーバのメモリをビューイングし、および／または自身の行動を変更することにより、いつでもサーバを破壊することができる。敵対者は、プロトコルが開始する際、どのサーバを破壊するか決定する。プロトコルの間、ｎ個のサーバのうちｔ以下を敵対者が破壊することが仮定される（ここで、ｎ≧２ｔ＋１（またはより効率的なプロトコル変数の場合はｎ≧３ｔ＋１）である）。敵対者を分類する目的のため、悪意による故障を「通常の」サーバ故障（例えば、クラッシュなど）と区別する必要はない。敵対者はブロードキャストチャンネルＣに接続することができる。すなわち、敵対者は全てのメッセージを聞き、それ自身のメッセージをインジェクトすることができる。しかし、敵対者は、敵対者が制御できないサーバによりＣに送信されるメッセージを変更することおよび破壊されていないサーバがＣで送信されたメッセージを受信することを妨げることはできない。
【００２８】
実際、この好適なプロトコルはより可搬性の高い敵対者［ＯＹ９１］に対して有用である。本プロトコルは、「トライアル」で進行し、各トライアルは過去のトライアルの影響を受けない。トライアルの間、不正サーバ（悪意を有する敵対者を含む）を検出することができる。適切な鍵を生成することができ、または（プロトコルから逸脱して捕えられなかった）残りのサーバが新しいトライアルを再び開始する。今までに削除された不正サーバがｔ’個であるとすると、新しいトライアルが開始する際敵対者がｔ−１−ｔ’個の新しいサーバを占有する場合、本プロトコルは適切な鍵が生成されることを可能にする。
【００２９】
表記法：  下記の記載では、以下の表記法を用いる。「ｓｐ」とはセキュリティパラメータであり、Ｈとは、
【００３０】
【数１】
0004790122.tif 000002
である。下付き文字「i」「j」および「k」はベクトル内でインデックス付けされた個々の要素を示し、下付き文字「*」は（並行オペレーションを表す）ベクトル内の複数の要素全てを示す。Ｎ*は、各々が√Ｈおよび２√Ｈの範囲内である２つの未知の素数の積を示す。ｇ*およびｈ*は、互いに対する離散対数（ｍｏｄ  Ｎ*）が未知であるジェネレータである。このようなＮ*を発見するのは実際に困難であり、本プロトコルはこれを発見することを目的とする。
【００３１】
以下の好適なプロトコルの説明において、秘密シェア［Ｓｈ］、検証可能な秘密シェア［Ｆ］、無条件秘密検証可能な秘密シェア（ｕｎｃｏｎｄｉｔｉｏｎａｌｌｙ  ｓｅｃｕｒｅ  ｖｅｒｉｆｉａｂｌｅ  ｓｅｃｒｅｔ  ｓｈａｒｉｎｇ）［Ｐ９１］、素数群に対して離散対数を使用するベーシックコミットメント（ｂａｓｉｃ  ｃｏｍｍｉｔｍｅｎｔｓ  ｕｓｉｎｇ  ｄｉｓｃｒｅｔｅ  ｌｏｇｓ  ｏｖｅｒ  ｐｒｉｍｅ  ｇｒｏｕｐｓ）  ［Ｐ９１］、離散対数の知識のベーシック証明（ｂａｓｉｃ  ｐｒｏｏｆｓ  ｏｆ  ｋｎｏｗｌｅｄｇｅ  ｏｆ  ｄｉｓｃｒｅｔｅ  ｌｏｇｓ）  ［ＧＨＹ８５、  ＣＥＧ、  ＣＥＧＰ］および複数の当事者全てが私用乱数値にコミットし、これらの値を明らかにすることにより乱数値を生成することを可能とする或る方法などの当該分野において公知の技術について言及する。本明細書中、これらの（上記および下記両方の）出版物の内容全体の全てを参考のため援用する。
【００３２】
（メインプロトコル）
メインプロトコルは、以下の一連の工程で進行する。
【００３３】
１．セットアップ：  参加者は、ＳＩＭＵＬＡＴＯＲ−ＥＱＵＩＶＯＣＡＬ  ＣＯＭＭＩＴＭＥＮＴＳプロシージャのセットアッププロトコルを以下のように実行する。
【００３４】
２．再開始ポイント：  セットアッププロトコルを終了する際およびプロトコルが再開始ポイントに戻ってくる度に、大多数の参加者が、どのサーバが「正直」で（いくつかの当事者が除去された場合に）不正を働いている当事者の数の上界（ｕｐｐｅｒ  ｂｏｕｎｄ）はいくつなのかを承認する。
【００３５】
３．Ｎの分散型計算を実行する：  シェア所有者Ｓ1，．．．，Ｓnに対し、ｎ≧２ｔ＋１（またはより効率的な乗算プロトコルの場合はｎ≧３ｔ＋１）である。説明目的のため、Ｌ＝ｎ！とし、ｓｐをセキュリティパラメータとし、
【００３６】
【数２】
0004790122.tif 000003
とする。このプロトコルの目的は、以下の式を計算することである：
Ｎ＝（ｐ1＋ｐ2＋．．．＋ｐn）（ｑ1＋ｑ2＋．．．＋ｑn）、
ここで、ｐ’およびｑ’は、シェア所有者によりランダムに選択された値である。計算工程は、以下のように行われる。
【００３７】
各シェア所有者Ｓiは、ｐi，ｑi∈R［１／２√Ｈ，√Ｈ］を選択する（ここで、下付き文字「R」は「ランダム」を示し、記号∈Rは集合または区間（ｉｎｔｅｒｖａｌ）内の乱数を示す）。
【００３８】
各シェア所有者Ｓiは、整数についてシャミール秘密シェアスキームを用い、ｐiおよびｑiの各々のシェアを分散する。説明目的のため、ｐiをシェアするための多項式をａi（ｘ）とし、ｑiをシェアするための多項式をｂi（ｘ）とする。
【００３９】
各シェア所有者Ｓiは、下記で説明するＭＵＬＴＩＰＬＩＣＡＴＩＯＮ  ＳＣＨＥＭＥ  ＯＶＥＲ  ＴＨＥ  ＩＮＴＥＧＥＲＳプロシージャを用いて、
Ｎ＝（ｐ1＋ｐ2＋．．．＋ｐn）（ｑ1＋ｑ2＋．．．ｑn）を計算する。
【００４０】
各シェア所有者Ｓiは互いに、上記乗算スキームからのゼロ係数検証シェアによる下記にて説明するＰＲＯＯＦ  ＯＦ  ＫＮＯＷＬＥＤＧＥ  ＯＦ  Ａ  ＤＩＳＣＲＥＴＥ  ＬＯＧプロトコル、すなわち
【００４１】
【数３】
0004790122.tif 000004
およびｈ*を用いて、ｐiおよびｑiが［０，３／√２Ｈ］の範囲内であることを証明する。
【００４２】
シェア所有者が（自身の証拠を満たさないことが検出される者として）不正を行い、大多数のシェア所有者がその不正を承認する場合、不正を行ったシェア所有者は残りのプロトコルから除外される。
【００４３】
４．ＲＯＢＵＳＴ  ＤＩＳＴＲＩＢＵＴＥＤ  ＤＯＵＢＬＥ−ＰＲＩＭＡＬＩＴＹ  ＴＥＳＴ  ＯＦ  Ｎを実行する。Ｎが失敗した場合、現在の「正直（ｈｏｎｅｓｔ）」なシェア所有者（すなわち除外されていないシェア所有者）は、Ｎ値がそのｐｒｉｍａｌｉｔｙテストを満足するまでプロトコルを再開始ポイントから繰り返す。
【００４４】
５．ＲＯＢＵＳＴ  ＤＩＳＴＲＩＢＵＴＥＤ  ＧＥＮＥＲＡＴＩＯＮ  ＯＦ  ＰＵＢＬＩＣ  ＡＮＤ  ＰＲＩＶＡＴＥ  ＫＥＹＳを実行する。Ｎがｐｒｉｍａｌｉｔｙテストを満たす場合、残りの「正直な」当事者は、２つのプロトコルのうち１つを実行し、公開鍵および私用鍵ｅおよびｄを決定する。（ＳＭＡＬＬ  ＰＵＢＬＩＣ  ＫＥＹＳまたはＬＡＲＧＥ  ＰＵＢＬＩＣ  ＫＥＹＳのプロトコルは、公開指数の大小に応じてシステム設計者またはオペレータが選択することができる。）
このメインプロトコルは、複数の支援プロトコルを用いる。これらの支援プロトコルについて下記に説明する。
【００４５】
（シミュレータ多義性コミットメント）
コミットメントは、封印された封筒（この封筒は、一方通行のみで開封することができる（制約プロパティ））内の値を通知する概念を電子的通信においてシミュレートするために用いられるが、封筒は開封されるまで封筒内部の値を明らかにしない（セキュリティプロパティ）。
【００４６】
当事者Ｂは、当事者Ａの値にコミットすることができ、これによりコミットメントは制約となる。しかし、シミュレータは非制約的なコミットメントを生成することができる。［ＩＹ８７］において、このようなメカニズムを（より低効率ではあるが）早くから用いた例が記載されている。シミュレータ多義性（Ｓｉｍｕｌａｔｏｒ−Ｅｑｕｉｖｏｃａｌ）コミットメントは基本的には、トラップドアの証拠知識と組み合わされたトラップドアコミットメント［ＦＳ８９］である。
【００４７】
好適なコミットメントメカニズムでは、以下のセットアッププロトコルを用いる。このプロトコルは、任意の回数のコミットメントに対して１回だけ実行すればよい（このコミットメントメカニズム自体は、通常のコミットメントを用いて特別コミットメントをセットアップする。）。
【００４８】
セットアップ：
・当該分野で公知の技術を用いてＺ*pについて強力な素数Ｐおよびジェネレータｇが分散的に選択される。
【００４９】
・当事者Ａは、ＢのＡへのコミットメントに用いられる値ｇ’  ∈Ｚ*pを選択し、ｇ’をＢに送信し、ｇを底とした離散対数ｇ’（ｄｉｓｃｒｅｔｅ  ｌｏｇ  ｏｆ  ｇ’  ｂａｓｅ  ｇ）を知っていることをＢに対して証明する（これは、当該分野で公知の離散対数の知識を証明するための基本的なプロシージャを用いて行うことができる）。
【００５０】
基本的なコミットメント：
・［Ｐ９１］において、コミットメントが計算的制約を有するよう、当事者（ｐａｒｔｙ）Ａが情報理論的に値にコミットすることが可能なプロトコルが開発された。例えば、３つ（ｇ，ｈ，Ｐ）のＰ＝２Ｐ’＋１ａの強力な素数があり、ｈを底とした離散対数ｇであり、ｍｏｄ  ＰがＡに対して未知であるとする。Ａは、ランダムな値ｘ’について
【００５１】
【数４】
0004790122.tif 000005
を公開化することにより、値ｘにコミットする。Ａがこのコミットメントを公開することを所望する場合、Ａはｘおよびｘ’を明らかにし、別の当事者は、
【００５２】
【数５】
0004790122.tif 000006
かどうかを検証し得る。［Ｐ９１］において、Ａがコミットメントを２種類の方法でオープンすることができる場合、Ａはｈを底とした離散対数ｇｈ  ｍｏｄ  Ｐを知る。コミットメントは、ｇおよびｇ’が用いられる点以外はＢａｓｉｃ  Ｃｏｍｍｉｔｍｅｎｔプロトコルの場合と同様に構築される。
【００５３】
・Ｂが、
【００５４】
【数６】
0004790122.tif 000007
を選択し、
【００５５】
【数７】
0004790122.tif 000008
を公開することにより値
【００５６】
【数８】
0004790122.tif 000009
にコミットする。
【００５７】
・Ｂがそのコミットメントをオープンにすることを所望する場合、Ｂはｘおよびｘ’を明らかにし、Ａは、
【００５８】
【数９】
0004790122.tif 000010
かどうかを検証し得る。
【００５９】
（整数に関する乗算スキーム）
整数に関する乗算スキームは、素数フィールドに関する分散型乗算についてのプロトコルを変更したものである。第１に素数フィールドに関する乗算について述べ、第２に整数に関する乗算を可能にする変更例について述べる。
【００６０】
素数フィールドに関する多項和の乗算
このプロトコルは、各々が多項式の和で表される２つの秘密値を乗算する。［ＧＪＫＲ］において（素数フィールドのみに関する）これらのプロトコルに対して関連プロトコルが述べられていが、本明細書中で説明される本プロトコルはこれらの関連プロトコルとは違って無条件にセキュアであり、他に仮定が無い場合の離散対数の困難性に基づく。
【００６１】
本スキームは、サーバ間で私用メッセージを送る意味論的にセキュアな公開鍵暗号を用いる。サーバ（シェア所有者）Ｓ1，．．．，Ｓn（ｎ≧２ｔ＋１の場合）は、素数フィールドに関してロバストな乗算を実行する一方、無条件にセキュリティを保持することができる。本プロトコルの目的は、ＡiおよびＢiがＳiにより選択された場合にＣ≡（Ａ1＋Ａ2＋．．．＋Ａn）（Ｂ1＋Ｂ2＋．．．＋Ｂn）ｍｏｄ  Ｐ’を計算することである。（本節において用いられる変数ＣはメインプロトコルのＮに相当し、Ａnはメインプロトコルのｐnに相当し、Ｂnはメインプロトコルのｑnに相当する）。本スキームは以下の工程で進行する。
【００６２】
１．セットアップ
説明目的のため、Ｐ＝２Ｐ’＋１を強力な素数とし、（底ｇに対する離散対数ｈを未知とするように）ｇおよびｈをＺp*のジェネレータとする。各サーバＳiは、
【００６３】
【数１０】
0004790122.tif 000011
を決定し、ランダム多項式を用いてこれらの値のシャミール秘密シェアリング工程を実行する。
【００６４】
【数１１】
0004790122.tif 000012
ここで、ａi（０）＝Ａiであり、ｂi（０）＝Ｂiである。
【００６５】
【数１２】
0004790122.tif 000013
である点に留意されたい。各サーバは値Ａi，Ｂiのシェア表現を生成したが、これらのサーバはシェアを他のサーバにまだ分散していない点にも留意されたい。本プロトコルの間、いずれかのシェア所有者Ｓiが破壊されると決定された場合、残りのサーバはそのサーバに関してＡi＝Ｂi＝０でありかつ本プロトコルを通じてシェアＡi＝Ｂi＝０はゼロに等しいとする。
【００６６】
２．ＡiおよびＢiのＰＥＤＥＲＳＥＮシェアリング
サーバは、Ｐｅｄｅｒｓｅｎシェアリングスキームを変更したものを用いてＡiおよびＢiの各値をシェアする。Ｐｅｄｅｒｓｅｎは自身のシェアリングスキームを検証可能な秘密シェアリングを構築するために用いたが、本明細書中に記載のこのプロトコルではこのシェアリングを効率的な、ロバストかつセキュアな乗算のベースとして用いる。この乗算プロトコルへの入力は、以下のように生成される。
【００６７】
（ａ）各サーバＳiは、ペアの秘密
【００６８】
【数１３】
0004790122.tif 000014
を生成し、ランダムな多項式
【００６９】
【数１４】
0004790122.tif 000015
を用いて、これらの秘密をシャミールシェアリングを用いてシェアする（ここで、ａ’i（０）＝Ａ’iおよびｂ’i（０）＝Ｂ’iである）。各サーバは、（ａi（ｘ），ａ’i（ｘ））および（ｂi（ｘ），ｂ’i（ｘ））：
【００７０】
【数１５】
0004790122.tif 000016
およびの各ペアに対して、Ｐｅｄｅｒｓｅｎ検証シェアを公開する。各サーバＳkは、検証シェアを用いてそれ自身のシェアを検証する。
【００７１】
（ｂ）説明目的のため、以下を定義する。
【００７２】
【数１６】
0004790122.tif 000017
多項式ａ（ｘ）およびａ’（ｘ）のゼロ番目の係数はそれぞれＡおよびＡ’であることが観察される。ペア（ａ（ｘ），ａ’（ｘ））に関する検証シェアが以下のように全てのシェア所有者によって計算可能である点にも留意されたい。
【００７３】
【数１７】
0004790122.tif 000018
３．乱数化多項式の生成
各サーバは、さらにランダムな多項式を生成する。
【００７４】
【数１８】
0004790122.tif 000019
サーバは、これらの多項式のシェアを分散し、１≦ｊ≦２ｔで、検証シェア
【００７５】
【数１９】
0004790122.tif 000020
をブロードキャストする（ｚi（０）＝ｚ’i（０）＝０および１≦ｉ≦ｎの場合にρi,0＝１である点に留意されたい）。各サーバｊは、受信した検証シェアを用いて受信した多項式シェアを検証する。
【００７６】
各サーバＳiはまた、ランダムな多項式
【００７７】
【数２０】
0004790122.tif 000021
を生成し、この多項式のシェアを分散する。
【００７８】
４．ランダム化されたＡ（ｘ）Ｂi（ｘ）およびＡ（ｘ）Ｂ’i（ｘ）のシェアを生成および検証する：
全てのシェア所有者は、前回受信したシェアを用いて以下のようにｖi（ｘ）およびｖ’i（ｘ）のシェアを局所的に計算する：
ｖi（ｘ）≡ａ（ｘ）ｂi（ｘ）＋ｚi（ｘ）および
ｖ’i（ｘ）≡ａ’（ｘ）ｂi（ｘ）＋ｚ’i（ｘ）＝ｒi（ｘ）
各サーバＳiは、多項式ペア（ｖi（ｘ）、ｖ’i（ｘ））について検証シェアＶi、jを以下のようにブロードキャストする：
【００７９】
【数２１】
0004790122.tif 000022
全てのサーバＳiは、局所的シェアが公開シェアと整合するかどうかを検証することができる。正しいｖi（ｊ）値が決まらない場合は、ＳjはＳiにシェアｂi（ｊ）およびｒi（ｊ）を明らかにするよう呼び掛ける。全てのシェア所有者は、ｂi（ｊ）がｂi（ｘ）の検証シェアに適切かどうかを決定することができ、以下を計算することによりｖi（ｊ）がｖi（ｘ）の検証シェアに適合するかどうかを決定することができる。
【００８０】
【数２２】
0004790122.tif 000023
ここで、
【００８１】
【数２３】
0004790122.tif 000024
は、（ａ（ｘ），ａ’（ｘ））についてのα検証シェアから計算することができ、
【数２４】
0004790122.tif 000025
は、（ｚi（ｘ），ｚ’i（ｘ））についてのρ検証シェアから計算することができる。
５．検証シェアの正当性を証明する
１≦ｉ≦ｎの場合、各サーバＳiは、１≦ｉ≦ｎの場合に
【００８２】
【数２５】
0004790122.tif 000026
の表現を知っていることを全ての他のサーバに対して証明し、ここで前者の離散対数ｇおよび後者の
【００８３】
【数２６】
0004790122.tif 000027
は等しい。これは、２ｔ＋１≦ｎ≦３ｔである場合のみに必要とされる。
【００８４】
６．出力
各Ｓkは、ｖ（ｋ）およびｖ’（ｋ）を計算し、明らかにする。ここで、
【００８５】
【数２７】
0004790122.tif 000028
である。
【００８６】
各サーバは、上記で得られた値を挿入してｖ（０）を得る。ｖ（０）≡ＡＢ≡Ｃ  ｍｏｄ  Ｐ’であるため、この値は、所望の乗算により得られた値である。これらの多項式ｖ（ｘ）およびｖ’（ｘ）についての検証シェアは、前回の工程からの検証シェアから計算することができる点に留意されたい。明らかにされたシェアは全て、これらの検証シェアを用いて検証される。
【００８７】
整数に関する基本的な技術
メインプロトコルは整数に関する乗算を必要としたが、上述の基本的スキームは有限フィールドに関する乗算を達成する。（有限フィールドに関する）上記のスキームは、下記のように変更することができ、これにより整数に関する乗算を行う。
【００８８】
１．整数に関する秘密シェアリング［ＦＧＭＹａ］  上記にて用いられた素数フィールドに関するシャミール秘密シェアリング技術が、整数について用いられる変数を用いて変更される。これは、シャミール秘密シェアリング［Ｓｈ］の変数である。説明目的のため、Ｌ＝ｎ！とする。秘密ｓ∈［０，Ｋ］をシェアする際、当事者はランダム多項式
【００８９】
【数２８】
0004790122.tif 000029
を選択し、これによりａo＝Ｌ2ｓとなり、互いにａj∈R［０，Ｌ，２Ｌ．．．Ｌ3Ｋ2］となる。各シェア所有者ｉ∈｛１，．．．，ｎ｝は、秘密シェアｓi＝ａ（ｉ）を受信する。濃度ｔ＋１の全ての集合Λは、ＬａＧｒａｎｇｅ挿入を用いてｓを計算し得る。
【００９０】
２．整数に関するＰＥＤＥＲＳＥＮの無条件にセキュアなＶＳＳ
上記で用いられた素数フィールドに関するｐｅｄｅｒｓｅｎシェアリング工程は、整数に関して用いられる変数を用いて変更される。これは、Ｐｅｄｅｒｓｅｎ  Ｕｎｃｏｎｄｉｔｉｏｎａｌｌｙ  Ｓｅｃｕｒｅ  ＶＳＳ［Ｐ９１］の変数である。説明目的のため、用語「ｓｐ」をセキュリティパラメータと仮定し、Ｈ＝２spとする。Ｎ*は、各々が［√Ｈ、２√Ｈ］の範囲内にある２つの未知の素数の積であり、ｇ*およびｈ*は、それら自身の離散対数ｍｏｄ  Ｎ*を決定するのが困難であるジェネレータ（Ｎ*を決定することが本発明の目的であるため）であることも仮定する。この場合、各要素Ｓkは３つ（Ｎk，ｇk，ｈk）を選択し、ブロードキャストすることができる。
【００９１】
本プロトコルは、ｎ＋１秘密シェアリングによって開始する。すなわち最初は整数に関するシャミール秘密シェアリング工程であり、次にｎは上記のような整数に関するシャミールシェアリングの変数を用いたペアの秘密（ｃｏｍｐａｎｉｏｎ  ｓｅｃｒｅｔ）のシェアリングである。具体的には、秘密ｓ∈［０，Ｋ］に関して、当事者はランダムな多項式
【００９２】
【数２９】
0004790122.tif 000030
を選択し、これによりａ0≡Ｌ2ｓとなり、互いにａj∈R［０，．．．，Ｌ3Ｋ2］となる。次いで、３つの（Ｎk，ｇk，ｈk）の各々について、当事者は、それぞれにａ’j,k∈R［０，Ｌ，２Ｌ．．．，Ｌ3Ｋ3］を用いてランダム多項式
【００９３】
【数３０】
0004790122.tif 000031
を選択する。次いで、当事者は各多項式のシェアを各シェア所有者に（ｎ＋１の全シェアを各シェア所有者へと）送信し、検証シェア
【００９４】
【数３１】
0004790122.tif 000032
を公開する。各シェア所有者Ｓkは、それ自身のシェアａ（ｋ）および
【００９５】
【数３２】
0004790122.tif 000033
に関する検証シェアを用いて
【００９６】
【数３３】
0004790122.tif 000034
によって検証することができる（全て１≦ｋ’≦ｎの場合）。
【００９７】
３．整数に関する多項和乗算
有限フィールドに関する多項和乗算は、以下のように変更することができ、これにより、整数に関する和乗算が実行される。このプロトコルは、（統計的意味においてのみではあるが）無条件にセキュアである。
【００９８】
本プロトコルは、サーバ間で私用メッセージを送信する意味論的にセキュアな公開鍵暗号を用いる。このプロトコルは、サーバ（シェア所有者）Ｓ1，．．．Ｓn（ｎ≧２ｔ＋１の場合）が整数に関してロバストな乗算を行う一方、無条件にセキュリティを保持ことを可能にする。本プロトコルの目的は、範囲［１／２√Ｈ，√Ｈ］からＡiおよびＢiが、Ｓiにより選択された場合にＣ≡（Ａ1＋Ａ2＋．．．＋Ａn）（Ｂ1＋Ｂ2＋．．．＋Ｂn）ｍｏｄ  Ｐ’を計算することである（敵対者は上記範囲外から値を選択し得る）。
【００９９】
このプロトコルは、ｍｏｄ  Ｐ’ではなく整数に関してシェア計算を実行し、ｍｏｄ  Ｐではなくｍｏｄ  Ｎ*に関して検証およびチェックシェア計算を行い、そして以下の特定の変更点を有する点以外は前節で述べたものと同じである。すなわち、
工程１（セットアップ）：各ｉについて、ゼロ番目の係数ａi（ｘ）およびｂi（ｘ）はそれぞれ、Ｌ2ＡiおよびＬ2Ｂiとなる。
【０１００】
工程２ｂ（ＡiおよびＢiのＰｅｄｅｒｓｅｎシェアリング）：ゼロ番目の係数ａ（ｘ）は、ＡではなくＬ2Ａとなる。
【０１０１】
工程３（ランダム化多項式の生成）：ｚi（ｘ）およびｚi’（ｘ）の係数が以下のように得られる。すなわち、ｚi,j∈R［０，Ｌ11Ｈ3］およびｚ’i,j∈R［０，Ｌ11Ｈ4］。ｒi（ｘ）の係数は以下のように得られる。すなわちｒij∈R［０，Ｌ11Ｈ4］である。
【０１０２】
工程６（出力）：最後に、ｖ（０）はＡＢではなくＬ4ＡＢとなるため、参加者はＬ4で分割される。
【０１０３】
（ロバスト性ツール）
証拠知識が、上記セットアップで選択されたコミットメントツールを用いる。これらのツールは、サーバがゼロ知識証拠を効率的かつ一定の回数行うことを可能にする。
【０１０４】
１．離散対数の証拠知識
［ＧＨＹ８５］において、Ｘ＝ｇxｍｏｄ  Ｐの離散対数（またはあらゆる同形の関数）の検証者∨に対して証明者
【０１０５】
【数３４】
0004790122.tif 000035
が知識を証明するゼロ知識双方向証拠が示されている。本出願人らは下記において、合成モジュラス、Ｎ、および入力Ｘ＝ｇxｍｏｄ  Ｎ（いくつかのΖがΖ≧１の場合、ｘ∈［０．．Ζ］）に基づいた類似の証拠を実証する。
【０１０６】
【数３５】
0004790122.tif 000036
は、Ｓｉｍｕｌａｔｏｒ−Ｅｑｕｉｖｏｃａｌコミットメントを用いて、ランダムに選択されたｓｐビットストリングｃ＝ｃ1‖．．．‖ｃspにコミットし、また
【０１０７】
【数３６】
0004790122.tif 000037
ここで、ｑi∈R［０．．．Ζ］を送信する。
【０１０８】
∨は、ランダムに選択されたｓｐビットストリングｃ’＝ｃ’1‖．．．‖ｃ’spを
【０１０９】
【数３７】
0004790122.tif 000038
へと送信する。
【０１１０】
それ自身のコミットメントを
【０１１１】
【数３８】
0004790122.tif 000039
は、オープンする。ｋ＝１．．．ｓｐの場合、
【０１１２】
【数３９】
0004790122.tif 000040
は、ｖk＝ｄkｘ＋ｑkを送信する。
ここで、
【０１１３】
【数４０】
0004790122.tif 000041
である。
【０１１４】
ｋ＝１．．．ｓｐの場合、∨は、
【０１１５】
【数４１】
0004790122.tif 000042
を検証する。
【０１１６】
２．離散対数の証拠知識および対応する表現
証明者
【０１１７】
【数４２】
0004790122.tif 000043
が（ｘ，ｙ）の表現がＹ＝ｇ*xｈ*Y／Ｙ  ｍｏｄ  Ｎ*であり、この表現の第１の部分がＸ＝ｇxｍｏｄ  Ｎ（ｘ，ｙ∈［０．．．Ｚ］）の離散対数に相当することを知っていることを証明する場合、以下のプロトコルが用いられる。
【０１１８】
【数４３】
0004790122.tif 000044
は、Ｓｉｍｕｌａｔｏｒ−Ｅｑｕｉｖｏｃａｌコミットメントを用いて、ランダムに選択されたｓｐビットストリングｃ＝ｃ1‖．．．‖ｃspにコミットし、また
【０１１９】
【数４４】
0004790122.tif 000045
を送信する。ここでｑi，ｑ’1  ∈R［０．．Ｚ（Ｎ＋Ｎ*）］である。
【０１２０】
∨は、ランダムに選択されたｓｐビットストリングｃ’＝ｃ’1‖．．．‖ｃ’spを
【０１２１】
【数４５】
0004790122.tif 000046
に送信する。
【０１２２】
【数４６】
0004790122.tif 000047
は、それ自身のコミットメントをオープンする。ｋ＝１．．．ｓｐの場合、
【０１２３】
【数４７】
0004790122.tif 000048
はｖk＝ｄkｘ＋ｑkおよびｖ’k＝ｄkｙ＋ｑ’kを送信する。ここで、
【０１２４】
【数４８】
0004790122.tif 000049
である。
ｋ＝１．．．ｓｐの場合、∨は
【０１２５】
【数４９】
0004790122.tif 000050
を検証する。
【０１２６】
３．対応する表現の証拠知識
証明者
【０１２７】
【数５０】
0004790122.tif 000051
がｙおよびｙ’の値を知っていることを証明しようとし、これによりｇ*およびＨ*に関して（ｘ，ｙ）がＸ＝ｇx*ｈy*ｍｏｄ  Ｎ*の表現であり、（ｘ’，ｙ’）がｇ*およびｈ*に関して
【０１２８】
【数５１】
0004790122.tif 000052
の表現である場合、ｘ＝ｘ’であり、以下のプロトコルが用いられる。
【０１２９】
【数５２】
0004790122.tif 000053
は、Ｓｉｍｕｌａｔｏｒ−Ｅｑｕｉｖｏｃａｌコミットメントを用いて、ランダムに選択されたｓｐビットストリングｃ＝ｃ1‖．．．‖ｃspにコミットし、また
【０１３０】
【数５３】
0004790122.tif 000054
を送信する（ｑi，ｑ’i，ｑi”  ∈R［０．．Ｚ（Ｎ＋Ｎ*）］）。
【０１３１】
∨は、ランダムに選択されたｓｐビットストリングｃ’＝ｃ’1‖．．．‖ｃ’spを
【０１３２】
【数５４】
0004790122.tif 000055
に送信する。
【０１３３】
【数５５】
0004790122.tif 000056
は、それ自身のコミットメントをオープンする。ｋ＝１．．．ｓｐの場合、
【０１３４】
【数５６】
0004790122.tif 000057
は、ｖk＝ｄkｘ＋ｑk、ｖ’k＝ｄkｘ＋ｑ’kおよびｖ”ｋ＝ｄkｙ’＋ｑ”kを送信する。ここで、
【０１３５】
【数５７】
0004790122.tif 000058
である。
ｋ＝１．．．ｓｐの場合、∨は、
【０１３６】
【数５８】
0004790122.tif 000059
を検証する。
【０１３７】
４．証拠知識および表現の範囲
以下のプロトコルは、証明者
【０１３８】
【数５９】
0004790122.tif 000060
がｘおよびｙの値を知っていることを証明し、これにより（ｘ，ｙ）はｇ*およびｈ*に関してＸ＝ｇ*xｈ*Yｍｏｄ  Ｎ*の表現である（ここで、ｙ∈［０．．．Ζ］およびｘ∈［ａ−ｗ．．ｂ＋ｗ］であり、ｗ＝｜ａ−ｂ｜）。ｘ∈［ａ．．ｂ］である場合、このプロトコルはゼロ知識である（［ａ−ｗ．．ｂ＋ｗ］⊆［０．．Ζ］とする）。
【０１３９】
【数６０】
0004790122.tif 000061
は、Ｓｉｍｕｌａｔｏｒ−Ｅｑｕｉｖｏｃａｌコミットメントを用いて、ランダムに選択されたｓｐビットストリングｃ＝ｃ1‖．．．‖ｃspにコミットし、また
【０１４０】
【数６１】
0004790122.tif 000062
を送信する。ここで、ｑi，∈R［０，ｗ］，ｑ’i，ｑ”i∈R［０．．Ζｎ*］である。これらのペアが無秩序であることに留意されたい。
∨は、ランダムに選択されたｓｐビットストリングｃ’＝ｃ’1‖．．．‖ｃ’spを
【０１４１】
【数６２】
0004790122.tif 000063
に送信する。
【０１４２】
【数６３】
0004790122.tif 000064
は、それ自身のコミットメントをオープンする。ここで、
【０１４３】
【数６４】
0004790122.tif 000065
とする。ｋ＝１．．．ｓｐの場合、ｄk＝１のとき、
【０１４４】
【数６５】
0004790122.tif 000066
は、ｑk，ｑ’kおよびｑ”kを送り、そうでない場合はｖk＝ｘ＋ｇkおよびｖ’k＝ｙ＋ｇ’kまたはｖk＝ｘ＋ｑkおよびｖ’k＝ｙ＋ｑ”kを送信する（どちらの場合もｖk∈［ａ．．ｂ］）。
ｋ＝１．．．ｓｐの場合、ｄk＝１で、∨は、ｑk∈［０．．ｅ］および
【０１４５】
【数６６】
0004790122.tif 000067
を検証し、
【０１４６】
【数６７】
0004790122.tif 000068
は、
【０１４７】
【数６８】
0004790122.tif 000069
によって送信されたｋ番目のペアの要素となり、そうでない場合は、∨はｖk∈［ａ．．ｂ］および
【０１４８】
【数６９】
0004790122.tif 000070
が、
【０１４９】
【数７０】
0004790122.tif 000071
により送信されたｋ番目のペアの要素の１つに相当することを検証する。
【０１５０】
（ロバストな分散二重素数性テスト）
好適な方法は、Ｂｏｎｅｈ−Ｆｒａｎｋｌｉｎによる先述のものに基づいた二重素数テストスキームを用いるが、これをロバストであり、且つロバスト性ツールを値ｎの先行する生成に「連結する」ように改変する。この方法では、サーバは以前に計算された値Ｎが２つの大きな素数の積であるかどうか（所定の署名および他の暗号スキームにおいてＮを使用するために必要な条件）を検証する。ロバスト性を獲得するためには（例えば、たとえプロトコルに参加するサーバの一方が不正であってもＮが二重素数であることを決定するためには）、プロトコルは、
【０１５１】
【数７１】
0004790122.tif 000072
として定義される、各サーバＳiに対する多項式を利用する。ここで、ａi（ｘ）およびｂi（ｘ）は、Ｎの分散計算においてそれぞれｐiおよびｑiを分散するために用いられた。また、好適な方法は、Ｐｅｄｅｒｓｅｎシェアステップにおいて使用される対応する検証シェアも用いる。例示目的で、これらの検証シェアをγi,j、但し０≦ｊ≦ｔと呼び、
【０１５２】
【数７２】
0004790122.tif 000073
とする。ここでｐ’iおよびｑ’iは、それぞれｐiおよびｑiに対する１組の秘密である。
【０１５３】
当事者は、所望の秘密レベルを獲得するために必要なだけの回数、以下のステップを繰り返す。成功した反復の各々が、計算された値Ｎが二重素数であることの信頼度を増加させる。いかなる反復の失敗も、Ｎが二重素数でないことを示し、サーバは、新しいＮの値を計算するために再開点（ＲＥＳＴＡＲＴＩＮＧ  ＰＯＩＮＴ）に戻る。
【０１５４】
１．シェア所有者はｇを、
（ｇ／ｎ）＝１
のように無作為に選択する。ここで、”（ｇ／ｎ）”はＪａｃｏｂｙ記号を示す。
【０１５５】
２．第１のサーバＳ1は、値、
【０１５６】
【数７３】
0004790122.tif 000074
を計算しブロードキャストする。
【０１５７】
次に第１のサーバが、ＰＲＯＯＦ  ＯＦ  ＫＮＯＷＬＥＤＧＥ  ＯＦ  Ａ  ＤＩＳＣＲＥＴＥ  ＬＯＧにおけるプロトコルを用いて、Ｑ1の離散対数および
【数７４】
0004790122.tif 000075
すなわち
【０１５８】
【数７５】
0004790122.tif 000076
およびｈ*よりも大きく、この対応する表現の知識を証明する。
【０１５９】
それぞれのｉ≧１（即ち残りのサーバ）に対して、各サーバＳiは、
【０１６０】
【数７６】
0004790122.tif 000077
をブロードキャストする。次に、各サーバＳiは、ＰＲＯＯＦ  ＯＦ  ＫＮＯＷＬＥＤＧＥ  ＯＦ  Ａ  ＤＩＳＣＲＥＴＥ  ＬＯＧにおけるプロトコルを用いて、Ｑ1の離散対数およびγi,0、すなわち
【０１６１】
【数７７】
0004790122.tif 000078
およびｈ*より大きい、γi,0の対応する表現の知識を証明する。
３．すべてのシェア所有者は、
【０１６２】
【数７８】
0004790122.tif 000079
を検証する。ここで、記号「≡」は、「合同である」ことを意味する。合同でない場合、サーバはＮが２つの素数の積でないことを宣言する。
【０１６３】
（公開鍵および個人鍵のロバストな分散生成）
鍵生成ステップは、
【０１６４】
【数７９】
0004790122.tif 000080
（φ（Ｎ）はオイラー関数）
である関係を利用する。好適なプロトコルは、２つのうち１つの手順、即ち、小さな公開鍵に対しては単純な手順を、より大きな（一般的な）公開鍵にはより複雑な手順を用いる。
【０１６５】
シェア値の表現の変更が最初に実施される場合、所定の操作は（ロバスト性を確証するための情報を検証しながら）容易になし得る。ｎ人のサーバ中のｔ次多項式により共有される関数をｔからｔ加法（和）シェアに変換する「多項式から和」の技術が用いられる。「和から多項式」技術は、ｔからｔをｎからｔの多項式シェアに加法的に変換する。［ＦＧＭＹａ］からのシェア表現変換技術が用いられ得る。
【０１６６】
（小さな公開鍵のための鍵生成）
小さな公開鍵、例えばе＝３であるＲＳＡシステムに対しては、以下のプロセスが用いられ得る。
【０１６７】
１．シェア所有者は、ＳＩＭＵＬＡＴＯＲ−ＥＱＵＩＶＯＣＡＬ  ＣＯＭＭＩＴＭＥＮＴＳに記載される技術を用いて、ｇ  ∈R［１，Ｎ−１］を連帯的に選択する。この手順では、それぞれのサーバが値ｇiに関与し、すべての参加者がｇiを明かした後、すべての参加者がｇiの積としてｇを計算し得る。
【０１６８】
２．それぞれのシェア所有者Ｓ1は「検証シェア」
【０１６９】
【数８０】
0004790122.tif 000081
をブロードキャストする。
【０１７０】
３．それぞれのシェア所有者Ｓiは、その値をＱi4  ｍｏｄ  Ｎに対して検証する。実際には、Ｓ1は、
【０１７１】
【数８１】
0004790122.tif 000082
に対してそれを検証する。
【０１７２】
４．それぞれのシェア所有者Ｓiは、ｘi＝ｐi＋ｑi  ｍｏｄ  ３を明かす。
【０１７３】
５．それぞれのシェア所有者Ｓ1は、基数ｇ’’＝ｇ3を伴う
【０１７４】
【数８２】
0004790122.tif 000083
の離散対数の知識（ＰＲＯＯＦ  ＯＦ  ＫＮＯＷＬＥＤＧＥ  ＯＦ  Ａ  ＤＩＳＣＲＥＴＥ  ＬＯＧに記載された技術を用いて達成され得る）を証明する。即ち、それぞれのシェア所有者Ｓiは、基数ｇ’’を伴うＸの指数を知っていると示すことにより、ｐi＋ｑi−ｘi＝３ｒとなるように値ｒを知っていることを示す。
【０１７５】
６．次のステップは、
【０１７６】
【数８３】
0004790122.tif 000084
である事実を利用する。
例示目的で、
【０１７７】
【数８４】
0004790122.tif 000085
すべてのサーバがこれらの値を計算し得る。
【０１７８】
φ（Ｎ）＝２  ｍｏｄ  ３である場合、第１のシェア所有者Ｓ1は、自らのｄのシェアを、ｄ1＝（ｒ−（ｐi＋ｑi−ｘ1））／３（場合１）として計算し、２≦ｉ≦ｎに対して、残るそれぞれのシェア所有者Ｓiが、自らのｄのシェアを、ｄi＝−（ｐi＋ｑi−ｘi）／３（場合２）として計算する。
【０１７９】
φ（Ｎ）＝１  ｍｏｄ  ３である場合、第１のシェア所有者Ｓ1は、自らのｄのシェアを、ｄ1＝（ｒ’−２（ｐ1＋ｑ1−ｘ1））／３（場合３）として計算し、２≦ｉ≦ｎに対して、残るそれぞれのシェア所有者Ｓiが、自らのｄのシェアを、ｄi＝−２（ｐi＋ｑi−ｘi）／３（場合４）として計算する。（値ｄが秘密であり、実際にｄを生成することなくｄのシェアを生成することが本発明の目的であることを想起されたい）
７．すべてのシェア所有者は、ステップ２で散布された検証シェアと比較したとき、３乗された検証シェアが正しいことを検証する。例えば、上述の場合１では、第１のサーバが
【０１８０】
【数８５】
0004790122.tif 000086
から開始し、これを３乗している。次に第１のサーバは、この結果に
【０１８１】
【数８６】
0004790122.tif 000087
の逆数を掛けている。結果は、ステップ２で散布された
【０１８２】
【数８７】
0004790122.tif 000088
に等しくなるはずである。
８．和から多項式への変換が実行され、（ｔ，ｎ）安全なｄの多項式シェアを構築する。生成されたシェアは、秘密暗号鍵のシェア、例えば、おおもとの承認機関における分散署名手順として用いられ得る。
【０１８３】
（大きな公開鍵に対する鍵生成）
大きなеに対しては、好適なプロトコルは、ＢｏｎｅｈおよびＦｒａｎｋｌｉｎにより説明される概念に関連した（φ（Ｎ））-1  ｍｏｄ  еとは異なる技術を用いる。好適なプロトコルは、値еは、Ｅ＝２е＋１ａ（強い）素数を伴う素数と見なされ得るという仮定を利用する。本方法の先のステップは、１≦ｉ≦ｎのとき、ｆi（ｘ）＝ａi（ｘ）＋ｂi（ｘ）であるという定義を利用していた。例示目的で、
【０１８４】
【数８８】
0004790122.tif 000089
とする。そうすると、ｆ（０）＝Ｌ2φ（Ｎ）となる。好適な方法は以下のステップで進められる。
【０１８５】
１．シェア所有者は連帯的にеを無作為に選択し（ＳＩＭＵＬＡＴＯＲ−ＥＱＵＩＶＯＣＡＬ  ＣＯＭＭＩＴＭＥＮＴＳからの手順を用いる）、еおよび２е＋１が素数であることを見極めるためのテストを行う。
【０１８６】
２．シェア所有者は、連帯的にｇe、  ｈe∈R  Ｚ*Eを選択する（ここでもＳＩＭＵＬＡＴＯＲ−ＥＱＵＩＶＯＣＡＬ  ＣＯＭＭＩＴＭＥＮＴＳからの手順を用いる）。
【０１８７】
３．シェア所有者は、連帯的にｇ、  ｈ∈  Ｚ*Nを選択する（ＳＩＭＵＬＡＴＯＲ−ＥＱＵＩＶＯＣＡＬ  ＣＯＭＭＩＴＭＥＮＴＳからの手順を用いる）。
（シェア所有者はこれらの多項対数を選択し得、そのすべてに対して検証手順を反復し得る。これにより、大きな桁数の発生器を保証する）。
【０１８８】
４．それぞれのシェア所有者Ｓ1は、ｍi  ∈R  ［０，Ｈ］を選択し、ｍiのシャミールシェアリングを整数に対して実行する。例示目的で、
ｍ＝ｍ1＋．．．＋ｍn
とする。そうするとｍは無作為となる。シェアの加算を用いることで、シェア所有者は、加算のシェアを保持し得る。例示目的で、この加算多項式をｆｍと呼ぶと、そのゼロ係数としてのｆｍ（０）＝Ｌ2ｍである。
【０１８９】
５．シェア所有者は、有限領域に対する乗法（е桁）を実行し、Ｄ＝Ｌ4φ（Ｎ）ｍ  ｍｏｄ  еを計算する（それぞれのｍiのシャミールシェアリングの値はすべてｍｏｄ  еから取られる）。これは、ｆおよびｆｍを乗算することにより達成される。記数目的で、ＩＮＶ＝Ｄ-1  ｍｏｄ  еとすると、これは公開値Ｄから容易に計算される（Ｄがｍの値により「無作為化」されており、任意に見えるので、その公開アベイラビリティがφ（Ｎ）に関する情報を漏らさないことに留意されたい）。
【０１９０】
６．それぞれのｊ，ｉに対し、各シェア所有者Ｓiは、そのｍiの整数シェアをＩＮＶで乗算する（ｍがｍiのの和であり、各ｍiに対して多項式が存在するので、プロトコルは「多項式の和」表現を生成することに留意されたい）。これによりサーバは、その和が秘密、
Ｗ≡（Ｌ4φ（Ｎ））-1  ｍｏｄ  е
を含む多項式の整数シェアリングを与えられる。この秘密は、Ｌ2で乗算すると、ゼロにおける合計多項式の値となる。
【０１９１】
７．シェア所有者は、（この最新の多項式およびゼロ係数におけるＬ4Ｗφ（Ｎ）＋１を伴う多項式シェアリングを得るためのｆ（ｘ）の）Ｎに対する検証シェアを伴う整数に対して乗算を実行する（１を加算するためには、単に生成されたすべてのシェアに１を加算する。−１で乗算するには、すべてのシェアを−１で乗算する）。そうして、生成された多項式のシェアを明かす代わりに、シェア保有者は、べき指数におけるシェアのみを明かす。例えば、生成された多項式がｖ（ｘ）であり、生成された付随多項式がｖ’（ｘ）であると仮定した場合、Ｓiはｖ（ｉ）およびｖ’（ｘ）を明かす代わりに、
【０１９２】
【数８９】
0004790122.tif 000090
を明かし、ＰＲＯＯＦ  ＯＦ  ＫＮＯＷＬＥＤＧＥ  ＯＦ  Ａ  ＤＩＳＣＲＥＴＥ  ＬＯＧからのプロトコルを用いる実際のシェアを知っていることを証明する。ｖ（０）≡（（−１）＋１）＝０  ｍｏｄ  еであり、ｖ（０）≡１  ｍｏｄ  φ（Ｎ）であることに留意されたい。
【０１９３】
シェア所有者は、多項式から和を実行し、ｔ＋１人のシェア所有者に分散される秘密和を獲得する。
【０１９４】
ｔ＋１人のシェア所有者は、その加法シェアをеで除算し、リマインダを発行する。また彼らは新しい加法シェアのための検証シェアも発行する（すべてのシェア所有者は、これらの検証シェアをеの累乗とし、それらを本来の加法シェア
【０１９５】
【数９０】
0004790122.tif 000091
と比較することで検証するはずである）。リマインダは加算され、еの倍数となる。シェア所有者の一人がこの倍数を加法シェアに加算する。そうして、これらのシェア所有者は、集合的にｄの加法シェアリングを保持する。
【０１９６】
ｔ＋１人のシェア所有者は、和から多項式を実行し、（ｔ，ｎ）安全なｄの多項式シェアリングを構築する。
【０１９７】
（プロトコルの有効性と変形）
典型的なシステムでは、ｈは１０００のオーダー（即ち、１０２４〜２０４８）である。整数の処理は、べき指数の大きさに４００未満を加算し、２-40の保証が妥当だと仮定する。値ｎは１０未満であり、ｋ＝４０が正当性の十分な保証となる証明のエラーの確率は２−ｋ-4であると予測される。
【０１９８】
それぞれｓｐ／２ビットの２つの無作為な素数からＲＳＡモジュラスを生成する確率は、約（ｓｐ／２）-2であるので、この手順は約ｓｐ2／４回繰り返されると予測される。各回の通信の複雑さはＯ（ｎｋ（ｓｐ））により拘束され、各回の計算の複雑さは、約Ｏ（ｎ（ｋ＋ｔ））モジュラスの累乗である。ｋおよびｔの現実的な値を仮定すれば、計算の複雑さは乗法プロトコルにより支配され、約２４ｎ（ｔ＋１）モジュラスの累乗となる。ＢｏｎｅｈおよびＦｒａｎｋｌｉｎにより論じらているように試行除算を実行しても、あまりよい効率は獲得できない。なぜなら、小さな素数に対するそれぞれの試行が、ロバストな乗法を含み、そのために各分散整数に対して約Ｏ（ｎｔＢ／１ｎＢ）モジュラスの累乗が試行されるからである。
【０１９９】
多大な実用的改善がなされ得る。まず、いったん可能なＮが生成されれば試行除算が行われ得るので、多くの分散二重素数テストが排除される。また、この試行除算の後に、それぞれのｐiおよびｑiが正当な範囲に存在するテストが行われた場合、その多くは保存され得る（この場合、シェア保有者の悪質な不正行為が判別され得るように、Ｎをテストして、Ｎが可能な範囲にあることを確実にしなればならない）。
【０２００】
おそらく、最大の改良は、それぞれのｐi  ｍｏｄ−ｔｈｅ−ｐｒｏｄｕｃｔ−Ｊ−ｏｆ−ｓｍａｌｌ−ｐｒｉｍｅｓ−ｕｐ−ｔｏ  ｓｏｍｅ−Ｂの値が明かされ、共有された値がＪの倍数であると仮定することからもたらされる。明かされた値の和はテストされ、Ｂまでの任意の小さな素数で除算可能かどうかが判断される。除算可能な場合、分散整数は素数ではなく、破棄される。勿論、これにより安全性が低減されるので、例えば、７までの素数に対してこれを実行することが好ましい。これにより、約６（ｌｏｇ（（２−１）（３−１）（５−１）（７−１）））だけ安全性が低減されるが、その数字が素数である確率が約５倍に増大し、従って、プロトコルに対する予測される回数は２５分の１に低減される（安全性の低減が懸念される場合、実行回数に大きな影響を及ぼすことなくｓｐを僅かに増加し得る。または、素数２および３のみを用い、安全性を約１ビット低減し、プロトコルの予測回数を約６だけ低減するのもよい）。
【０２０１】
上述の改良により、プロトコルにおけるモジュラスの累乗の総数は、約２４ｎ（ｔ＋１）×（ｓｐ／１０）2となり、これは約１０，０００である（試行除算に代えるので、（ｓｐ／２）2から低減される）。ｎ＝４およびｔ＝１の場合に対しては、２，０００，０００モジュラスの累乗が存在する。８，１０３までの試行除算を用いるＢｏｎｅｈ−Ｆｒａｎｋｌｉｎの非ロバストプロトコルは、約４８４モジュラスの累乗、約４０００少ない因数を実行する。
【０２０２】
すべての関係者が誠実だという見込みがある場合、「楽観的実行」を実施することにより、性能を向上させ得る。この概念は、プロトコル（加えてＢｏｎｅｈ−Ｆｒａｎｋｌｉｎからの試行除算）は実行するが、いかなる検証情報も伴わないというものである。即ち、付随多項式または検証シェアは生成されない。参加者がＲＳＡモジュラスの生成に失敗した各回の最後には、その回からの情報すべてが明かされる。明かされた情報が正当であることにすべての参加者が同意した場合、その回では不正は起こらなかったことになり、参加者は先へ進む。不正が発見された場合は、本願に記載されるロバストプロトコルに逆戻りする。ＲＳＡモジュールが発見された場合、参加者は、同じ多項式シェアリングであるがロバスト性の検証（即ち、付随多項式、検証シェア、知識の証明）を含むシェアリングを用いて回を戻す。すべての情報が正しく検証された場合には、ＲＳＡモジュールが用いられる。さもなくば、不正が発生してしまい、参加者はロバストプロトコルに戻る。
【０２０３】
この動作「モード」の問題は、不正は検証し得るが、どの参加者が不正を働いたかを正確に判別できないことである。誰が不正を働いたかを判別するためには、参加者は他の参加者へのメッセージに署名することを要求し、メッセージの受信者に、署名を受け入れるか、または全員にメッセージを明かすことを送信者に請うかのいずれかをさせることができる。署名が参加者の個人鍵に対するＲＳＡ署名だと仮定すれば、参加者は単一モジュラスの累乗を要求すると仮定し得る。さらに、１署名を１回ごとに用いるか、複数回にまたがって用いて、モジュラスの累乗の数を低減し得る。全体として本方法は、（署名および暗号の安全性とロバスト性に関する仮定によれば）尚、ロバストかつ安全であるが、約ｎ2倍（ｎは参加者の数である）の非ロバストプロトコルのモジュラスの累乗しか必要としない（これはｎが３ｔ＋１］よりも大きい場合にしか有効でないことに留意されたい。乗法プロトコルにおいて、正当なシェアを保証するためにゼロ知識［ＺＫ］を用いることはできないからである）。
【０２０４】
［ＢＧＭ］におけるように、より速いモジュラス累乗アルゴリズムを用いることによっても性能は向上し得る。なぜなら、これらのロバストプロトコルでは、参加者が同じ基数およびモジュラスに対して多くの累乗を実行するからである。
【０２０５】
別なる有効性の源は、無作為オラクル［ＦＳ８６］との計算による区別は不能と考えられている一般的な１方向ハッシュ関数から導出され得る自己呼びかけ記号列の公知の方法を用いることにより、ゼロ知識証明における不正回数からもたらされる。
【０２０６】
分散プロトコルまたは暗号鍵に対する多くの数学的操作の適用を向上させるために補助プロトコルが組み合わせられ得る。そのような操作は、乗法、反転、加法、および累乗を含む。上述の一例は、ＤＳＳ分散プロトコルである。
【０２０７】
（プロトコルの種類）
いったん合成Ｎが確立されれば、これを、分散ＲＳＡシステムとして以外に、様々な暗号プロトコルにおいて用いる数々の方法がある。
１．当事者は「合成ＥｌＧａｍａｌシステムを起動し得る。彼らは無作為要素ｇを引き出し、公開鍵ｙ＝ｇxを生成する。ここでｘは加法または多項シェアリングスキームのいずれかを用いて当事者間で共有される。
２．ユーザは、Ｎのアベイラビリティを用いることにより識別プロトコルに対する登録をし、平方剰余を生成して、その平方根は秘密にされる。
３．ユーザはＹａｏの秘密ビット交換プロトコルに携わり、ここでＮによる値を暗号化することと、ビットごとに解読を明かすこととを両方同時に行う。
４．ユーザは（е，Ｎ）を用いて、ＲＳＡを公開関与スキームとして用いる（即ち、１方向関数として用いる）。これは、過半数が公開を望まない限り公開できない。これの適用の１つは、平文の第三者寄託である。