distributed - 分布式随机数生成

Question

我想知道是否有办法让 N 个参与者的网络同意随机选择从 1 到 M 的数字。（例如，不受任何参与者的影响）这已经通过抛硬币协议解决了 n=2 和 m=2 的值。有谁知道任何适用于任意 N 和 M 值的解决方案？

Answer 1

编辑

更好的算法（感谢 wnoise）：

1. 每个人都从 0 到 M-1 选择一个秘密数字
2. 每个人都会在他们的号码上附加大量随机垃圾，并使用安全哈希对结果进行哈希处理
3. 每个人都告诉其他人这个哈希
4. 每个人都告诉其他人他们的秘密号码，以及他们附加的随机垃圾
5. 每个人都验证数字和哈希 + gunk 匹配
6. 将所有秘密数字模M相加，然后加1得到最终结果

作为参与者，我应该对此感到满意，因为我知道我对最终结果有完全的影响——最终的数字可能是任何东西，这取决于我选择的秘密数字。因此，由于没有其他人可以预测我的数字，他们也无法预测最终结果。

有什么方法可以减少我怀疑广播方法需要的来自 3M^2 的消息？

我认为只有哈希发布必须是广播，但它仍然是 O(M^2)。我想解决这个问题的唯一方法是预先交换数字签名密钥，或者拥有一个受信任的通信中心。

Edit2 - 散列的安全性如何？

可能的攻击包括：

1. 如果我可以生成哈希冲突，那么我有两个具有相同哈希的秘密数字。因此，一旦我知道了其他人的秘密号码，我就可以选择要透露我的哪个秘密号码，从而选择两种可能的结果之一。
2. 如果我使用 PRNG 生成我的秘密数字和随机 gunk，那么试图暴力破解我的哈希的攻击者不必尝试所有可能的数字+gunk，只需尝试 PRNG 的所有可能种子。
3. 我使用每个人透露的数字+gunk 来确定有关他们的 PRNG 的信息——我可以尝试猜测或暴力破解种子，或从输出中计算内部状态。这有助于我预测他们下次会生成什么数字，从而缩小了暴力攻击的搜索空间。

因此，您应该

1. 使用可信的、完整的散列算法。
2. 使用具有大种子/状态的加密安全随机数生成器，并尝试从良好的熵源中播种。

Answer 2

我不知道人们是否可以就单个数字的随机性达成一致；它应该在统计中。如果许多随机数的统计信息与从此处获取的数字统计信息相匹配，那么我会认为您的数字是随机的，但我不知道网络上的下一个 N+1 人。

Answer 3

这可能不是您要查找的内容，而只是开始此线程如何-
选择领导者，让领导者选择号码，然后将号码分发给每个人。