¿Por qué no ha habido un algoritmo de cifrado basado en los problemas conocidos de NP-Hard?

109

La mayor parte del cifrado actual, como el RSA, se basa en la factorización de enteros, que no se cree que sea un problema NP-hard, pero pertenece a BQP, lo que lo hace vulnerable a las computadoras cuánticas. Me pregunto, ¿por qué no ha habido un algoritmo de cifrado basado en un problema NP-hard conocido? Parece (al menos en teoría) que sería un mejor algoritmo de encriptación que uno que no es NP-hard.

Ken Li
fuente

Respuestas:

76

La peor dureza de los problemas NP-completos no es suficiente para la criptografía. Incluso si los problemas de NP completo son difíciles en el peor de los casos ( ), aún podrían resolverse eficientemente en el caso promedio. La criptografía supone la existencia de problemas intratables de caso promedio en NP. Además, demostrar la existencia de problemas difíciles de promediar en NP utilizando el supuesto es un problema abierto importante.P N PPNPPNP

Una lectura excelente es el clásico de Russell Impagliazzo, A Personal View of Average-Case Complexity , 1995.

Una excelente encuesta es la complejidad de casos promedio de Bogdanov y Trevisan, Fundamentos y tendencias en informática teórica vol. 2, no 1 (2006) 1–106

Mohammad Al-Turkistany
fuente
1
¿No necesitamos dureza en el mejor de los casos también? Después de todo, todas nuestras claves deben ser seguras. ¿O podemos evitar de manera efectiva (y eficiente) el mejor de los casos?
Raphael
77
Además, deberíamos ser capaces de generar instancias difíciles en un tiempo razonable. En resumen, necesitamos mucho más que solo ness. NP-hard
Kaveh
@Raphael, debería ser suficiente si la probabilidad de obtener un caso "bueno" indeseable es lo suficientemente pequeña. Si es más pequeño que la probabilidad de adivinar la clave correcta de un caso "malo" deseable, este riesgo debería considerarse aceptable en mi humilde opinión.
quazgar
49

Ha habido.

Un ejemplo de ello es el criptosistema McEliece, que se basa en la dureza de decodificar un código lineal.

Un segundo ejemplo es NTRUEncrypt, que se basa en el problema de vector más corto que creo que se sabe que es NP-Hard.

Otro es el criptosistema de mochila Merkle-Hellman que se ha roto.

Nota: No tengo idea si los dos primeros están rotos / qué tan buenos son. Todo lo que sé es que existen, y los obtuve haciendo una búsqueda en la web.

Aryabhata
fuente
66
A los efectos del criptoanálisis, McEliece probablemente no debería considerarse un solo criosistema; para cada clase de códigos lineales decodificables de manera eficiente que conecte, necesariamente tiene que idear una estrategia diferente para romperlo. Se ha roto para algunas clases de códigos, pero (como dice el artículo de Wikipedia) no para los códigos Goppa, que fueron la sugerencia original de McEliece.
Peter Shor
De esa lista, diría que NTRU parece la más prometedora, aún no se ha probado exhaustivamente la forma en que se evaluó RSA en función de lo que he leído hasta ahora.
Ken Li
El criptosistema Merkle-Hellman no es un ejemplo apropiado. Los verificadores de mochila Merkle-Hellman son solo un subconjunto de todos los vectores de mochila, por lo que el problema de la mochila Merkle-Hellman puede no ser NP difícil. No creo que sea NP-hard, al menos no conozco ningún documento que muestre esto.
milagro173
25

Puedo pensar en cuatro obstáculos principales que no son completamente independientes:

  • La dureza NP solo le brinda información sobre la complejidad en el límite . Para muchos problemas de NP completo, existen algoritmos que resuelven todas las instancias de interés (en un determinado escenario) razonablemente rápido. En otras palabras, para cualquier tamaño de problema fijo (por ejemplo, una "clave" dada), el problema no es necesariamente difícil solo porque es NP-difícil.
  • La dureza NP solo considera el peor de los casos. Muchas, incluso la mayoría de todas las instancias, pueden ser fáciles de resolver con los algoritmos existentes. Incluso si supiéramos cómo caracterizar las instancias difíciles (afaik, no lo hacemos), todavía tendríamos que encontrarlas.
  • 2n(n1)nn
  • Necesitas algún tipo de reversibilidad. Por ejemplo, cualquier número entero se describe de manera única por su factorización prima. Imagen que desearíamos usar TSP como método de cifrado; dados todos los recorridos más cortos, ¿puedes (re) construir el gráfico del que provienen de manera única?

Tenga en cuenta que no tengo experiencia en criptografía; estos son meramente algorítmicos resp. objeciones teóricas de complejidad.

Rafael
fuente
Excelente resumen Pero tenga en cuenta que la dureza BQP tiene las mismas advertencias que sus dos primeros puntos.
Mitch
14

La criptografía de clave pública tal como la conocemos hoy se basa en permutaciones de trampillas unidireccionales , y la trampilla es esencial.

Para que un protocolo sea público seguro, necesita una clave disponible para todos y una forma de cifrar un mensaje con esta clave. Obviamente, una vez encriptado, debería ser difícil recuperar el mensaje original conociendo solo su cifrado y la clave pública: el cifrado solo debe ser descifrable con alguna información adicional, es decir, su clave privada.

Con eso en mente, es fácil construir un sistema criptográfico primitivo basado en cualquier permutación de trampilla unidireccional.

  1. Alice le da la permutación unidireccional al público, y mantiene la trampa para ella sola.
  2. Bob puso su entrada en la permutación y transmitió la salida a Alice.
  3. Alice usa la trampilla para invertir la permutación con la salida de Bob.

PNP , por lo que probar que una función es unidireccional es intratable.

PNPNPINPNPNPINP

NPNPNP

Heinz Fiedler
fuente
RSA, sí, es una función de trampilla. No estoy seguro de que dlog sea TDF (es unidireccional)
111
Si un problema NP-intermedio fuera NP-duro, sería NP-completo, una contradicción.
Myria
0

Solo para dar un argumento heurístico, basado en la experiencia práctica.

Casi todas las instancias, de casi todos los problemas de NP completo, son fáciles de resolver. Hay problemas en los que esto no es cierto, pero son difíciles de encontrar, y es difícil estar seguro de que tienes esa clase de sonido.

Esto ha surgido en la práctica varias veces cuando las personas intentan escribir generadores de problemas aleatorios para alguna clase famosa de NP completo, como Programación de restricciones, SAT o Vendedor ambulante. En una fecha posterior, alguien encuentra un método para resolver casi todas las instancias que el generador aleatorio produce trivialmente. Por supuesto, si ese fuera el caso de un sistema de cifrado, ¡estaríamos en serios problemas!

Chris Jefferson
fuente