分布式随机数生成

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,只有PRNG的每个可能的种子.
3. 我使用每个人揭示的数字+ gunk来确定有关其PRNG的信息 - 我可以尝试猜测或强制种子,或者从输出中计算内部状态.这有助于我预测下一次他们将产生的数字,从而缩小搜索空间以进行暴力攻击.

因此,你应该

1. 使用可信,不间断的哈希算法.
2. 使用具有大种子/状态的加密安全随机数生成器,并尝试从良好的熵源中播种它.