Modificación a Blum ' protocolo de s de una moneda los bancos por teléfono para que un jugador puede ' t perder intencionalmente

Question

Blum del protocolo, como se describe aquí, http://www.math2803.gatech.edu/wp-content/uploads/CoinFlip.pdf para voltear una moneda sobre el teléfono funciona bien, excepto que no hay manera de asegurarse de que Bob no mentir y decir que él perdió en la final del protocolo. Si Bob afirma haber ganado, debe enviar la factorización de n a Alice, pero no hay tal verificación para cuando Bob dice que perdió.

Es allí cualquier modificación a este protocolo, de modo que Bob no intencional puede perder?

Answer 1

No es realmente una modificación del protocolo, pero ¿cómo es esto de un sorteo basado en la factorización de ser duro:

1. Alice elige dos grandes aleatoria de los números primos $p$$q$. Ella le dice a Bob su producto $pq$.

2. Bob elige un random bit $b\in\{0,1\}$. Él envía a Alice.

3. Alice revela $p$$q$.

4. Bob gana si su bit es la misma como poco 100 $\min(p,q)$.

---

El problema con esto es que no se cómo funciona-si el protocolo es realizado por escrito terminamos con una muestra aleatoria de bits que ninguna de las partes tiene una forma de control.

Sin embargo, ¿qué pasa si el protocolo no es completa? Esta tiene la característica de que Alice sabe que ha ganado antes de Bob. Si no le gusta el resultado, ella podría perder la conexión sin enviar el mensaje 3, la afirmación de que su equipo se estrelló y ella no recuerda $p$ $q$ más, o lo que sea.

Simplemente reiniciando el protocolo en ese caso no funciona -- si suponemos que el protocolo funciona a la perfección, la segunda vez, Alice acaba de firmar a sí misma un 75% en general la oportunidad de conseguir su mejor resultado.

Con el fin de garantizar la honestidad en completar el protocolo, parece que necesitamos una manera de castigar a un partido que deja de participar en el medio de ella. Sin embargo, dentro de los límites de la "moneda de lanzar" la metáfora, la única manera de hacerlo sería saber lo que Alice resultado deseado es y dictar la que ella pierde si de repente se va en silencio. Pero entonces, en el caso de Bob gana, ella podría igual de bien del estado "renunciaré" en lugar de enviar mensaje 3 -- y, a continuación, volvemos a la situación en su enlace.

Parece concebible que uno podría diseñar un protocolo donde las dos partes tienen la misma probabilidad de ser el primero en ser capaz de comprobar cuál es el resultado. Pero que realmente no ayuda -- si uno de los jugadores tiene una fuerte preferencia por un resultado, pero la otra es honesto/indiferente, todavía podemos obtener desequilibrado resultados si un jugador puede forzar un reinicio alegando problemas técnicos.