Asignar al azar N Elements a N Agentes de manera que cada agente solo conozca su propio elemento

Question

Problema

Estoy trabajando en una aplicación que involucra barajando y distribuyendo a los jugadores. Como un desafío, traté de resolver este problema de una manera que no requiere un intermediario de confianza.

En otros términos, la tarea es encontrar un algoritmo distribuido que

• Asigna de manera única $ n $ números de agentes $ 1..n $
• permite que cada agente no sepa nada sobre la tarea, pero su propia
• Al revelar la asignación, permite que otros jugadores verifiquen la asignación

También asumimos que saber que la asignación de otros es una ventaja para cada agente, y revelar su propia desventaja prematuramente. También se supone que los agentes pueden hablar entre sí de una manera oculta de todos los demás agentes.

Solución parcial

La solución que se me ocurrió con las obras solo bajo el supuesto de que los adversarios no colaboran.

La idea es crear un conjunto de $ n $ imponible, y asigne a cada agente exactamente un incondicional. Luego, el conjunto se pasa del agente al agente de un orden acordado, oculto de todos los demás, hasta que cada agente recibió el conjunto exactamente una vez. Cada vez que un agente recibe el conjunto, cambia su noce con uno nuevo, memoriza el nuevo nonce, y confirma el recibo del conjunto a los demás. Todo este procedimiento se realiza dos veces, en qué punto, todos los agentes han recibido el establecido al menos una vez después de que todos los demás agentes intercambiaran sus no sucesiones, lo que hace imposible reconocer y, por lo tanto, mapear a los otros agentes.

Cuando el último agente recibe el establecido la segunda vez, la comparte con todos, y todos los agentes confirman a los demás que su nove está contenido en el conjunto. Luego, los agentes asignan un número a cada uno que no sea en el conjunto según una semilla aleatoria acordada, dándonos la asignación única requerida.

Para permitir la verificación de propiedad, en lugar de las noncias, los agentes colocan el valor de la hash de su increta en el conjunto, revelando la noce real solo cuando se requiere la verificación.

---

El problema con esta solución es que si los adversarios se les permite colaborar, cada vez que un adversario recibe el conjunto, pueden comparar sus versiones, identificar cambios y potencialmente derivar de qué no pertenecen a otros agentes, lo que les permite saber qué número consiguió asignado a ellos.

¡Todas las ideas son apreciadas!

Answer 1

Este problema es parte de un conjunto de problemas conocidos como Mental Poker .

Hay un artículo excelente y pequeño por shamir , Rivest y Adleman que describen una forma práctica sobre cómo implementar dicho algoritmo.

El resumen es oro:

¿Pueden dos jugadores potencialmente deshonestos jugar un juego justo de póquer sin usar ninguna tarjeta (por ejemplo, por teléfono)?

Este documento proporciona las siguientes respuestas:

1. no. (Prueba matemática rigurosa suministrada.)
2. sí. (Protocolo correcto y completo dado.)

Básicamente, desde un punto de vista teórico de la información, la reproducción de un juego de este tipo es imposible sin un tercero de confianza, pero es factible diseñar un protocolo utilizando funciones criptográficas más conocidas y duras.

---

El algoritmo funcionará de la siguiente manera:

Supongamos que tiene $ n $ no tes (números de $ 1 $ a $ n $ ). Cada participante en el protocolo tiene acceso a funciones secretas $ e_i $ y $ d_i $ que se utilizan para cifrar y descifrar datos. Estas funciones deben satisfacer pocas propiedades, lo que analizaremos más tarde.

El primer participante recibe el conjunto completo de noces. Cifra cada incremento con su función secreta $ e_1 $ , los arrastra al azar, y pasa los datos resultantes a segundo participante.

El segundo participante hará lo mismo, pero en este caso no tiene impuestos, sino una permutación aleatoria de las no áreas cifradas. También cifrará cada elemento con su propia función secreta $ e_2 $ y recuperar nuevamente los datos.

Luego, tercero participante, y así sucesivamente, hasta que todos los participantes se han barajado y encriptado los datos con su función secreta.

En general, el proceso de configuración es:

data = [1..n]
for i in [1..n]:
    data = [e_i(nonce) for nonce in data]
    shuffle(data)

Después de esta configuración, cada elemento de data son los noces cifrados con todas las funciones secretas $ e_i $ en un orden aleatorio desconocido para cualquier participante.

Observe que en este punto es imposible para cada participante deducir cada increíble sin la ayuda de otros participantes. Y es suficiente que uno de los participantes para barajar los datos completamente aleatorios para eliminar cualquier posible sesgo en el orden resultante, independientemente si algún participante malicioso intenta sesgar el pedido.

Participante $ i $ se le asigna el noce en la posición $ i $ . Para recuperar dicha nonce, el participante $ i $ se le pregunta a un participante $ j \ neq i $ para descifrar el Valor con su función secreta $ d_j $ a su vez. Al final, el participante $ i $ tendrá su inconveniente solo encriptado con su propia función secreta $ e_i $ por lo Puede recuperarlo usando $ d_i $ .

Recuperación de nonce $ i $ :

nonce_i_encrypted = data[i]
for j in [1..n]:
    if j == i:
        continue
    nonce_i_encrypted = d_j(nonce_i_encrypted)

nonce_i = d_i(nonce_i_encrypted)

Al final de este procedimiento, cada participante conoce su propia nonce, pero ningún otro participante sabe nada al respecto.

Después de usar estos valores para su problema actual, un jugador puede afirmar que realmente están en control de tal nonce, ya sea por la publicación de las funciones de secretos $ e_i $ y $ d_i $ , para que todos puedan calcular localmente todos los valores, o descifrar el valor data[i] después del primer paso, pero antes del segundo paso, publicando y luego use este valor en la entrada en El segundo paso para descifrarlo completamente.

Las funciones $ e_i $ y $ d_i $ deben tener las siguientes propiedades:

1. $ e_i (x) $ es la versión cifrada de un mensaje $ x $ bajo la tecla < Span Class="Math-Container"> $ i $ ,
2. $ d_i (e_i (x))= x $ para todos los mensajes $ x $ y llaves $ i $ ,
3. $ e_i (e_j (x))= e_j (e_i (x)) $ para todos los mensajes $ x $ y llaves $ i $ y $ j $ ,
4. Dado $ x $ y $ e_i (x) $ es computacionalmente imposible para un criptoalista Derive $ i $ , para todos $ x $ y $ i $ , <

/ li>

Dados cualquier mensaje $ x $ y $ y $ , es computacionalmente imposible encontrar llaves < Span Class="Math-contenedor"> $ i $ y $ j $ tal que $ e_i (x )= e_j (y) $ .

Como se indica en el documento, la mayoría de estas suposiciones son de alguna manera común, excepto por la propiedad 3), lo que dice que las funciones de cifrado deben conmutar.

Proponen un esquema de cifrado simple que satisface estas propiedades. Digamos que todos los participantes acuerdan en algún gran número primo $ P $ (está bien si se fija en el protocolo). Y cada participante elige secretamente un número aleatorio $ k_i $ tal que $ gcd (k_i, p - 1)= 1 $ < / span>. Digamos $ q_i $ es un valor que $ k_i \ cdot q_i \ equiv. 1 \ mod (p -1) $ < / span>. Luego, el participante $ i $ puede usar funciones secretas:

$$ E_I (x)= x ^ {k_i} \ mod (p) $$ $$ d_i (y)= y ^ {q_i} \ mod (p) $$

Algunas advertencias sobre este algoritmo: los participantes no pueden hacer trampa de tal manera que el colusión los beneficia a aprender la nonce sobre el otro compañero (a menos que, por supuesto, $ n-1 $ < / SPAN> Los participantes colnan, y solo queda una nonce). Sin embargo, los participantes maliciosos pueden atacar el protocolo sin participar, estancando efectivamente el proceso de negociación, ya que se requieren muchas acciones de cada participantes mientras están tratando las noces. También pueden producir gibberish, pero esto se puede mitigar extender el protocolo para detectar qué participante fue el culpable y penalizar a dicho participante a un nivel superior.

---

Implementé este algoritmo para un juego de póker en cerca de Blockchain . Puedes ver el código en óxido aquí . Observa que no haya ningún tercero de confianza en un bloque de bloques, pero hay un entorno informático de confianza que todos los participantes pueden usar como mecanismo para ejecutar este protocolo.