En criptografía , Merkle's Puzzles es una construcción temprana de un criptosistema de clave pública , un protocolo ideado por Ralph Merkle en 1974 y publicado en 1978. Permite que dos partes acuerden un secreto compartido intercambiando mensajes, incluso si no tienen secretos en común de antemano.
Supongamos que Alice y Bob desean comunicarse. Bob puede enviar un mensaje a Alice de la siguiente manera: primero crea una gran cantidad de acertijos, cada uno de ellos de una cantidad moderada de dificultad (debe ser posible para Alice resolver el acertijo con una cantidad moderada de esfuerzo computacional). Los acertijos tienen la forma de un mensaje encriptado con una clave desconocida ; la clave debe ser lo suficientemente corta como para permitir un ataque de fuerza bruta . Bob envía todos los acertijos (es decir, mensajes encriptados) a Alice, quien elige uno al azar y lo resuelve. La solución desencriptada contiene un identificador así como una clave de sesión, de modo que Alice puede comunicarle a Bob qué acertijo ha resuelto. Ambas partes ahora tienen una clave común; Alice, porque resolvió un acertijo, y Bob, porque envió el acertijo. Cualquier espía (Eva, por ejemplo) tiene una tarea más difícil: no sabe qué acertijo fue resuelto por Alice. Su mejor estrategia es resolver todos los acertijos, pero como hay tantos, esto es más costoso computacionalmente para Eve que para Alice.
Tenga en cuenta que la espía Eve puede leer el identificador X enviado (en texto claro) desde Alice a Bob, pero no tiene forma de asignarlo a la clave secreta Y que Bob y Alice ahora están usando para su comunicación en curso, porque el valor de X dentro de cada mensaje se generó aleatoriamente.
Los parámetros del juego de rompecabezas se pueden elegir para que sea considerablemente más difícil para un espía descifrar el código que para las partes comunicarse, pero los rompecabezas de Merkle no proporcionan las enormes diferencias cualitativas en dificultad que se requieren para (y definen) la seguridad en la criptografía moderna.
Supongamos que la cantidad de acertijos enviados por Bob es m y que Bob y Alice necesitan n pasos de cálculo para resolver un acertijo. Entonces, ambos pueden deducir una clave de sesión común dentro de una complejidad de tiempo de O ( m + n ). Eve, por el contrario, debe resolver todos los acertijos, lo que le lleva O ( mn ) de tiempo. Si m ≈ n , el esfuerzo de Eve tiene una complejidad aproximadamente cuadrática en comparación con Alice y Bob, es decir, su tiempo de cálculo es del orden del cuadrado del de ellos. Por lo tanto, n debe seleccionarse lo suficientemente grande como para que el cálculo aún sea factible para Alice y Bob mientras supere las capacidades de Eve.
La complejidad cuadrática no suele considerarse lo suficientemente segura contra un atacante (o, en el otro extremo, para valores m,n grandes, lo suficientemente conveniente para los participantes) para aplicaciones criptográficas prácticas en el mundo real. Sin embargo, este esquema tiene la distinción de ser uno de los primeros ejemplos de criptografía de clave pública y fue una inspiración para el protocolo de intercambio de claves Diffie-Hellman , que tiene una complejidad mucho mayor y se basa en el problema del logaritmo discreto .
En 2008, Boaz Barak y Mohammad Mahmoody-Ghidary demostraron ("Los rompecabezas de Merkle son óptimos") que este límite cuadrático no se puede mejorar.