¿Por qué no ha habido un algoritmo de cifrado que se basa en los conocidos problemas NP-duros?

Question

La mayoría de encriptación de hoy, tales como el RSA, se basa en la factorización de enteros, que no se cree que es un problema NP-duro, pero pertenece a BQP, lo que la hace vulnerable a los ordenadores cuánticos. Me pregunto, ¿por qué no ha sido un algoritmo de cifrado que se basa en un conocido problema NP-duro. Suena (al menos en teoría) como lo haría un mejor algoritmo de cifrado que uno que no está demostrado que es NP-duro.

Answer 1

peor de los casos la dureza de los problemas NP-completos no es suficiente para la criptografía. Incluso si los problemas NP-completos son difíciles en el peor de los casos ($ P \ ne NP $), que aún podrían ser eficientemente resolubles en el promedio de los casos. Criptografía supone la existencia de caso promedio problemas insolubles en NP. Además, lo que demuestra la existencia de problemas de erección de la media en NP utilizando el P $ \ ne NP $ supuesto es un importante problema abierto.

Una excelente lectura es el clásico por Russell Impagliazzo, Una visión personal de la Media-complejidad asistencial , 1995 .

Un excelente estudio es media-complejidad asistencial por Bogdanov y Trevisan, Fundamentos y Tendencias en Ciencias de la Computación Teórica vol. 2, No 1 (2006) 1-106

Answer 2

Se han producido.

Un ejemplo de ello es McEliece criptosistema que se basa en la dureza de la decodificación de 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-duro .

Otra es Merkle-Hellman mochila criptosistema que ha sido roto.

Nota: no tengo ni idea de si las dos primeras están rotos / lo buenos que son. Todo lo que sé es que existen, y tengo los de hacer una búsqueda en Internet.

Answer 3

No puedo pensar en cuatro grandes obstáculos que no son totalmente independientes:

• NP-hard sólo le da información acerca de la complejidad en el límite . Durante muchos problemas NP-completos, existen algoritmos que resuelven todos los casos de interés (en un determinado escenario) razonablemente rápido. En otras palabras, para cualquier fijo tamaño del problema (por ejemplo, un determinado "clave"), el problema no es necesariamente difícil sólo porque es NP-duro.
• NP-hard sólo tiene en cuenta el tiempo del peor caso. Muchos, incluso la mayoría de todos los casos puede ser fácil de resolver con algoritmos existentes. Incluso si supiéramos cómo caracterizar los casos difíciles (que yo sepa, no), tendríamos todavía tenemos que encontrarlos.
• Es necesario tener enorme casos que son difíciles de resolver. La búsqueda de (productos) de grandes números primos es fácil en el sentido de que el espacio de búsqueda es plana: un número es adecuado o no tampoco. Imaginar el uso de gráficos: de los $ 2 ^ {n (n-1)} $ gráficos de tamaño n $ $ $ para grandes n $, usted tiene que encontrar los que tienen propiedades agradables
.
• Usted necesita algún tipo de reversibilidad. Por ejemplo, cualquier número entero se describe de manera única por su primer factorización. Imagen que se desea utilizar TSP como método de cifrado; dado todos los recorridos más cortos, se puede (re) construir la gráfica que vinieron de forma única?

Tenga en cuenta que no tengo ninguna experiencia en la criptografía; estos son meramente resp algorítmica. complejidad de la teoría de las objeciones.

Answer 4

criptografía de clave pública tal como la conocemos hoy en día se basa en unidireccional trampilla permutaciones , y la trampilla es esencial

Para un protocolo de estar seguros públicamente, se necesita una forma clave a disposición de cualquier persona, y una para cifrar un mensaje usando esta clave. Obviamente, una vez cifrado, debe ser duro para recuperar el mensaje original conociendo sólo su sistema de cifrado y la clave pública:. La cifra sólo debe ser descifrable con alguna información adicional, a saber, su clave privada

Con esto en mente, es fácil construir un primitiva sistema de cifrado basado en cualquier permutación trampa de un sentido.

1. Alice da la permutación de un solo sentido para el público, y mantener la trampilla para sí misma.
2. Bob puso su entrada en la permutación, y transmitir la salida a Alice.
3. Alice utiliza la trampilla para invertir la permutación con la salida de Bob.

La dificultad ahora es encontrar permutaciones reales trampa de un sentido, y hay un montón de funciones que creemos que son buenos candidatos (RSA, logaritmo discreto, algunas variaciones sobre el problema de celosía). Sin embargo, si podemos encontrar con certeza una función unidireccional, entonces nosotros también demostramos que $ \ mathsf {P} \ ne \ mathsf {NP} $, por lo que en realidad demuestra que una función es de un solo sentido es intratable.

Al revés, si se prueba que $ \ mathsf {P} \ ne \ mathsf {NP} $, también demostraremos que hay una clase en el medio llamada $ \ mathsf {NPI} $ (intermedio), de los problemas en $ \ mathsf {NP} $ pero no $ \ mathsf {NP} $ - duro. Algunos candidatos buenos para los problemas en $ \ mathsf {NPI} $ son también los candidatos para un solo sentido permutaciones, ya que aún no hemos sido capaces de demostrar que son $ \ mathsf {NP} $ -. Dura

Así que para responder a su pregunta, no usamos $ \ mathsf {NP} $ - problemas difíciles porque necesitamos permutación unidireccional con trampillas, y estas funciones especiales probablemente vivo en una clase entre $ \ mathsf {NP} $ y $ \ mathsf {NP} $ -. dura

Answer 5

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

Casi todos los casos, de casi todos los problemas NP-completos, son fáciles de resolver. Hay problemas que esto no es cierto, pero son difíciles de encontrar, y es difícil estar seguro de que tienes sonar un tal clase.

Esto se ha planteado en la práctica varias veces cuando la gente trata de escribir generadores de problemas aleatorios para algunos famosos clase NP-completo, como Programación con restricciones, SAT o vendedor ambulante. En algunos posteriores alguien encuentra la fecha un método para resolver casi todos los casos que el generador aleatorio produce trivial. Por supuesto, si ese fuera el caso de un sistema de encriptación estaríamos en serios problemas!

Answer 6

criptosistemas

Merkle-Hellman se basan en problemas de la mochila binarios (suma de subconjuntos).