¿Existen algoritmos de criptografía de clave pública que son probablemente NP-difíciles de vencer? [cerrado]

Question

Si la computación cuántica práctica se hiciera realidad, me pregunto si hay algún algoritmo criptográfico de clave pública que se base en problemas de NP completo, en lugar de factorización entera o logaritmos discretos.

Editar:

Consulte la "Computación cuántica en la teoría de la complejidad computacional" Sección de el artículo wiki sobre computadoras cuánticas. señala que la clase de problemas que las computadoras cuánticas pueden responder (BQP ) se cree que es estrictamente más fácil que NP-complete.

Editar 2:

'Basado en NP-complete' es una mala forma de expresar lo que me interesa.

Lo que pretendía pedir es un algoritmo de cifrado de clave pública con la propiedad de que cualquier método para romper el cifrado también se puede usar para romper el problema de NP-completo subyacente. Esto significa que romper el cifrado demuestra que P = NP.

Answer 1

Estoy respondiendo a este viejo hilo porque es una pregunta muy común e importante, y todas las respuestas aquí son inexactas.

La respuesta corta a la pregunta original es un inequívoco "NO". No hay esquemas de cifrado conocidos (y mucho menos los de clave pública) que se basan en un problema de NP completo (y, por lo tanto, todos ellos, bajo reducciones de tiempo polinómico). Algunos están "más cerca" que otros, sin embargo, déjenme explicarlo.

Hay mucho que aclarar aquí, así que comencemos con el significado de "basado en un problema de NP completo". La interpretación generalmente acordada de esto es: "se puede demostrar que es seguro en un modelo formal particular, suponiendo que no existan algoritmos de tiempo polinomial para problemas de NP completo". Para ser aún más precisos, suponemos que no existe un algoritmo que siempre resuelva un problema de NP completo. Esta es una suposición muy segura, porque eso es algo realmente difícil de hacer para un algoritmo: aparentemente es mucho más fácil encontrar un algoritmo que resuelva instancias aleatorias del problema con buena probabilidad.

Sin embargo, ningún esquema de encriptación tiene tal prueba. Si observa la literatura, con muy pocas excepciones (ver más abajo), los teoremas de seguridad se leen como sigue:

  

Teorema: Este esquema de cifrado es demostrablemente seguro, suponiendo que no   existe un algoritmo de tiempo polinómico para    resolución de instancias aleatorias de algún problema X .

Tenga en cuenta las " instancias aleatorias " parte. Para un ejemplo concreto, podríamos suponer que no existe un algoritmo de tiempo polinómico para factorizar el producto de dos primos aleatorios de n bits con alguna buena probabilidad. Esto es muy diferente (menos seguro) de suponer que no existe un algoritmo de tiempo polinómico para siempre factorizar todos productos de dos primos aleatorios de n bits.

Las "instancias aleatorias" versus '' peores casos '' El problema es lo que disparó varios respondedores arriba. Los esquemas de cifrado de tipo McEliece se basan en una versión aleatoria muy especial de los códigos lineales de decodificación, y no en la versión real del peor de los casos que es NP-complete.

Ir más allá de esto " instancias aleatorias " El tema ha requerido una investigación profunda y hermosa en informática teórica. Comenzando con el trabajo de Ajtai de Mikl, hemos encontrado algoritmos criptográficos donde la suposición de seguridad es el "peor de los casos". (más seguro) supuesto en lugar de uno aleatorio. Desafortunadamente, los supuestos del peor de los casos son para problemas que no se sabe que son NP completos, y alguna evidencia teórica sugiere que no podemos adaptarlos para usar problemas NP completos. Para los interesados, busque "criptografía basada en la red".

Answer 2

Se han propuesto algunos criptosistemas basados ??en problemas NP-hard (como el Merkle-Hellman sistema criptográfico basado en el problema de la suma de subconjuntos, y el criptosistema de mochila tipo naccache-Stern sobre el problema de la mochila), pero todos se han roto. ¿Por qué es esto? Lección 16 de las Grandes ideas en informática teórica de Scott Aaronson dice algo sobre esto, que creo que deberías tomar como definitivo. Lo que dice es lo siguiente:

Idealmente, nos gustaría construir un [Generador pseudoaleatorio criptográfico] o un criptosistema cuya seguridad se basara en un problema NP-completo. Desafortunadamente, los problemas de NP completo siempre son el peor de los casos. En criptografía, esto se traduciría en una declaración como & # 8220; existe un mensaje que es difícil de decodificar, ¡lo cual no es una buena garantía para un sistema criptográfico! Un mensaje debería ser difícil de descifrar con una probabilidad abrumadora. A pesar de décadas de esfuerzo, aún no se ha descubierto que relacione el peor de los casos con el caso promedio de problemas de NP completo. Y es por eso que, si queremos criptosistemas computacionalmente seguros, necesitamos hacer suposiciones más fuertes que P & # 8800; NP.

Answer 3

Esta fue una pregunta abierta en 1998:

Sobre la posibilidad de basar la criptografía en el supuesto de que P! = NP por Oded Goldreich, Rehovot Israel, Shafi Goldwasser

Del resumen: "Nuestra conclusión es que la pregunta permanece abierta".

- ¿Me pregunto si eso ha cambiado en la última década?

Editar:

Por lo que puedo decir, la pregunta aún está abierta, con un progreso reciente hacia una respuesta de que no existe tal algoritmo.

Adi Akavia, Oded Goldreich, Shafi Goldwasser y Dana Moshkovitz publicaron este artículo en el ACM en 2006: Al basar las funciones unidireccionales en la dureza NP " Nuestros principales hallazgos son los siguientes dos resultados negativos "

El sitio de Stanford Complexity Zoo es útil para describir lo que significan esos dos resultados negativos.

Answer 4

Si bien se han roto muchos formularios, consulte Merkle-Hellman , basado en una forma del 'problema de mochila' NP-complete.

Answer 5

La criptografía de celosía ofrece el mensaje general (sobre) generalizado de que, de hecho, uno puede diseñar sistemas criptográficos en los que romper el caso promedio es tan difícil como resolver un problema NP-duro particular (generalmente el problema de vector más corto o el problema de vector más cercano).

Puedo recomendar leer la sección de introducción de http://eprint.iacr.org/2008/521 y luego persiguiendo referencias a los sistemas criptográficos.

Además, vea las notas de la conferencia en http: //www.cs.ucsd. edu / ~ daniele / CSE207C / , y busca enlaces para un libro si quieres.

Answer 6

Google para NP-complete y cifrado de clave pública encuentra falsos positivos ... que en realidad son inseguros. Este cartoonish pdf parece mostrar un algoritmo de encriptación de clave pública basado en el problema de conjunto de dominación mínima . Leyendo más, luego admite mentir que el algoritmo es seguro ... el problema subyacente es NP-Complete pero su uso en el algoritmo PK no preserva la dificultad.

Otro hallazgo falso positivo de Google: Criptoanálisis del criptosistema Goldreich-Goldwasser-Halevi de Crypto ' 97 . Del resumen:

En Crypto '97, Goldreich, Goldwasser y Halevi propusieron un criptosistema de clave pública basado en el problema de vector más cercano en una red, que se sabe que es NP-hard. Mostramos que hay una falla importante en el diseño del esquema que tiene dos implicaciones: cualquier texto cifrado pierde información sobre el texto sin formato, y el problema de descifrar textos cifrados puede reducirse a un problema de vector más cercano que es mucho más fácil que el problema general. .

Answer 7

Hay un sitio web que puede ser relevante para sus intereses: Criptografía post-cuántica .

Answer 8

Aquí está mi razonamiento. Corrígeme si me equivoco.

(i) `` Romper '' un sistema criptográfico es necesariamente un problema en NP y co-NP. (Romper un sistema criptográfico implica invertir la función de cifrado, que es uno a uno y computable en tiempo polinómico. Por lo tanto, dado el texto cifrado, el texto plano es un certificado que se puede verificar en tiempo polinómico. el texto cifrado está en NP y en co-NP.)

(ii) Si hay un problema NP-duro en NP y co-NP, entonces NP = co-NP. (Este problema sería NP-completo y en co-NP. Dado que cualquier lenguaje NP es reducible a este lenguaje co-NP, NP es un subconjunto de co-NP. Ahora use simetría: cualquier lenguaje L en co-NP tiene -L (su complemento) en NP, donde -L está en co-NP --- es decir L = --L está en NP.)

(iii) Creo que generalmente se cree que NP! = co-NP, ya que de lo contrario hay pruebas de tamaño polinómico de que las fórmulas booleanas no son satisfactorias.

Conclusión: las conjeturas teóricas de la complejidad implican que los criptosistemas NP-duros no existen.

(De lo contrario, tiene un problema NP-duro en NP y co-NP, de donde NP = co-NP --- que se cree que es falso).

Answer 9

Si bien RSA y otros algoritmos criptográficos ampliamente utilizados se basan en la dificultad de la factorización de enteros (que no se sabe que NP-complete), también hay algunos algoritmos de criptografía de clave pública basados ??en problemas de NP-complete. Una búsqueda en Google de "clave pública" y "np-complete" revelará algunos de ellos.

(Dije incorrectamente antes que las computadoras cuánticas acelerarían los problemas de NP completo, pero esto no es cierto. Estoy corregido).

Answer 10

Como señalan muchos otros pósters, es posible basar la criptografía en problemas NP-hard o NP-complete.

Sin embargo, los métodos comunes para la criptografía se basarán en matemáticas difíciles (es decir, difíciles de descifrar). La verdad es que es más fácil serializar números como una clave tradicional que crear una cadena estandarizada que resuelva un problema NP-hard. Por lo tanto, la criptografía práctica se basa en problemas matemáticos que aún no se ha demostrado que sean NP-hard o NP-complete (por lo que es concebible que algunos de estos problemas estén en P).

En el cifrado ElGamal o RSA, romperlo requiere descifrar el logaritmo discreto, así que mira esto wikipedia artículo.

  

No se conoce ningún algoritmo eficiente para calcular logaritmos discretos generales logbg. El algoritmo ingenuo es elevar b a potencias cada vez mayores k hasta que se encuentre la g deseada; Esto a veces se llama multiplicación de prueba. Este algoritmo requiere un tiempo de ejecución lineal en el tamaño del grupo G y, por lo tanto, exponencial en el número de dígitos en el tamaño del grupo. Sin embargo, existe un algoritmo cuántico eficiente debido a Peter Shor ( http://arxiv.org/abs/ quant-ph / 9508027 ).

     

Calcular logaritmos discretos es aparentemente difícil. No solo no se conoce un algoritmo eficiente para el peor de los casos, sino que se puede demostrar que la complejidad del caso promedio es al menos tan difícil como el peor de los casos utilizando la auto-reducción al azar.

     

Al mismo tiempo, el problema inverso de la exponenciación discreta no lo es (se puede calcular de manera eficiente utilizando la exponenciación por cuadratura, por ejemplo). Esta asimetría es análoga a la existente entre la factorización entera y la multiplicación entera. Ambas asimetrías han sido explotadas en la construcción de sistemas criptográficos.

La creencia generalizada es que estos son NP completos, pero tal vez no se pueda probar que sí. ¡Tenga en cuenta que las computadoras cuánticas pueden romper cripto eficientemente!

Answer 11

Como nadie realmente respondió la pregunta, tengo que darte una pista: "McEliece". Haz algunas búsquedas en él. Es un algoritmo de cifrado NP-Hard comprobado. Necesita tiempo de cifrado y descifrado O (n ^ 2). También tiene una clave pública de tamaño O (n ^ 2), lo cual es malo. Pero hay mejoras que reducen todos estos límites.