Generación de números aleatorios distribuidos

Question

Me preguntaba si hay una forma de que una red de N participantes acepte que se eligió un número del 1 al M al azar. (por ejemplo, no influenciado por ninguno de los participantes) Esto se ha resuelto para valores de n = 2 ym = 2 por coin tossing protocol. ¿Alguien sabe de alguna solución que pueda funcionar para valores arbitrarios de N y M?

Answer 1

Editar

mejor algoritmo (wnoise gracias):

1. Cada uno recoge un número secreto de 0 a M-1
2. Cada uno añade una carga de suciedad al azar a su número y hashes el resultado con un hash seguro
3. Todo el mundo le dice a todos los demás este hash
4. Todos le cuentan a todos los demás su secreto número, además de la suciedad al azar se anexan a la misma
5. Cada uno verifica que los números y los hashes + Match mugre
6. Añadir todos los números secretos juntos módulo M, a continuación, añade 1 al obtener el resultado final

Como como participante, debería estar satisfecho con esto porque sé que tuve plena influencia sobre el resultado final; el número final podría haber sido cualquier cosa, dependiendo de mi elección de número secreto. Entonces, como nadie más podía predecir mi número, tampoco podrían haber predicho el resultado final.

¿Alguna manera de reducir los mensajes del 3M^2 que sospecho que requeriría un enfoque de transmisión?

Creo que solo la publicación hash tiene que ser una emisión, pero sigue siendo O (M^2). Supongo que la única forma de evitarlo sería preintercambiar claves de firma digital o tener un centro de comunicación de confianza.

Edit2 - ¿Qué tan seguro es el hashing?

ataques posibles incluyen:

1. Si puedo generar una colisión de hash entonces tengo dos números secretos con el mismo hash. Entonces, una vez que conozco los números secretos de todos los demás, puedo elegir cuál de mis números secretos revelaré, seleccionando uno de los dos posibles resultados.
2. Si genero mi número secreto y suciedad al azar usando un PRNG, entonces un atacante tratando de usar fuerza bruta mi hash no tiene que probar todos los números posibles + gunk, solo cada posible semilla para el PRNG.
3. Utilizo el número + mugre que todos revelan para determinar la información sobre sus PRNGs: podría intentar adivinar o forzar las semillas, o calcular el estado interno de la salida. Esto me ayuda a predecir qué números generarán la próxima vez, lo que reduce el espacio de búsqueda para un ataque de fuerza bruta.

Por lo tanto, usted debe

1. utilizar un algoritmo de hash de confianza, ininterrumpida.
2. Use un generador de números aleatorios criptográficamente seguro que tenga una semilla/estado grande y trate de sembrarlo de una buena fuente de entropía.

Answer 2

Esto probablemente no es lo que estás buscando, pero sólo para empezar este hilo que tal esto -
Seleccione un líder, que el líder de elegir el número, distribuir el número de todos.

Answer 3

No sé si es posible que las personas estén de acuerdo con la aleatoriedad de un solo número; debería estar en las estadísticas. Si las estadísticas de muchos números aleatorios coinciden con las estadísticas de los números tomados del here, entonces consideraría su número al azar, pero no sé sobre el próximo tipo N + 1 en la red.