PPAD y Quantum

20

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 ...PAGPAGUNArePAGLSPAGLSPAGPAGUNAre

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 . nortePAGLSPAGPAGUNAreLPAG

ingrese la descripción de la imagen aquí ¡Feliz cumpleaños, Christos!

Gil Kalai
fuente
1
Te he ayudado a preguntarle al profesor Umesh V. Vazirani sobre esta pregunta en Papafest. Él siente que esta es una pregunta interesante, pero no tiene respuesta ahora.
Rupei Xu
1
Con respecto a la Orientación de sumidero único (USO), recientemente se demostró que se reduce a un problema llamado Línea de final de potencial único, que es (polinomialmente equivalente) a Línea de final de medición (EOML). Ambos problemas se encuentran en una clase que es, en términos generales, una contraparte "uniforme" de PLS. Los resultados de CHKPRR también muestran cómo construir instancias difíciles de EOML y, por lo tanto, CLS. Sin embargo, dado que no se sabe si EOML se reduce a USO, aún podría darse el caso de que USO sea fácil para las computadoras cuánticas. CLSPAGLSPAGPAGUNAre
Occams_Trimmer
Estimado @Occams_Trimmer, ¿hay alguna razón para pensar que USO es difícil para las computadoras clásicas? Por ejemplo, ¿está completo para algunas de las clases que mencionaste?
Gil Kalai
1
No, no se sabe que esté completo para ninguna clase (que yo sepa). Como USO es bastante bajo en la jerarquía, es plausible que también sea fácil en el caso clásico.
Occams_Trimmer

Respuestas:

11

Dos respuestas que aprendí al escribir una publicación de blog sobre esta pregunta

  1. 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.

  2. 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 .

Aviad Rubinstein
fuente
1
Muchas gracias, Aviad! ¡Y bienvenido al sitio!
Gil Kalai
Bienvenido Aviad! Tu respuesta es excelente! Acabo de mover lo mío a la parte de comentarios (para evitar compartir los puntajes de votación de usted :)).
Rupei Xu
Todavía no entiendo 1. Ciertamente hay supuestos de dureza criptográfica que no se aplican en el caso cuántico. ¿Qué es lo que hace que "romper Fiat-Shamir" sea difícil para QC a diferencia de, digamos "romper RSA"?
Gil Kalai
8

PAGPAGUNAre

En un nivel alto, CHKPRR crea una distribución sobre instancias de fin de línea donde encontrar una solución requiere:

  • romper la solidez del sistema de prueba obtenido al aplicar la heurística Fiat-Shamir al famoso protocolo sumcheck, o
  • PAG

SUNATPAGPAGUNAre

z{0 0,1}norteF(z)=XFnorteF, que funcionaría perfectamente bien en esta configuración: el protocolo sumcheck . Convertir una prueba interactiva en una no interactiva (mantener la capacidad de verificación pública y la compacidad) es exactamente lo que hace la heurística de Fiat-Shamir.

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:

Todavía no entiendo 1. Ciertamente hay supuestos de dureza criptográfica que no se aplican en el caso cuántico. ¿Qué es lo que hace que "romper Fiat-Shamir" sea difícil para QC a diferencia de, digamos "romper RSA"?

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.

PAGPAGUNArede la función hash subyacente. En un nivel intuitivo, esto no es en lo que las computadoras cuánticas son buenas, porque este es un problema que no parece necesariamente tener una estructura fuerte que pueda explotar (a diferencia, por ejemplo, logaritmo discreto y RSA): las funciones hash pueden ser típicamente muy "desestructurado"

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.

RKX(X,HK(X))RRR

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.

PAGPAGUNAre

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:

  • El cifrado completamente homomórfico (FHE) es una primitiva que sabemos cómo construir bajo una variedad de supuestos de red. Si el esquema solo debe evaluar circuitos de tamaño acotado, de hecho sabemos cómo construirlo bajo el aprendizaje estándar con suposición de error.
  • La seguridad circular establece que el FHE debería ser difícil de romper incluso cuando se usa para cifrar su propia clave secreta. Esto es más fuerte que la noción de seguridad habitual, que no permite mensajes dependientes de claves. Es un problema abierto importante y de larga data construir un FHE circularmente seguro bajo un supuesto de red estándar, como LWE. Aún así, una década después de la primera construcción de FHE de Gentry y muchos intentos de criptoanálisis, la seguridad circular de los candidatos de FHE establecidos se ha convertido en una suposición relativamente segura (incluso contra computadoras cuánticas), y no conocemos ningún ataque que explote la clave encriptaciones dependientes de una manera no trivial.
  • 2ω(Iniciar sesiónλ)-λλ2CλC<12-CλC<1
  • Finalmente, queremos que todo lo anterior se mantenga si permitimos un tiempo de ejecución superpolinomial para el atacante. Esto sigue en línea con lo que pueden lograr los algoritmos conocidos.

PAGPAGUNAre

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.

Geoffroy Couteau
fuente
1
Estimado Geoffroy, muchas gracias por tu gran respuesta.
Gil Kalai