El acertijo fue formulado en 1958 por John McCarthy y es el siguiente:

Dos países se encuentran en guerra. Un País está enviando espías al otro. Dichos espías hacen su trabajo y regresan. Al regresar corren el peligro de ser agredidos por los guardias de su propio país al cruzar la frontera. Se requiere de un mecanismo de contraseña. Se asume que los espías son gente de confianza pero que los guardias que vigilan la frontera no, pues comúnmente van a embriagarse a bares locales, por lo que se debe asumir que el enemigo llegará a saber cualquier cosa que ellos sepan.

¿Puedes idear un protocolo de seguridad con el que el espía sea capaz de regresar a salvo pero que, al mismo tiempo, impida al enemigo ser capaz de introducir sus propios espías usando la información conocida por los guardias?

A continuación discuto una solución a este problema, por lo que si quieren quebrarse la cabeza y resolver el problema por su cuenta dejen de leer ahora. Dicho esto discutamos la solución:

La solución se basa en lo que se conoce como una función de un solo sentido (one-way function). Estas funciones tienen la propiedad de que, dado un valor de entrada, es fácil calcular su resultado, pero dado el resultado es muy difícil calcular su entrada. Una función que, por ejemplo, NO cumple esta propiedad es func(x) { return x*3; } ya que para obtener el valor de entrada, a partir de su resultado, basta con dividirlo entre 3.

Considera esta función:

func2(x) {
    y = x^2; // elevamos x al cuadrado
    y = digitosEnMedio(y); // obtenemos 100 dígitos a la mitad de y
    return y;
}

Suponiendo que x es un número de 100 dígitos, ¿Cómo obtendrías x a partir del resultado? Hacerlo es realmente muy difícil y de hecho, para obtener x dado y esencialmente tenemos que probar todos los x posibles. Si se fijan, el problema de “dado y encontrar x” tiene la propiedad de ser muy fácil de verificar (si conocemos x podemos obtener fácilmente y) pero muy difícil de resolver. Este tipo de problemas, cuya solución (en este caso x) es muy difícil de encontrar pero muy fácil de verificar, son bien conocidos y, de hecho, son famosos: Pertenecen a la clase de problemas conocida como NP. Hasta el momento no se ha podido demostrar que, efectivamente, estos problemas no pueden resolverse fácilmente y de esto se trata la pregunta ¿P = NP?. Al que pueda demostrar esto le esperan un millón de dólares.

Regresando al acertijo, ¿cómo usamos func2 para resolverlo? Al guardia le damos y el cuál es un número de 100 dígitos, y al espía le damos x, que también es de 100 dígitos. Creamos también una pequeña máquina que calcule func2. Al llegar el espía, este ingresa x en la máquina sin que el guardia lo vea. El guardia simplemente verifica que el resultado coincida con el número y que tiene y listo: El guardia no conoce la contraseña ni es capaz de encontrarla, pero si es capaz de verificarla.

Esto es también la base de la criptografía de llave pública y privada, y, por esta razón, algunos de ustedes habrán leído que si se llega a demostrar que P = NP, nuestros mecanismos de criptografía actuales se volverían automáticamente obsoletos.