¿Estado de los mundos de Impagliazzo?

33

En 1995, Russell Impagliazzo propuso cinco mundos de complejidad:

1- Algoritmica: con todas las asombrosas consecuencias.PAGS=nortePAGS

2- Heuristica: los completos de son difíciles en el peor de los casos ( ) pero se pueden resolver de manera eficiente en el caso promedio.nortePAGSPAGS≠nortePAGS

3- Pessiland: existen problemas de completos en el caso promedio, pero no existen funciones unidireccionales. Esto implica que no podemos generar instancias difíciles del completo con una solución conocida. nortePAGSnortePAGS

4- Minicrypt: existen funciones unidireccionales pero los sistemas criptográficos de clave pública son imposibles

5- Criptomanía: existen sistemas criptográficos de clave pública y es posible una comunicación segura.

¿Qué mundo se ve favorecido por los recientes avances en complejidad computacional? ¿Cuál es la mejor evidencia para la elección?

Russell Impagliazzo, una visión personal de la complejidad del caso promedio , 1995

Los cinco mundos de Impagliazzo, el blog La complejidad computacional

cc.complexity-theory conditional-results average-case-complexity Mohammad Al-Turkistany
fuente
2
No soy lo suficientemente experto para responder, pero pensé que le gustaría saber que en el primer Taller de Barreras en Complejidad, Impagliazzo solicitó un programa de investigación muy en línea con su pregunta. Llame oráculos "oráculos parecidos a la Tierra" en los que se mantienen los mismos teoremas de complejidad que se mantienen en el mundo "real" no relativizado en el que vivimos. Luego estudie las propiedades de estos oráculos que son un poco como la Tierra real. Entonces, en ese marco, su pregunta se convierte en "¿Qué debe satisfacer un oráculo para ser como la Tierra?"
Aaron Sterling el

Respuestas:

26

Hace aproximadamente un año coorganicé un taller sobre complejidad y criptografía: el estado de los mundos de Impagliazzo , y las diapositivas y videos en el sitio web pueden ser de interés.

La respuesta corta es que no ha cambiado mucho en el sentido de que la mayoría de los investigadores todavía creen que vivimos en la "Criptomanía" y todavía tenemos más o menos la misma evidencia de esto, y no hay mucho progreso en colapsar ninguno de los mundos.

Quizás la pieza más importante de información nueva es el algoritmo de Shor que muestra que al menos si reemplaza P con BQP, los criptosistemas de clave pública más comúnmente utilizados son inseguros. Pero, debido a los criptosistemas basados ​​en Lattice, la suposición predeterminada es que vivimos en la criptomanía incluso en este caso, aunque quizás el consenso aquí es un poco más débil que el caso clásico. Incluso en el caso clásico, parece haber mucha más evidencia de la existencia de funciones unidireccionales ("Minicrypt") que la existencia de cifrado de clave pública ("Cryptomania"). Aún así, dado el esfuerzo que la gente ha dedicado a tratar de romper varios criptosistemas de clave pública, también hay evidencia significativa de esto último.

Boaz Barak
fuente
Este enlace puede funcionar mejor: archive.dimacs.rutgers.edu/Workshops/Cryptography/program.html
Timothy Chow
18

Buena pregunta, pero los científicos ni siquiera han podido separar "Algorithmica" de los casos restantes, y mucho menos decidir el mundo exacto en el que vivimos.

Dicho esto, hay varios trabajos de investigación sobre el tema. Ver por ejemplo: Sobre la posibilidad de basar la Criptografía en el supuesto de que P! = NP por Goldreich y Goldwasser, y sus referencias.

Ver también Basar funciones unidireccionales en dureza NP por Adi Akavia et al.

Además, es bien sabido que la decodificación de algunos sistemas criptográficos es NP-hard (ver, por ejemplo, el sistema criptográfico McEliece , o la criptografía basada en Lattice ). No sé por qué esto NO resuelve el problema, ya que no estoy familiarizado con tales criptosistemas. Vea los comentarios de Peter Shor a continuación.

También le sugiero que eche un vistazo rápido a la discusión en Stackoverflow . Revisar la literatura que cita el trabajo de Impagliazzo también puede ser instructivo.

EDITAR: Los siguientes resultados pueden ser de interés:

Feigenbaum y Fortnow. Random-Self-Reducibility de conjuntos completos. SIAM Journal on Computing, 22: 994–1005, 1993.

Bogdanov y Trevisan. Sobre las reducciones de peor caso a promedio para problemas de NP. En Actas del 44º Simposio anual de IEEE sobre fundamentos de la informática, páginas 308–317, 2003.

Akavia, Goldreich, Goldwasser y Moshkovitz. Sobre la base de funciones unidireccionales en dureza NP

Gutfreund y Ta-Shma. Nuevas conexiones entre desrandomización, complejidad del peor de los casos y complejidad del caso promedio. Tech. Rep. TR06-108, Coloquio electrónico sobre la complejidad computacional, 2006.

Bogdanov y Trevisan. Complejidad de caso promedio. Encontró. Tendencias Theor. Comput Sci. 2, 1 (octubre de 2006), 1-106. DOI = http://dx.doi.org/10.1561/0400000004

MS Dousti
fuente
55
El criptosistema McEliece no es un criptosistema; es toda una familia de criptosistemas, según la clase de códigos de corrección de errores que use en él. Si utiliza códigos arbitrarios de corrección de errores, entonces es NP-hard romper, pero también NP-hard es decodificar un mensaje. Si usa una clase de códigos de corrección de errores que tiene un algoritmo de decodificación de tiempo polinómico, entonces es tiempo de polinomia decodificar el mensaje, pero ya no tenemos una prueba de que romper el sistema criptográfico es NP difícil. La situación con la criptografía basada en celosía es mejor, pero aún no es NP-hard de descifrar.
Peter Shor
@ Peter: ¡Muchas gracias! ¡Resolviste un rompecabezas que me intrigó durante mucho tiempo!
MS Dousti
De hecho, parece que para algunas familias de códigos de corrección de errores, el criptosistema McEliece se ha roto, aunque no para los códigos Goppa, que estaban en la propuesta original de McEliece.
Peter Shor