distributed - 分散乱数生成

Question

N 人の参加者のネットワークが、1 から M までの数字がランダムに選択されたことに同意する方法があるかどうか疑問に思っていました。(例: どの参加者にも影響されない) これは、n=2 および m=2 の値について、コイン投げプロトコルによって解決されました。N と M の任意の値に対して機能するソリューションを知っている人はいますか?

Answer 1

編集

より良いアルゴリズム (wnoise に感謝):

1. 全員が0からM-1までの秘密の数字を選ぶ
2. 誰もが自分の番号に大量のランダムガンクを追加し、安全なハッシュで結果をハッシュします
3. 誰もがこのハッシュを他の人に伝えます
4. 誰もが自分の秘密の番号と、それに追加したランダムなガンクを他の人に伝えます
5. 数値とハッシュ+ガンクが一致することを全員が確認します
6. すべての秘密の数字をモジュロ M で加算し、1 を加算して最終結果を取得します。

参加者として、私は最終結果に完全な影響力を持っていたことを知っているので、これに満足する必要があります.秘密の番号の選択に応じて、最終的な番号は何でもかまいません. 誰も私の番号を予測できなかったので、彼らも最終的な結果を予測できなかった.

ブロードキャスト アプローチで必要になると思われる 3M^2 からのメッセージを減らす方法はありますか?

ハッシュの発行だけがブロードキャストでなければならないと思いますが、それでも O(M^2) です。これを回避する唯一の方法は、デジタル署名キーを事前に交換するか、信頼できる通信ハブを用意することだと思います。

Edit2 - ハッシュ化はどれくらい安全ですか?

考えられる攻撃は次のとおりです。

1. ハッシュの衝突を生成できれば、同じハッシュを持つ 2 つの秘密の番号が得られます。したがって、他の全員の秘密の番号を知ったら、どの秘密の番号を公開するかを選択して、2 つの可能な結果のいずれかを選択できます。
2. PRNG を使用して秘密の番号とランダムなガンクを生成した場合、ハッシュをブルート フォースしようとする攻撃者は、可能なすべての番号とガンクを試す必要はなく、PRNG の可能なすべてのシードのみを試す必要があります。
3. PRNG に関する情報を判断するために、誰もが明らかにする数字とガンクを使用します。シードを推測またはブルート フォースするか、出力から内部状態を計算することができます。これにより、次回彼らが生成する数値を予測することができ、ブルート フォース攻撃の検索スペースを狭めることができます。

したがって、

1. 信頼できる、途切れのないハッシュ アルゴリズムを使用します。
2. 大きなシード/状態を持つ暗号的に安全な乱数ジェネレーターを使用し、エントロピーの適切なソースからシードしてみてください。

Answer 2

人々が単一の数字のランダム性に同意できるかどうかはわかりません。統計にあるはずです。多くの乱数の統計がここから取得した数字の統計と一致する場合、私はあなたの数字をランダムと見なしますが、ネットワーク上の次の人物 N+1 については知りません。

Answer 3

これはおそらくあなたが探しているものではありませんが、このスレッドを開始するにはどうすればよいですか -
リーダーを選択し、リーダーに番号を選択させ、その番号を全員に配布します。