¿Hay algoritmos de criptografía de clave pública que sean probablemente difíciles de derrotar para NP?

Question

Si la informática 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 NP-completos, en lugar de factorización entera o logaritmos discretos.

Editar:

Por favor, echa un vistazo a la "computación cuántica en la teoría de la complejidad computacional" de the wiki article on quantum computers. Se señala que la clase de los problemas de los ordenadores cuánticos pueden responder (SCL) se cree que es más fácil de lo estrictamente NP completar.

Edición 2:

'Sobre la base de NP-completo' es una mala manera de expresar lo que me interesa en

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

Answer 1

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

La respuesta breve a la pregunta original es un "NO" inequívoco. No existen esquemas de encriptación conocidos (y mucho menos los de clave pública) que se basan en un problema NP-completo (y, por lo tanto, todos ellos, en reducciones de tiempo polinomial). Sin embargo, algunos están "más cerca" que otros, así que permítanme dar más detalles.

Hay mucho que aclarar aquí, así que comencemos con el significado de "basado en un problema NP-completo". La interpretación generalmente acordada de esto es: "se puede probar que es seguro en un modelo formal particular, suponiendo que no existen algoritmos de tiempo polinomial para problemas NP-completos". Para ser aún más precisos, suponemos que no existe ningún algoritmo que siempre resuelva un problema NP-completo. Esta es una suposición muy segura, porque eso es algo muy 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 cifrado tiene tal prueba. Si nos fijamos en la literatura, con muy pocas excepciones (véase más adelante), los teoremas de seguridad se leen como la siguiente:

Teorema: Este esquema de cifrado es demostrablemente seguro, en el supuesto de que no existe algoritmo de tiempo polinomial para resolviendo instancias aleatorias de algún problema X.

Tenga en cuenta la parte "instancias aleatorias". Para un ejemplo concreto, podemos suponer que no existe un algoritmo de tiempo polinomial 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 polinomial para siempre factorizando todos los productos de dos primos aleatorios de n bits.

El problema de las "instancias aleatorias" frente a las "instancias de los peores casos" es lo que ha provocado la falla de varios de los que respondieron anteriormente. Los esquemas de cifrado del tipo McEliece se basan en una versión aleatoria muy especial de códigos lineales de decodificación, y no en la versión del peor caso real que es NP-completa.

Impulsar más allá de este problema de "instancias aleatorias" ha requerido una profunda y hermosa investigación en informática teórica.Comenzando con el trabajo de Miklós Ajtai, hemos encontrado algoritmos criptográficos donde la suposición de seguridad es una suposición del "peor caso" (más seguro) en lugar de un caso aleatorio. Desafortunadamente, las suposiciones del peor caso son para problemas que no se sabe que son NP completos, y algunas evidencias teóricas sugieren que no podemos adaptarlos para usar problemas NP-completos. Para los interesados, busque "criptografía basada en celosía".

Answer 2

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

(He dicho de forma incorrecta antes de que los ordenadores cuánticos aceleraría problemas NP-completos, pero esto no es verdad. Estoy corregida.)

Answer 3

Mientras que muchas formas se han roto, echa un vistazo a Merkle-Hellman, basado en una forma del NP-complete 'Knapsack Problem'.

Answer 4

Google para encriptación completa y clave pública encuentra falsos positivos ... que son realmente inseguros. Parece que cartoonish pdf muestra un algoritmo de encriptación de clave pública basado en minimium dominating set problem. Leyendo más, admite admitir que el algoritmo es seguro ... el problema subyacente es NP-completo, pero su uso en el algoritmo PK no conserva la dificultad.

Otro Hallazgo positivo Google encuentra: Cryptanalysis of the Goldreich-Goldwasser-Halevi cryptosystem from 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 un enrejado, que se sabe que es NP-hard. Mostramos que hay un error importante en el diseño del esquema que tiene dos implicaciones: cualquier texto cifrado filtra información sobre el texto sin formato, y el problema de descifrar los textos cifrados puede reducirse a un problema especial del vector más cercano que es mucho más fácil que el problema general .

Answer 5

Esta fue una pregunta abierta en 1998:

On the possibility of basing Cryptography on the assumption that P != NP por Oded Goldreich, Rehovot Israel, Shafi Goldwasser

Del resumen: "Nuestra conclusión es que la cuestión sigue abierta".

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

Editar:

Por lo que yo puedo decir es la cuestión sigue abierta, con la reciente progreso hacia una respuesta de no existe tal algoritmo.

Adi Akavia, Oded Goldreich, Shafi Goldwasser, y Dana Moshkovitz publicó este papel en la ACM en 2006: On basing one-way functions on NP-hardness "Nuestros principales resultados son los siguientes dos resultados negativos"

El sitio de Stanford Complexity Zoo es útil en decripting lo esos dos resultados negativos significan. Se han propuesto

Answer 6

Algunos sistemas criptográficos basados ​​en los problemas NP-duro (tales como el sistema de cifrado basado en Merkle-Hellman el problema subconjunto de suma, y ​​el Naccache-Stern knapsack cryptosystem basado en el problema de la mochila), pero todos ellos han sido rotos. ¿Por qué es esto? La conferencia 16 de Scott Aaronson's Great Ideas in Theoretical Computer Science dice algo sobre esto, que creo que debería tomar como definitivo. Lo que dice es lo siguiente:

Idealmente, nos gustaría construir un [Cripgraphic Pseudorandom Generator] o criptosistema cuya seguridad se basara en un problema NP-completo. Desafortunadamente, los problemas NP-completos siempre son sobre el peor de los casos. En criptografía, esto se traduciría en una afirmación como "existe existe un mensaje que es difícil de descodificar", lo que no es una buena garantía para un sistema criptográfico. Un mensaje debe ser difícil de descifrar con una probabilidad abrumadora. A pesar de décadas de esfuerzo, aún no se ha descubierto ninguna manera de relacionar el peor de los casos con el promedio de casos de problemas NP-completos. Y esta es la razón por la cual, si queremos criptosistemas de seguridad computacional, necesitamos hacer suposiciones más fuertes que P ≠ NP.

Answer 7

Según lo señalado por muchos otros carteles, 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 las matemáticas difíciles (difíciles de descifrar, es decir). 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 han demostrado ser 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, para romperlo se necesita un craqueo del logaritmo discreto, así que mira este artículo wikipedia.

No se conoce ningún algoritmo eficiente para calcular logaritmos discretos generales logbg. El algoritmo ingenuo es elevar b a potencias mayores y más altas k hasta que se encuentre el g deseado; esto a veces se llama multiplicación de prueba. Este algoritmo requiere 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 mostrar que la complejidad de un caso promedio es al menos tan difícil como el peor de los casos utilizando autoreducibilidad aleatoria.

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

La creencia generalizada es que estos son NP-completos, pero tal vez no se puede probar así. Tenga en cuenta que las computadoras cuánticas pueden romper crypto de manera eficiente.

Answer 8

La criptografía de enrejado ofrece el mensaje final (demasiado) generalizado de que uno puede diseñar criptosistemas donde dividir el caso promedio es tan difícil como resolver un problema particular de NP (normalmente 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 buscar referencias a los criptosistemas.

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

Answer 9

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

Answer 10

hay un sitio web que puede ser relevante para sus intereses: Post-Quantum Cryptography.

Answer 11

Aquí está mi razonamiento. Corrígeme si estoy equivocado.

(i) `` Romper '' un criptosistema es necesariamente un problema en NP y co-NP. (Romper un criptosistema implica invertir la función de encriptación, que es uno a uno y computable en tiempo polinomial. Por lo tanto, dado el texto cifrado, el texto sin formato es un certificado que se puede verificar en tiempo polinomial. Por lo tanto, consultar el texto sin formato basado en 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 --- que es L = --L está en NP.)

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

Conclusión: conjeturas complejidad teórica implican que no existen sistemas criptográficos NP-duros.

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