Póquer mental es el nombre común para un conjunto de problemas criptográficos que implican jugar un juego limpio a distancia sin la necesidad de un tercero de confianza . El término también se aplica a las teorías que rodean estos problemas y sus posibles soluciones. El nombre proviene del juego de cartas póquer , que es uno de los juegos a los que se aplica este tipo de problema. Problemas similares descritos como juegos de dos partes son el lanzamiento de una moneda a distancia por parte de Blum , el problema de los millonarios de Yao y la transferencia inconsciente de Rabin .
El problema se puede describir así: "¿Cómo se puede permitir que sólo actores autorizados tengan acceso a cierta información sin utilizar un árbitro confiable?" (Eliminar al tercero de confianza evita el problema de intentar determinar si se puede confiar en el tercero o no, y también puede reducir los recursos necesarios).
En el póquer, esto podría traducirse como: "¿Cómo podemos asegurarnos de que ningún jugador esté apilando el mazo o mirando las cartas de otros jugadores cuando nosotros mismos estamos barajando el mazo?". En un juego de cartas físico, esto sería relativamente sencillo si los jugadores estuvieran sentados frente a frente y se observaran unos a otros, al menos si se puede descartar la posibilidad de hacer trampas convencionales. Sin embargo, si los jugadores no están sentados en el mismo lugar, sino en lugares muy separados y se pasan el mazo completo entre ellos (por ejemplo, mediante el correo postal ), esto de repente se vuelve muy difícil. Y para los juegos de cartas electrónicos, como el póquer en línea , donde la mecánica del juego está oculta para el usuario, esto es imposible a menos que el método utilizado sea tal que no permita que ninguna de las partes haga trampa manipulando u observando inapropiadamente la "baraja" electrónica. .
Se han sugerido varios protocolos para hacer esto, el primero por Adi Shamir , Ron Rivest y Len Adleman (los creadores del protocolo de cifrado RSA ). [1] Este protocolo fue el primer ejemplo de dos partes que realizan computación segura en lugar de transmisión segura de mensajes, empleando criptografía; Más tarde, debido a la filtración de información parcial en el protocolo original, esto llevó a la definición de seguridad semántica por parte de Shafi Goldwasser y Silvio Micali . El concepto de póquer mental multijugador se introdujo en el libro Cryptoprotocols de Moti Yung de 1984. [2] Posteriormente, el área evolucionó hasta convertirse en lo que se conoce como protocolos de computación multipartita seguros (para dos partes y también para varias partes).
Un posible algoritmo para barajar cartas sin el uso de un tercero de confianza es utilizar un esquema de cifrado conmutativo . Un esquema conmutativo significa que si algunos datos se cifran más de una vez, el orden en el que se descifran estos datos no importará.
Ejemplo: Alice tiene un mensaje de texto sin formato . Ella cifra esto, produciendo un texto cifrado confuso que luego le entrega a Bob . Bob vuelve a cifrar el texto cifrado, utilizando el mismo esquema que Alice pero con otra clave . Al descifrar este mensaje doblemente cifrado, si el esquema de cifrado es conmutativo, no importará quién lo descifre primero.
Un algoritmo para barajar cartas utilizando cifrado conmutativo sería el siguiente:
El mazo ahora está barajado.
Este algoritmo puede ampliarse para un número arbitrario de jugadores. Los jugadores Carol , Dave , etc. sólo necesitan repetir los pasos 2-4 y 8-10.
Durante el juego, Alice y Bob escogerán cartas del mazo, identificando en qué orden se colocan en el mazo barajado. Cuando cualquiera de los jugadores quiera ver sus cartas, solicitará al otro jugador las claves correspondientes. Ese jugador, al comprobar que el jugador solicitante tiene derecho a mirar las cartas, pasa las claves individuales de esas cartas al otro jugador. La verificación es para garantizar que el jugador no intente solicitar claves para tarjetas que no le pertenecen a ese jugador.
Ejemplo: Alicia ha elegido las cartas del 1 al 5 del mazo barajado. Bob ha elegido las cartas del 6 al 10. Bob solicita mirar las cartas que le han asignado. Alice está de acuerdo en que Bob tiene derecho a mirar las tarjetas 6 a 10 y le da las claves de sus tarjetas individuales A 6 a A 10 . Bob descifra sus tarjetas usando las claves de Alice y la suya propia para estas tarjetas, B 6 a B 10 . Bob ahora puede ver las cartas. Alice no puede saber qué tarjetas tiene Bob porque no tiene acceso a las claves B 6 a B 10 de Bob , necesarias para descifrar las tarjetas.
El esquema de cifrado utilizado debe ser seguro contra ataques de texto sin formato conocido : Bob no debe poder determinar la clave A original de Alice (o una cantidad suficiente para permitirle descifrar cualquier tarjeta que no tenga) basándose en su conocimiento de los valores no cifrados de las cartas que ha robado. Esto descarta algunos esquemas de cifrado conmutativo obvios, como simplemente realizar XOR en cada tarjeta con la clave. (Usar una clave separada para cada tarjeta incluso en el intercambio inicial, lo que de otro modo haría que este esquema fuera seguro , no funciona ya que las tarjetas se barajan antes de devolverlas).
Dependiendo del mazo acordado, este algoritmo puede ser débil. Al cifrar datos, ciertas propiedades de estos datos pueden conservarse desde el texto sin formato hasta el texto cifrado. Esto puede usarse para "etiquetar" ciertas tarjetas. Por lo tanto, las partes deben acordar una baraja en la que ninguna carta tenga propiedades que se conserven durante el cifrado.
Christian Schindelhauer describe protocolos sofisticados para realizar y verificar una gran cantidad de operaciones útiles en cartas y pilas de cartas en su artículo de 1998 "A Toolbox for Mental Card Games" [SCH98]. El trabajo se refiere a operaciones de propósito general (enmascarar y desenmascarar cartas, barajar y rebarajar, insertar una carta en una pila, etc.) que hacen que los protocolos sean aplicables a cualquier juego de cartas. Los protocolos criptográficos utilizados por Schindelhauer se basan en la residuosidad cuadrática y el esquema general es similar en espíritu al protocolo anterior. La exactitud de las operaciones se puede verificar mediante pruebas de conocimiento cero , de modo que los jugadores no necesitan revelar su estrategia para verificar la exactitud del juego.
La biblioteca C++ libtmcg [STA05] proporciona una implementación de la caja de herramientas de Schindelhauer. Se ha utilizado para implementar una versión segura del juego de cartas alemán Skat , logrando un rendimiento modesto en el mundo real. El juego Skat lo juegan tres jugadores con una baraja de 32 cartas, por lo que requiere mucho menos procesamiento computacional que un juego de póquer en el que entre cinco y ocho jugadores usan una baraja completa de 52 cartas.
Hasta la fecha, los enfoques de póquer mental basados en el protocolo estándar Alice-Bob (arriba) no ofrecen un rendimiento lo suficientemente alto para jugar en línea en tiempo real. El requisito de que cada jugador cifre cada tarjeta impone una sobrecarga sustancial. Un artículo reciente de Golle [GOL05] describe un protocolo de póquer mental que logra un rendimiento significativamente mayor al explotar las propiedades del juego de póquer para alejarse del modelo de cifrado aleatorio. En lugar de barajar las cartas y luego repartirlas según sea necesario, con el nuevo enfoque, los jugadores generan números aleatorios (encriptados) sobre la marcha, que se utilizan para seleccionar la siguiente carta. Cada carta nueva debe compararse con todas las cartas que ya se han repartido para detectar duplicados. Como resultado, este método es especialmente útil en juegos de estilo póquer, en los que el número de cartas repartidas es muy pequeño en comparación con el tamaño de toda la baraja. Sin embargo, el método necesita que todas las cartas que ya se han repartido sean conocidas por todos, lo que en la mayoría de los juegos de estilo póquer sería contrario a su propósito.
El algoritmo de generación de tarjetas requiere un criptosistema con dos propiedades clave. El cifrado E debe ser aditivamente homomórfico , de modo que E(c 1 )*E(c 2 ) = E(c 1 + c 2 ) . En segundo lugar, las colisiones deben ser detectables sin revelar el texto sin formato. En otras palabras, dadas E(c 1 ) y E(c 2 ) , debe ser posible responder si c 1 = c 2 , sin que los jugadores aprendan ninguna otra información (específicamente, las identidades de c 1 y c 2 ). El esquema de cifrado Elgamal es sólo un ejemplo de un sistema bien conocido con estas propiedades. El algoritmo funciona de la siguiente manera:
De esta manera, los jugadores solo necesitan calcular el cifrado de las cartas que realmente se usan en el juego, más algunos gastos generales para las colisiones que son pequeños siempre que la cantidad de cartas necesarias sea mucho menor que el tamaño de la baraja. Como resultado, este esquema resulta ser entre 2 y 4 veces más rápido (medido por el número total de exponenciaciones modulares) que el protocolo más conocido [JAK99] que realiza una mezcla completa utilizando redes mixtas .
Tenga en cuenta que la generación de números aleatorios es segura siempre que un jugador genere números aleatorios válidos. Incluso si k-1 jugadores se confabulan para generar el número r* , siempre que el k -ésimo jugador genere verdaderamente un número aleatorio , la suma sigue siendo uniformemente aleatoria en {0, 51}.
Medido en términos del número de cifrados de agente único, el algoritmo en [GOL05] es óptimo cuando no ocurren colisiones, en el sentido de que cualquier protocolo que sea justo para cada jugador debe realizar al menos tantas operaciones de cifrado. Como mínimo, cada agente debe cifrar cada tarjeta que realmente utilice. De lo contrario, si algún agente no participa en el cifrado, entonces ese agente es susceptible de ser engañado por una coalición de los jugadores restantes. Sin que el agente que no encripta lo sepa, los otros agentes pueden compartir las claves para que todos puedan conocer los valores de todas las tarjetas. Por lo tanto, cualquier enfoque que dependa de los agentes para realizar el cifrado debe centrarse en esquemas que minimicen el efecto de las colisiones si se quiere lograr un mejor rendimiento.
Cualquier protocolo de póquer mental que dependa de que los jugadores realicen el cifrado está sujeto al requisito de que cada jugador cifre cada carta que se reparta. Sin embargo, al hacer suposiciones limitadas sobre la confiabilidad de terceros, se pueden lograr protocolos significativamente más eficientes. El protocolo de elección de cartas sin barajar podrá adaptarse para que el cifrado sea gestionado por dos o más servidores. Suponiendo que los servidores no estén en colusión, dicho protocolo es seguro.
El protocolo básico que utiliza dos servidores es el siguiente:
En este protocolo, los servidores S1 y S2 deben confabularse para que cualquiera de ellos pueda conocer los valores de alguna tarjeta. Además, como los jugadores deciden en última instancia qué cartas se reparten, los servidores no confiables no pueden influir en el juego en la medida en que es posible en el póquer en línea tradicional . El esquema puede ampliarse para permitir más servidores (y, por lo tanto, mayor seguridad), simplemente incluyendo servidores adicionales en el cifrado inicial. Finalmente, el primer paso del protocolo se puede realizar fuera de línea, lo que permite precalcular y almacenar en caché una gran cantidad de "mazos" cifrados y barajados, lo que da como resultado un excelente rendimiento en el juego.
