El póquer mental es el nombre común de un conjunto de problemas criptográficos que se refieren a jugar un juego justo 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 grupos son el lanzamiento de una moneda a distancia 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 confiable evita el problema de tratar de 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 las cartas o mirando las cartas de otros jugadores cuando estamos barajando las cartas nosotros mismos?". En un juego de cartas físico, esto sería relativamente sencillo si los jugadores estuvieran sentados frente a frente y observándose entre sí, al menos si se puede descartar la posibilidad de trampas convencionales. Sin embargo, si los jugadores no están sentados en el mismo lugar, sino en lugares muy separados y se pasan la baraja entera entre ellos (usando el correo postal , por ejemplo), 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 al 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 condujo a la definición de seguridad semántica por Shafi Goldwasser y Silvio Micali . El concepto de póquer mental multijugador fue introducido en el libro Cryptoprotocols de Moti Yung de 1984. [2] El área ha evolucionado más tarde en lo que se conoce como protocolos de computación multipartidaria seguros (para dos partes y también para múltiples partes).
Un algoritmo posible para barajar cartas sin recurrir a 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 que se descifran esos datos no importará.
Ejemplo: Alice tiene un mensaje de texto simple . Lo cifra, lo que produce un texto cifrado ilegible que luego le da 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:
Ahora la baraja está barajada.
Este algoritmo se puede ampliar para una cantidad arbitraria de jugadores. Los jugadores Carol , Dave , etc. solo necesitan repetir los pasos 2 a 4 y 8 a 10.
Durante el juego, Alice y Bob elegirán cartas del mazo, identificando el orden en el que se encuentran en el mazo barajado. Cuando uno de los jugadores quiera ver sus cartas, solicitará las llaves correspondientes al otro jugador. Ese jugador, tras comprobar que el jugador solicitante está autorizado a mirar las cartas, le pasa las llaves individuales de esas cartas al otro jugador. La comprobación sirve para garantizar que el jugador no intente solicitar llaves de cartas que no le pertenecen.
Ejemplo: Alice ha elegido las cartas 1 a 5 de la baraja barajada. Bob ha elegido las cartas 6 a 10. Bob pide ver las cartas que le han sido asignadas. Alice acepta que Bob tiene derecho a ver las cartas 6 a 10 y le da sus claves individuales de cartas A 6 a A 10. Bob descifra sus cartas utilizando tanto las claves de Alice como las suyas propias para estas cartas, B 6 a B 10. Bob ahora puede ver las cartas. Alice no puede saber qué cartas tiene Bob porque no tiene acceso a las claves de Bob B 6 a B 10 que son necesarias para descifrar las cartas.
El esquema de cifrado utilizado debe ser seguro contra ataques de texto plano conocidos : Bob no debe ser capaz de determinar la clave original A de Alice (o una cantidad suficiente de ella para permitirle descifrar las cartas que no posee) basándose en su conocimiento de los valores no cifrados de las cartas que ha sacado. Esto descarta algunos esquemas de cifrado conmutativo obvios, como simplemente aplicar la operación XOR a cada carta con la clave. (Usar una clave separada para cada carta incluso en el intercambio inicial, lo que de otro modo haría que este esquema fuera seguro , no funciona ya que las cartas se barajan antes de ser devueltas).
Dependiendo de la baraja acordada, este algoritmo puede ser débil. Al cifrar datos, ciertas propiedades de estos datos pueden conservarse desde el texto simple hasta el texto cifrado. Esto puede usarse para "etiquetar" ciertas cartas. 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 ocupa de operaciones de propósito general (enmascarar y desenmascarar cartas, barajar y volver a barajar, 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 residuosidad cuadrática , y el esquema general es similar en espíritu al protocolo anterior. La corrección de las operaciones se puede verificar utilizando pruebas de conocimiento cero , de modo que los jugadores no necesitan revelar su estrategia para verificar la corrección del juego.
La biblioteca C++ libtmcg [STA05] proporciona una implementación de la caja de herramientas 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 es jugado por tres jugadores con una baraja de 32 cartas, y por lo tanto requiere mucho menos esfuerzo 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 métodos de póquer mental basados en el protocolo estándar Alice-Bob (arriba) no ofrecen un rendimiento lo suficientemente alto para el juego en línea en tiempo real. El requisito de que cada jugador encripte cada carta 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 encriptación-mezclado. En lugar de barajar las cartas y luego repartirlas según sea necesario, con el nuevo método, los jugadores generan números aleatorios (encriptados) sobre la marcha, que se utilizan para seleccionar la siguiente carta. Cada nueva carta 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 la cantidad de cartas repartidas es muy pequeña en comparación con el tamaño de toda la baraja. Sin embargo, el método necesita que todos conozcan todas las cartas que ya se han repartido, lo que en la mayoría de los juegos de estilo póquer iría en contra de su propósito.
El algoritmo de generación de cartas requiere un criptosistema con dos propiedades clave. El cifrado E debe ser homomórfico aditivamente , 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 simple. En otras palabras, dados E(c 1 ) y E(c 2 ) , debe ser posible responder si c 1 = c 2 , sin que los jugadores conozcan ninguna otra información (específicamente, las identidades de c 1 y c 2 ). El esquema de cifrado de Elgamal es solo 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 se usan realmente en el juego, más una pequeña sobrecarga por las colisiones, 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 el barajado completo 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 un número aleatorio de manera veraz , la suma sigue siendo uniformemente aleatoria en {0, 51}.
Medido en términos de la cantidad de cifrados de un solo agente, el algoritmo en [GOL05] es óptimo cuando no ocurren colisiones, en el sentido de que cualquier protocolo que sea justo para todos los jugadores debe realizar al menos la misma cantidad de operaciones de cifrado. Como mínimo, cada agente debe cifrar cada carta que se use realmente. 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 lo sepa el agente que no cifra, los otros agentes pueden compartir las claves para permitirles a todos conocer los valores de todas las cartas. 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 desea 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 encripte todas las cartas que se reparten. Sin embargo, al hacer suposiciones limitadas sobre la confiabilidad de terceros, se pueden lograr protocolos significativamente más eficientes. El protocolo para elegir cartas sin barajar se puede adaptar para que el cifrado lo gestionen dos o más servidores. Suponiendo que los servidores no estén coludidos, dicho protocolo es seguro.
El protocolo básico que utiliza dos servidores es el siguiente:
En este protocolo, los servidores S1 y S2 deben coludirse para que cualquiera de ellos pueda conocer el valor de las cartas. Además, como los jugadores son los que deciden en última instancia qué cartas se reparten, los servidores no fiables no pueden influir en el juego en la medida en que es posible en el póquer online tradicional . El esquema se puede ampliar para permitir más servidores (y, por lo tanto, una mayor seguridad), simplemente incluyendo los servidores adicionales en el cifrado inicial. Por último, el primer paso del protocolo se puede realizar sin conexión, lo que permite calcular previamente y almacenar en caché una gran cantidad de "mazos" barajados y cifrados, lo que da como resultado un excelente rendimiento en el juego.
