En criptografía , Merkle's Puzzles es una de las primeras construcciones de un criptosistema de clave pública , un protocolo ideado por Ralph Merkle en 1974 y publicado en 1978. Permite a dos partes acordar un secreto compartido mediante el intercambio de 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 con una dificultad moderada; Alice debe poder resolver el acertijo con una cantidad moderada de esfuerzo informático. Los acertijos tienen la forma de un mensaje cifrado con una clave desconocida ; la clave debe ser lo suficientemente corta para permitir un ataque de fuerza bruta . Bob envía todos los acertijos (es decir, mensajes cifrados) a Alice, quien elige uno al azar y lo resuelve. La solución descifrada contiene un identificador y una clave de sesión, para que Alice pueda comunicarle a Bob qué rompecabezas ha resuelto. Ambas partes tienen ahora una clave común; Alice, porque resolvió un acertijo, y Bob, porque él envió el acertijo. Cualquier espía (Eve, por ejemplo) tiene una tarea más difícil: no sabe qué rompecabezas resolvió Alice. Su mejor estrategia es resolver todos los acertijos, pero como hay tantos, esto es más costoso desde el punto de vista computacional para Eve que para Alice.
Tenga en cuenta que Eve, la espía, puede leer el identificador X enviado (en texto claro) de Alice a Bob, pero no tiene forma de asignarlo a la clave secreta Y que Bob y Alice están usando ahora para su comunicación continua, 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 el número de acertijos enviados por Bob es m , y que tanto Bob como 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 temporal 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 normalmente no se considera lo suficientemente segura contra un atacante (o en el otro extremo, para m,n grandes, lo suficientemente conveniente para los participantes) para aplicaciones criptográficas prácticas del 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 ("Merkle Puzzles Are Optimal") que este límite cuadrático no se puede mejorar.