Si P = NP, ¿hay criptosistemas que requerirían n ^ 2 tiempo para romperse?

Si P es igual a NP, ¿será posible diseñar un sistema de criptosistema donde el algoritmo de criptoanálisis óptimo tome, por ejemplo, el cuadrado del tiempo empleado por los algoritmos legítimos de cifrado y descifrado? ¿Ya existen tales algoritmos?

Sí, de hecho, ¡el primer algoritmo de clave pública que se inventó fuera de una agencia de inteligencia funcionó así! La primera publicación que propuso la criptografía de clave pública fue "Comunicaciones seguras sobre canales inseguros" de Ralph Merkle , donde propuso utilizar "rompecabezas" . Este es un protocolo de acuerdo clave.

1. Alice envía mensajes encriptados (llamados rompecabezas), cada uno con un identificador único I i y una clave de sesión K i , con las claves para cada mensaje elegido entre un conjunto de n claves. Esto toma tiempo O ( n ) ( O ( 1 ) por mensaje).$n$$I_i$$K_i$$n$$O(n)$$O(1)$
2. Bob descifra uno de los mensajes por la fuerza bruta y envía de vuelta cifra con K i . Esto toma tiempo O ( n ) ( O ( 1 ) por tecla, multiplicado por n teclas posibles).$I_i$$K_i$$O(n)$$O(1)$$n$
3. Alice intenta todas las claves para descifrar el mensaje. Esto toma nuevamente tiempo.$O(n)$

Cada parte sólo requiere la computación, pero un espía que desee encontrar K i necesidades de probar la mitad de los puzzles en promedio para calcular la tecla derecha (el espía no sabe cuál es el mensaje de Bob eligió para descifrar), por lo que el espía requiere un cálculo de Θ ( n 2 ) en promedio.$O(n)$$K_i$$\Theta(n^2)$

Después de que Merkle inventó sus acertijos, Diffie y Hellman publicaron un protocolo de acuerdo clave basado en el problema del logaritmo discreto . Este protocolo todavía se usa hoy.

El problema con los acertijos de Merkle, o cualquier cosa en la que la cantidad de trabajo que debe realizar el atacante solo aumenta a medida que el cuadrado de la parte legítima, es que se requieren enormes tamaños de clave y cantidades de cómputo para lograr un margen de seguridad decente.

En cualquier caso, no está claro que simplemente demostrar que P = NP invalidará los algoritmos criptográficos existentes. Si el aumento del polinomio es una potencia lo suficientemente alta, puede que no importe tanto en la práctica. Consulte ¿Cómo deberá cambiarse la seguridad si P = NP? , ¿Podemos decir que si P = NPP = NP no hay cifrado de clave pública segura de CPA? , P = NP y sistemas criptográficos actuales , ...

https://en.m.wikipedia.org/wiki/One-time_pad

Un One Time Pad es seguro independientemente de la complejidad, siempre que sus números sean verdaderamente aleatorios.

Incluso si puede probar cada tecla rápidamente, es inútil porque esto revelará todos los mensajes posibles, y no hay forma de saber cuál era el deseado.

Por lo que describe, si el análisis solo tomara el cuadrado del tiempo de cifrado, se consideraría inseguro según los estándares modernos. El cifrado debe realizarse en segundos o incluso menos, por lo que un aumento cuadrático permitiría decodificar los mensajes en unas pocas horas.