¿Cómo realizar un experimento de lanzamiento de moneda justo por teléfono?

Question

Hace poco mi amigo me hizo esta pregunta. Supongamos que los dos individuos que participan en un sorteo no están cerca el uno del otro, pero pueden comunicarse por teléfono. ¿Cómo se puede construir un experimento de lanzamiento de moneda justo que sea mutuamente aceptable para ambos? No pueden ponerse de acuerdo en una función de cantidades como la hora o el número de teléfono, ya que éstas deciden el ganador a priori (antes de realizar el experimento).

Les sugerí que desconectaran la llamada y lo volvieran a intentar; el que consiguiera comunicarse con el otro primero sería el ganador. Pero la máquina de estados implicada aquí es un poco complicada para obtener las simples probabilidades (0,5,0,5).

P.D.: No confían el uno en el otro, por lo que uno de ellos no puede lanzar una moneda justa y transmitir su resultado al otro. Que ambos lancen simultáneamente tampoco funciona, ya que la segunda persona tiene el incentivo de mentir cuando se comunican los resultados.

Answer 1

Esta es una forma de hacerlo. Llamemos a las dos partes Alice y Bob (como es popular hacer en criptografía y en informática teórica más ampliamente en estos días).

Alice y Bob acuerdan una función hash segura $h$ . Alice elige una cadena al azar $r_A$ y Bob elige una cadena aleatoria $r_B$ . Bob le dice a Alice $r_B$ .

Ahora, Alice lanza una moneda, llama al resultado $x$ . Alice envía $h(x,r_A,r_B)$ a Bob y le pide que llame al sorteo. Digamos que Bob llama $y$ . Entonces Alice le dice a Bob $(x,r_A)$ y puede comprobar por sí mismo que $x = y$ comprobando que $h(x,r_A,r_B) = h(y,r_A,r_B)$ . De este modo, si Bob se equivocó, Alice puede demostrar que se equivocó.

Obviamente, si Bob lanza la moneda correctamente, entonces los dos hashes coinciden. Además, es extremadamente Es difícil para Alice hacer trampa porque si Bob dice "cruz", por ejemplo, cuando el lanzamiento de la moneda fue efectivamente "cruz", pero Alice quiere engañarlo para que piense que fue "cara", tendría que inventar una cadena aleatoria $r$ tal que $h(H,r,r_B) = h(T,r_A,r_B)$ que es difícil por la suposición de que $h$ es una función hash segura y el hecho de que Bob haya elegido $r_B$ . Esencialmente, el propósito de $r_A$ y $h$ son hacer que Alice se "comprometa" con su lanzamiento inicial $x$ . El punto de $r_B$ es para que, sin ella, Alicia pueda elegir alguna $r_A$ para el que conoce otra cadena $r$ que podría permitirle mentir.

Answer 2

Esto fue respondido por Manuel Blum en 1983.

http://dl.acm.org/citation.cfm?id=1008911

Blum propuso un esquema que es similar en seguridad a RSA.

Edición: Aquí hay un resumen del enfoque de Blum.

1. Alice elige dos números primos grandes $p$ et $q$ con la propiedad $p \equiv 3 \mod 4$ y $q \equiv 3 \mod 4$ . Calcula el número $n = pq$ y se lo lee a Bob por teléfono. Ella guarda los números $p$ et $q$ secreto.

2. Bob elige un número entero al azar $x$ entre $1$ et $n$ . Calcula el cuadrado $a = x^2 \mod n$ y se lo lee a Alice por teléfono. Guarda el número $x$ secreto.

3. Como Alicia conoce la factorización de n, puede calcular las raíces cuadradas de $a$ modulo $n$ . Hay cuatro de estas raíces cuadradas, digamos $x$ et $n-x$ et $x'$ et $n-x'$ . Alice puede calcularlas todas, pero no sabe qué número ha elegido Bob. Alice elige una de estas raíces cuadradas y se la lee a Bob por teléfono.

4. Bob compara el número que le han leído por teléfono con el número que ha elegido. Si Alice le comunicó el número $x$ o $n-x$ le dice a Alice "tú ganas, pero ahora debes decirme los factores $p$ et $q$ ". Entonces Alice lee los factores $p$ et $q$ por teléfono, y Bob puede comprobar que ambos son números primos y que $n = pq$ . El juego ha terminado, y Alice ha ganado.

5. Si Alicia comunicó el número $x'$ o $n-x'$ Bob puede utilizar esta información y el hecho de que conoce la otra raíz cuadrada, es decir $x$ para encontrar los factores de $n$ . Lo hace, y le dice a Alice "tú pierdes, aquí están tus factores". El juego ha terminado, y Bob ha ganado.

Answer 3

Una persona imagina un número $x$ calcula su hash y dice ese hash en el teléfono, prometiendo que el valor de $x$ para ser revelado más tarde hashes al hash hablado. A continuación, la otra persona dice el tiro, que es un poco. Entonces la primera persona revela $x$ el segundo verifica que su hash corresponde a lo que se escuchó por teléfono, y si el bit más bajo de $x$ coincide con el tiro entonces la moneda es HEADS ; de lo contrario, la moneda es TAILS .

Answer 4

El primero hace una pregunta dura de sí/no y el segundo se compromete a responder lo suficientemente rápido como para que encontrar la respuesta sea casi imposible. Entonces ambos pueden comprobar cuál era la respuesta real. Algunos ejemplos de preguntas son "¿el número primo número 1000 contiene un dígito 9" o "es el número de celdas negras en la 1000ª iteración de la regla 110 par" . Se puede encontrar una pregunta que incluso un ordenador tardaría un minuto en responder. Exigir una respuesta rápida a la segunda persona es la clave.

Answer 5

Una de las partes elige una ciudad de su estado; la otra parte indica inmediatamente impar o par. Digamos que el código postal termina en un número par. Entonces ganaría Even y perdería impar. Así es como hemos hecho antes un "lanzamiento de moneda" por teléfono.