Hoy en Nueva York y en todo el mundo se celebra el cumpleaños de Christos Papadimitriou. Esta es una buena oportunidad para preguntar sobre las relaciones entre la clase de complejidad PPAD de Christos (y sus otras clases relacionadas) y las computadoras cuánticas. En su célebre artículo de 1994, Papadimitriou introdujo y estudió sistemáticamente varias clases importantes de complejidad como PLS, PPAD y otras. (El documento de Papadimitriou se basó en algunos documentos anteriores y, en particular, como señaló Aviad, Johnson-Papadimitriou-Yannakakis introdujo el PLS en 1988).
Mi pregunta principal es:
¿Las computadoras cuánticas dan alguna ventaja para los problemas en ? o en ? o en ? etc ...
Otra pregunta es si hay algunos análogos cuánticos de PLS y PPAD y otras clases de Christos.
Observo que en estos documentos se encontraron conexiones notables recientes de PPAD con la criptografía: ¿ Sobre la dureza criptográfica de encontrar un equilibrio de Nash por N Bitansky, O Paneth, A Rosen y la dureza PPAD puede basarse en suposiciones criptográficas estándar? por A Rosen, G Segev, I Shahaf, y encontrar un equilibrio de Nash no es más fácil que romper Fiat-Shamir por Arka Rai Choudhuri, Pavel Hubacek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, Guy Rothblum. También noto que, en mi opinión, las clases de Christos son especialmente cercanas a las matemáticas y las pruebas matemáticas.
Actualización: Ron Rothblum comentó (sobre FB) que los resultados de Choudhuri, Hubacek, Kamath, Pietrzak, Rosen y G. Rothblum implican que PPAD está plausiblemente más allá del poder de las computadoras cuánticas. (Estaré encantado de ver una respuesta elaborada que lo explique).
Un comentario más: una buena pregunta relacionada es si encontrar el sumidero en una orientación única única del cubo tiene un algoritmo cuántico eficiente. (Creo que esta tarea es más fácil que pero no estoy seguro de cómo se relaciona con ). Esto está relacionado con la búsqueda para encontrar una ventaja cuántica para consulte https://cstheory.stackexchange.com/a/767/712 .
Respuestas:
Dos respuestas que aprendí al escribir una publicación de blog sobre esta pregunta
No : en las variantes de caja negra, la complejidad de la comunicación / consulta cuántica ofrece la aceleración cuadrática de Grover, pero no más que eso. Como señala Ron, esto se extiende a la complejidad computacional bajo supuestos plausibles.
Tal vez : el equilibrio de Nash es posiblemente el problema principal de las "clases Christos". Aquí, dar a los jugadores acceso al entrelazamiento cuántico sugiere un nuevo concepto de solución de "equilibrio cuántico correlacionado" que generaliza el equilibrio de Nash. Su complejidad aún está abierta. Vea este interesante artículo de Alan Deckelbaum.
Y una nota histórica: PLS fue presentado por Johnson-Papadimitriou-Yannakakis en 1988 .
fuente
En un nivel alto, CHKPRR crea una distribución sobre instancias de fin de línea donde encontrar una solución requiere:
Instanciando Fiat-Shamir
La heurística de Fiat-Shamir es muy simple: arregle alguna función hash, comience con una prueba interactiva de monedas públicas y reemplace cada mensaje aleatorio del verificador por un hash de la transcripción completa hasta el momento. La pregunta es entonces bajo qué propiedad de la función hash podemos probar que el protocolo resultante sigue siendo sólido (tenga en cuenta que ya no puede ser estadísticamente sólido; la esperanza es que siga siendo computacionalmente sólido).
Antes de profundizar en esto, déjame abordar tu comentario:
La descripción de alto nivel que di debería dejar en claro, espero, que "romper Fiat-Shamir" y "romper RSA" no son problemas realmente comparables. RSA es una suposición concreta y específica de dureza, y si puede factorizar enteros grandes, puede romperlo.
En términos más concretos, hay dos alternativas naturales al elegir una función hash para instanciar Fiat-Shamir:
El enfoque heurístico, concretamente eficiente:
elija su función hash favorita, por ejemplo, SHA-3. Por supuesto, no tenemos pruebas de que crear instancias de Fiat-Shamir con SHA-3 nos dé un problema difícil; pero tampoco sabemos de ningún ataque no trivial a la solidez de los sistemas de prueba obtenidos al aplicar Fiat-Shamir con SHA-3 a un sistema de prueba interactivo no degenerado. Esto también se extiende a la configuración cuántica: no conocemos ningún ataque cuántico que funcione mejor que la aceleración cuadrática habitual dada por el algoritmo de Grover. Después de décadas de intentos de criptoanálisis, el consenso en la comunidad criptográfica es que el algoritmo cuántico no parece , por lo que podemos ver, proporcionar aceleraciones superpolinomiales para primitivas de "estilo Minicrypt" (funciones hash, PRG, cifrados de bloque, etc.) sin alguna estructura algebraica subyacente fuerte, como SHA-2, SHA-3, AES, etc.
El enfoque de seguridad demostrable:
aquí el objetivo es aislar una propiedad limpia de la función hash que hace que el sonido heurístico de Fiat-Shamir, y construir una función hash que satisfaga estas propiedades bajo supuestos criptográficos plausibles.
La pregunta ahora es cómo construir funciones hash de correlación intratable para las relaciones que nos interesan, y en este contexto específico, para la relación asociada al protocolo sumcheck. Aquí, una línea de trabajo reciente (esencialmente 1 , 2 , 3 , 4 , 5 , 6 ) ha demostrado que, para muchas relaciones de interés, uno realmente puede construir funciones de hash intratables de correlación bajo supuestos basados en la red.
No estamos exactamente allí, de hecho. El reciente resultado de Peikert y Shiehian (el último artículo en la lista que di anteriormente) mostró que para las relaciones importantes, podemos construir una función hash de correlación intratable bajo problemas reticulares bien establecidos, como aprender con errores o el problema SIS ; sin embargo, la relación sumcheck no es capturada por este trabajo.
Aún así, CHKPRR, basándose en este trabajo demostró que se puede construir una función hash de correlación intratable bajo el supuesto de que cualquiera de las muchas construcciones concretas de esquemas de cifrado totalmente homomórficos tiene una seguridad circular casi óptima contra ataques de tiempo superpolinomial.
Analicemos esta suposición:
Por supuesto, una de las principales preguntas abiertas dejadas por CHKPRR es construir una función hash de correlación intratable para la relación sumcheck bajo una mejor suposición basada en la red, idealmente, la suposición LWE. Esto parece no trivial, pero no inverosímil, dado que esta es una línea de trabajo muy reciente, donde ya se han logrado muchos resultados sorprendentes para otras relaciones interesantes.
fuente