Una lotería de la que puedes estar convencido de que es justo

27

(Lo siento si esto es bien conocido). Me gustaría darle algún artículo a uno de los agentes, para que el agente obtenga el artículo con probabilidad . ¿Existe una herramienta criptográfica (u otra) para que cada agente (e incluso cada observador) pueda convencerse de que el sorteo al azar fue realmente justo?j p ikjpi

cr.crypto-security Gil Kalai
fuente
1
¿Se les permite a los agentes saber .. p k ? p0pk
Mike Samuel
¿Has visto esto? ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4232861
dspyz

Respuestas:

19

Si entiendo el problema correctamente, parecería que el público lanzara una moneda con cara . Parece que hay muchas maneras de hacer esto si asumes un poco de compromiso. Un ejemplo sería hacer que cada parte genere un número entero aleatorio entre 0 y k - 1 , utilizando el compromiso de bits para comprometerse públicamente con esa cadena de bits. Luego, una vez que cada agente se ha comprometido, todos revelan públicamente su número entero secreto. El agente ganador es entonces el indexado por la suma de los enteros módulo k . Si incluso un agente es honesto, el cambio debe ser aleatorio.kk−1k

Por supuesto, un problema con esto es que requiere un poco de compromiso. Los esquemas teóricos de información para el compromiso de bits son imposibles para la computación clásica y cuántica (aunque Adrian Kent recientemente propuso un esquema que explota la relatividad). Sin embargo, el compromiso de bit seguro se puede lograr con supuestos computacionales.

Joe Fitzsimons
fuente
2
Mi problema con este enfoque es que si desea convencer a muchos observadores externos de la equidad, cada uno de ellos debe comprometerse un poco y debe asegurarse de que cada uno de ellos revelará la prueba de su compromiso. No puede simplemente ignorar la parte de un observador que no revela su prueba porque entonces el último observador que revela podría manipular el resultado de la lotería al decidir si revela o no su prueba.
Zsbán Ambrus
1
@ user8067: No creo que sea posible sin interacción o sin confiar en que al menos una de las partes sea honesta. La razón por la que digo esto es que si la aleatoriedad inicial está realmente predeterminada a través de una conspiración de todos los participantes en ese punto, entonces todo el proceso es determinista y no aleatorio. Sin embargo, el problema requiere que el proceso sea aleatorio, por lo que parece ser lo mejor que puede hacer.
Joe Fitzsimons
2
No estoy convencido de que sea posible.
Joe Fitzsimons
2
@RickyDemer: No hay suficiente información en la pregunta para saber qué modelo de adversario es aplicable aquí. Si Gil nos dijera exactamente para qué sirve, entonces sería más fácil probar si un esquema específico cumple o no con sus requisitos. Pero dicho esto, no tengo dudas de que Gil es más que capaz de verificar si nuestras respuestas satisfacen o no sus necesidades.
Joe Fitzsimons
2
@RickyDemer: No me queda claro cuál es el modelo obvio para este caso. Depende en gran medida de la configuración, y no es obvio cuáles deberían ser los supuestos predeterminados. Es un poco demasiado negativo y comenzar a actuar como si mi respuesta y la de Lev estuvieran equivocadas. No incluyen explícitamente la advertencia señalada en la respuesta de Adam. Tenga en cuenta que no estoy editando mi respuesta, porque sin más información de Gil, no veo que tenga sentido adivinar sobre el modelo adversario, por lo que lo dejo lo más general posible (sin especificar si el el compromiso de bit no debe ser maleable).
Joe Fitzsimons
15

Como otros usuarios han insinuado, este es un problema bien estudiado en criptografía. Se llama "cambio de moneda" y es un caso especial de cómputo multiparte.

De qué protocolo depende realmente el trabajo depende mucho del contexto.

  • En la configuración "independiente", el protocolo se ejecutará de forma aislada, sin que los jugadores participen en otros protocolos (o, de hecho, en cualquier interacción con el mundo exterior) al mismo tiempo. Hay un tratamiento maravillosamente completo de esto en el libro de texto de Oded Goldreich "Fundamentos de la criptografía" (volumen 2, creo).

Solo para dar una idea de lo sutil que es, el protocolo "todos se comprometen con valores aleatorios" sugerido por otro respondedor es inseguro si el esquema de compromiso que utiliza es maleable. Los esquemas de compromiso no maleables le brindan un protocolo seguro, pero son un poco complicados de diseñar.

  • En entornos donde los participantes están involucrados en otros protocolos concurrentes, desea un protocolo que sea componible . Existen varias nociones de componibilidad, pero la más fuerte, llamada componibilidad universal , requiere algunos supuestos de configuración adicionales (por ejemplo, una PKI o una cadena aleatoria común visible para todas las partes pero que ninguna de ellas puede controlar). Desgraciadamente, no conozco un tratamiento accesible para este tema. Pero mirar un artículo reciente sobre compilabilidad universal o compromiso no maleable sería un buen lugar para comenzar.
Adam Smith
fuente
1
"Una cadena aleatoria común visible para todas las partes pero que ninguna de ellas puede controlar" es exactamente lo que queremos generar.
Zsbán Ambrus
1
y después de resolver de alguna manera ese problema una vez, uno puede componer universalmente resuélvelo nuevamente (arbitrariamente muchas veces).
Creo que el compromiso de UC es conocido por la configuración de clave pública registrada (que es una suposición más fuerte que PKI) y la configuración de múltiples cadenas (que es una suposición más débil que la cadena aleatoria común).
2
¡Bienvenido al sitio, Adam!
Gil Kalai
11

Nota: lea los comentarios a continuación. Este protocolo parece tener problemas.

pj

{0,1}bb

Cualquier agente puede estar seguro de que el número aleatorio elegido fue uniforme al azar eligiendo su propio vector uniforme al azar. Para que cualquier observador esté convencido, tienen que confiar en que al menos un agente siguió el protocolo, pero si ninguno lo hizo, creo que nadie realmente quería una lotería justa para empezar.

Lev Reyzin
fuente
Lo siento Lev, acabo de notar tu respuesta. Cuando comencé a escribir una respuesta, no había nada aquí, pero parece que ambos obtuvimos respuestas muy similares.
Joe Fitzsimons
¡Sin preocupaciones! Parece que estamos en el camino correcto, entonces.
Lev Reyzin
Sí, en realidad creo que hay muchos documentos sobre esto en el contexto del lanzamiento de monedas, pero realmente no conozco esa literatura lo suficientemente bien como para dar una respuesta adecuada basada en ella.
Joe Fitzsimons
77
La primera referencia que conozco es: M. Blum. Lanzamiento de monedas por teléfono. CRYPTO 1981: 11-15. Se puede descargar en dm.ing.unibs.it/giuzzi/corsi/Support/papers-cryptography/…
Ryan Williams
44
Hay un ataque estándar, si utiliza esquemas de compromiso de bits estándar (por ejemplo, hashing). Consideremos el caso con dos partes, Alice y Bob, donde Alice va primero. Después de que Alice transmite su compromiso, Bob puede copiarlo. Después de que Alice abre su compromiso, Bob puede abrir el suyo ahora. Ahora sus vectores aleatorios son iguales, por lo que son xor a cero: Bob pudo forzar el valor final a cero, una contradicción del requisito de equidad.
DW
-3

Los observadores pasivos no pueden verificar que el dibujo no haya sido escenificado. Las entradas en el proceso pseudoaleatorio se pueden elegir para dar el resultado deseado.

Sin embargo, si el observador puede proporcionar un número aleatorio que sabe que es aleatorio Y asegurarse de que otros agentes no cambien sus entradas después (porque podrían compensar su efecto con sus entradas), entonces puede estar seguro de que el resultado fue realmente aleatorio .

Esto requiere un esquema de compromiso que no conocemos que esté matemáticamente demostrado que sea seguro, pero en la práctica se puede realizar utilizando hash seguro (como SHA3).

Considere este ejemplo:

ingrese la descripción de la imagen aquí

He hecho un ejemplo de implementación. Puede verlo en vivo aquí: https://mrogalski.eu/cl/ o verifique las fuentes en GitHub .

Marek Rogalski
fuente
1
Esto ya se observa en la respuesta de Joe.
Kaveh
1
¡La ilustración gráfica es muy bonita!
Gil Kalai
3
Los gráficos son muy bonitos, pero su respuesta no contiene nada que no esté en las respuestas existentes.
David Richerby