cryptography - simetrico - criptografia simetrica ejemplos
¿Hay algoritmos de criptografía de clave pública que sean probables NP difíciles de vencer? (11)
Si la informática cuántica práctica se hiciera realidad, me pregunto si hay algoritmos criptográficos de clave pública que se basen en problemas NP-completos, en lugar de factorización entera o logaritmos discretos.
Editar:
Consulte la sección "Computación cuántica en la teoría de la complejidad computacional" del artículo de la 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 pretendo preguntar 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 utilizar para romper el problema NP-completo subyacente. Esto significa que romper el cifrado demuestra P = NP.
Esta fue una pregunta abierta en 1998:
Sobre la posibilidad de basar la Criptografía en la suposición 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 el 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 la ACM en 2006: Sobre cómo basar las funciones unidireccionales en la dureza NP "Nuestros principales hallazgos son los siguientes dos resultados negativos"
El sitio de Stanford, Complejidad Zoo es útil en la redacción de lo que significan los dos resultados negativos.
Google para cifrado NP-completo y Clave pública encuentra falsos positivos ... que en realidad son inseguros. Este pdf caricaturesco parece mostrar un algoritmo de encriptación de clave pública basado en el problema del conjunto dominante mínimo . 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 falso de Google: Cryptanalysis del sistema criptográfico 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 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 .
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 sean NP completos), también existen algunos 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.
(Dije incorrectamente antes que las computadoras cuánticas acelerarían los problemas NP-completos, pero esto no es verdad. Me corrijo).
Si bien muchas formas se han roto, echa un vistazo a Merkle-Hellman , basado en una forma del NP-complete ''Knapsack Problem''.
Se han propuesto algunos criptosistemas basados en problemas de NP-hard (como el criptosistema Merkle-Hellman basado en el problema de suma de subconjuntos y el criptosistema de mochila Naccache-Stern basado en el problema de la mochila), pero se han roto todos. ¿Por qué es esto? La lección 16 de Great Ideas in Theoretical Computer Science de Scott Aaronson dice algo sobre esto, que creo que debería considerar 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-complete. 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 un mensaje que es difícil de descodificar", ¡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.
Como señalan 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 (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 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 de ElGamal o RSA, para romperlo es necesario descifrar el logaritmo discreto, así que mira este artículo de 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 ).
La computación de 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 lo es (puede calcularse de manera eficiente utilizando la exponenciación mediante 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 puedan ser probados. Tenga en cuenta que las computadoras cuánticas pueden romper crypto de manera eficiente.
La criptografía de celosía ofrece el mensaje final (demasiado) generalizado de que efectivamente se pueden diseñar criptosistemas donde romper el caso promedio es tan difícil como resolver un problema particular de NP-NP (típicamente 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.
Estoy respondiendo a este hilo antiguo 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 "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 resuelva siempre un problema NP-completo. Esta es una suposición muy segura, porque eso es algo realmente difícil 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 esa prueba. Si nos fijamos en la literatura, con muy pocas excepciones (ver a continuación), los teoremas de seguridad se leen como los siguientes:
Teorema: este esquema de cifrado es probablemente seguro, suponiendo que no existe un algoritmo de tiempo polinomial para resolver 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 factorizar siempre 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.
Ir más allá de este problema de "instancias aleatorias" ha requerido una investigación profunda y hermosa en la informática teórica. Comenzando con el trabajo de Miklós Ajtai, hemos encontrado algoritmos criptográficos donde la suposición de seguridad es un supuesto "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".
Existe un sitio web que puede ser relevante para sus intereses: criptografía post-cuántica .
Aquí está mi razonamiento. Corrígeme si estoy equivocado.
(i) `` Rompiendo '''' 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-hard 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) Creo que generalmente se cree que NP! = co-NP, ya que de lo contrario hay pruebas de tamaño polinomial de que las fórmulas booleanas no son satisfactorias.
Conclusión: las conjeturas teóricas de la complejidad implican que los criptosistemas NP-hard no existen.
(De lo contrario, tiene un problema NP-hard en NP y co-NP, de ahí NP = co-NP --- que se cree que es falso).
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.