¿Están los problemas de descifrado involucrados en los algoritmos de criptografía asimétrica actuales NP-Complete?

Como una adición a la respuesta de Alon Amit, incluso si tuviera un protocolo criptográfico basado en un problema NP-hard, eso no es necesariamente útil.

Si el descifrado es NP-hard para algún protocolo, eso significa que alguna instancia del mismo no se puede resolver de manera eficiente (suponiendo que P no sea igual a NP).

Esta es una propiedad bastante inútil para un protocolo criptográfico. Lo que realmente desea es que casi todas las instancias no se puedan resolver de manera eficiente, de lo contrario, muchos mensajes serían fáciles de descifrar.

Para agregar a las otras respuestas, algunos de los problemas difíciles en la criptografía son auto-reducibles aleatoriamente dentro de un módulo, curva u otro parámetro de seguridad dado. Los ejemplos incluyen la mayoría de los problemas relacionados con el registro discreto: dlog en sí mismo, DDH, CDH, supuestos de BDH, supuestos lineales y de matriz lineal, supuestos bilineales q, supuestos de brecha, etc.

Eso significa que, por ejemplo, en la curva elíptica NIST p256, si romper algunos mensajes en algunas teclas es difícil, romper cualquier mensaje cifrado correctamente en cualquier tecla elegida correctamente es difícil. (Técnicamente, esto requiere algún tipo de versión teórica de ElGamal que no altere el secreto compartido, o de lo contrario requiere oráculos aleatorios). No estoy seguro de que esto sea lo mismo que la definición de complejidad de caso promedio porque la curva es arreglado, pero está bastante cerca.

Entonces, si DDH en las curvas NIST fueron NP-completo (probablemente no lo sea), y P! = NP, y p256 fueron lo suficientemente grandes como para que todos los algoritmos para resolver problemas NP-completos se vuelvan inviables por ese tamaño en el peor de los casos, podría Tenga la seguridad de que sus mensajes cifrados serían seguros. A los criptógrafos les gusta esta propiedad porque hace que nuestras pruebas sean más fáciles y porque significa que hay una clase de “trampas” de las que no tenemos que preocuparnos ni implementar.

No se sabe lo mismo para el factoring, que históricamente convirtió la generación de claves RSA en un problema complicado. Algunos criptógrafos solían recomendar que los módulos RSA se elijan como productos de “primos seguros”. Estos son primos p con alguna propiedad especial, por ejemplo, p + 1 y p-1 pueden tener factores primos grandes para que no se apliquen ciertos algoritmos de factorización especializados. Los primos seguros ya no se recomiendan para RSA porque los algoritmos de factorización de última generación (el método de curva elíptica y el tamiz de campo de número general) no tropiezan con ninguna clase conocida de primos. Pero, en teoría, romper el RSA-2048 podría ser el peor de los casos y el caso promedio fácil.

Solucionador de tiempo polinomial NP-Complete Solucionador de cubierta exacto