En la teoría de la complejidad computacional , un supuesto de dureza computacional es la hipótesis de que un problema particular no se puede resolver de manera eficiente (donde eficientemente significa típicamente "en tiempo polinomial "). No se sabe cómo probar la dureza (incondicional) para prácticamente cualquier problema útil. En cambio, los informáticos confían en las reducciones para relacionar formalmente la dureza de un problema nuevo o complicado con una suposición de dureza computacional sobre un problema que se comprende mejor.
Los supuestos de dureza computacional son de particular importancia en criptografía . Un objetivo importante en criptografía es crear primitivas criptográficas con seguridad demostrable . En algunos casos, los protocolos criptográficos tienen una seguridad teórica de la información ; la libreta de un solo uso es un ejemplo común. Sin embargo, la seguridad de la teoría de la información no siempre se puede lograr; en tales casos, los criptógrafos recurren a la seguridad computacional. En términos generales, esto significa que estos sistemas son seguros asumiendo que cualquier adversario es computacionalmente limitado , como todos los adversarios lo son en la práctica.
Los supuestos de dureza computacional también son útiles para guiar a los diseñadores de algoritmos: es poco probable que un algoritmo simple refute un supuesto de dureza computacional bien estudiado como P ≠ NP .
Comparación de supuestos de dureza
Los informáticos tienen diferentes formas de evaluar qué supuestos de dureza son más fiables.
Supuestos de fuerza de dureza
Decimos esa suposición es más fuerte que la suposición Cuándo implica (y lo contrario es falso o desconocido). En otras palabras, incluso si la suposición eran falsos, suposición aún puede ser cierto, y los protocolos criptográficos se basan en suposiciones aún puede ser seguro de usar. Por lo tanto, al diseñar protocolos criptográficos, se espera poder demostrar la seguridad utilizando los supuestos más débiles posibles.
Supuestos del caso promedio frente al del peor de los casos
Una suposición de caso promedio dice que un problema específico es difícil en la mayoría de los casos a partir de alguna distribución explícita, mientras que una suposición del peor de los casos solo dice que el problema es difícil en algunas instancias. Para un problema dado, la dureza del caso promedio implica la dureza del caso más desfavorable, por lo que una suposición de dureza de caso promedio es más fuerte que una suposición de dureza del caso más desfavorable para el mismo problema. Además, incluso para problemas incomparables, una suposición como la Hipótesis del tiempo exponencial a menudo se considera preferible a una suposición de caso promedio como la conjetura de la camarilla plantada . [1] Tenga en cuenta, sin embargo, que en la mayoría de las aplicaciones criptográficas, saber que un problema tiene una instancia difícil (es decir, un problema es difícil en el peor de los casos) es inútil porque no nos proporciona una forma de generar instancias duras. [2] Afortunadamente, muchos supuestos de casos promedio usados en criptografía (incluyendo RSA , registro discreto y algunos problemas de celosía ) pueden basarse en supuestos del peor de los casos a través de reducciones del peor caso al caso promedio. [3]
Falsificabilidad
Una característica deseada de un supuesto de dureza computacional es la falsabilidad , es decir, que si el supuesto fuera falso, sería posible probarlo. En particular, Naor (2003) introdujo una noción formal de falsabilidad criptográfica. [4] Aproximadamente, se dice que una suposición de dureza computacional es falsable si se puede formular en términos de un desafío: un protocolo interactivo entre un adversario y un verificador eficiente, donde un adversario eficiente puede convencer al verificador de aceptar si y solo si la suposición es falsa.
Supuestos comunes de dureza criptográfica
Se utilizan muchos supuestos de dureza criptográfica. Esta es una lista de algunos de los más comunes y algunos protocolos criptográficos que los utilizan.
Factorización de enteros
Dado un número compuesto , y en particular uno que es el producto de dos grandes números primos , el problema de factorización de enteros es encontrar y (más generalmente, encuentre números primos tal que ). Es un gran problema abierto encontrar un algoritmo para la factorización de enteros que se ejecute en un polinomio de tiempo en el tamaño de la representación (). La seguridad de muchos protocolos criptográficos se basa en el supuesto de que la factorización de enteros es difícil (es decir, no se puede resolver en tiempo polinomial). Los criptosistemas cuya seguridad es equivalente a esta suposición incluyen el criptosistema Rabin y el criptosistema Okamoto-Uchiyama . Muchos más criptosistemas se basan en supuestos más sólidos, como RSA , problemas de residuo y ocultamiento de Phi .
Problema de RSA
Dado un número compuesto , exponente y numero , el problema de RSA es encontrar . Se conjetura que el problema es difícil, pero se vuelve fácil dada la factorización de. En el criptosistema RSA ,es la clave pública , es el cifrado del mensaje , y la factorización de es la clave secreta utilizada para el descifrado.
Problemas de residuo
Dado un número compuesto y enteros , el problema de la residuosidad es determinar si existe (alternativamente, encontrar una) tal que
Casos especiales importantes incluyen el problema de residuosidad cuadrática y el problema de residuosidad compuesta decisional . Como en el caso de RSA, se conjetura que este problema (y sus casos especiales) es difícil, pero se vuelve fácil dada la factorización de. Algunos criptosistemas que dependen de la dureza de los problemas de residuos incluyen:
- Criptosistema Goldwasser-Micali (problema de redisduosidad cuadrática)
- Generador Blum Blum Shub (problema de redisduosidad cuadrática)
- Criptosistema Paillier (problema decisional de residuosidad compuesta)
- Criptosistema Benaloh (mayor problema de residuosidad)
- Criptosistema Naccache-Stern (mayor problema de residuosidad)
Suposición de ocultación de phi
Para un número compuesto , no se sabe cómo calcular eficientemente su función totient de Euler . La suposición de Phi-ocultación postula que es difícil de calculary, además, incluso calcular los factores primos de es difícil. Esta suposición se utiliza en el protocolo PIR de Cachin – Micali – Stadler . [5]
Problema de registro discreto (DLP)
Elementos dados y de un grupo , el problema del registro discreto solicita un número entero tal que . No se sabe que el problema del registro discreto sea comparable a la factorización de enteros, pero sus complejidades computacionales están estrechamente relacionadas .
La mayoría de los protocolos criptográficos relacionados con el problema del registro discreto en realidad se basan en la suposición más fuerte de Diffie-Hellman : elementos de grupo dados, dónde es un generador y son números enteros aleatorios, es difícil de encontrar . Ejemplos de protocolos que utilizan esta suposición incluyen el intercambio de claves Diffie-Hellman original , así como el cifrado ElGamal (que se basa en la variante Decisional Diffie-Hellman (DDH) aún más fuerte ).
Mapas multilineales
Un mapa multilineal es una función (dónde son grupos ) de modo que para cualquier y ,
- .
Para aplicaciones criptográficas, uno quisiera construir grupos y un mapa tal que el mapa y las operaciones del grupo en se puede calcular de manera eficiente, pero el problema de registro discreto en sigue siendo difícil. [6] Algunas aplicaciones requieren supuestos más sólidos, por ejemplo, análogos multilineales de los supuestos de Diffie-Hellman.
Para el caso especial de , se han construido mapas bilineales con seguridad creíble utilizando el emparejamiento de Weil y el emparejamiento de Tate . [7] ParaSe han propuesto muchas construcciones en los últimos años, pero muchas de ellas también se han roto, y actualmente no hay consenso sobre un candidato seguro. [8]
Algunos criptosistemas que se basan en supuestos de dureza multilineal incluyen:
- Esquema Boneh-Franklin (blineal Diffie-Hellman)
- Boneh-Lynn-Shacham (blineal Diffie-Hellman)
- Garg-Gentry-Halevi-Raykova-Sahai-Waters candidato para la ofuscación de indistinguibilidad y el cifrado funcional (rompecabezas multilineales) [9]
Problemas de celosía
El problema computacional más fundamental en las celosías es el problema del vector más corto (SVP) : dada una celosía, encuentra el vector distinto de cero más corto . La mayoría de los criptosistemas requieren suposiciones más sólidas sobre las variantes de SVP, como el problema de los vectores independientes más cortos (SIVP) , GapSVP , [10] o Unique-SVP. [11]
La suposición de dureza de celosía más útil en criptografía es para el problema de aprendizaje con errores (LWE):, dónde para alguna función lineal , es fácil de aprender usando álgebra lineal. En el problema LWE, la entrada al algoritmo tiene errores, es decir, para cada parcon alguna pequeña probabilidad. Se cree que los errores hacen que el problema sea intratable (para los parámetros apropiados); en particular, se conocen reducciones entre el peor de los casos y el promedio de las variantes de SVP. [12]
Para las computadoras cuánticas, los problemas de factorización y registro discreto son fáciles, pero se conjetura que los problemas de celosía son difíciles. [13] Esto hace que algunos criptosistemas basados en celosías sean candidatos para la criptografía post-cuántica .
Algunos criptosistemas que dependen de la dureza de los problemas de celosía incluyen:
- NTRU (tanto NTRUEncrypt como NTRUSign )
- La mayoría de los candidatos para el cifrado totalmente homomórfico
Supuestos de dureza no criptográficos
Además de sus aplicaciones criptográficas, los supuestos de dureza se utilizan en la teoría de la complejidad computacional para proporcionar evidencia de enunciados matemáticos que son difíciles de probar incondicionalmente. En estas aplicaciones, se prueba que el supuesto de dureza implica algún enunciado teórico de la complejidad deseado, en lugar de probar que el enunciado es verdadero en sí mismo. El supuesto más conocido de este tipo es el supuesto de que P ≠ NP , [14] pero otros incluyen la hipótesis del tiempo exponencial , [15] la conjetura de la camarilla plantada y la conjetura de los juegos únicos . [dieciséis]
-problemas difíciles
Se sabe que muchos problemas computacionales del peor de los casos son difíciles o incluso completos para alguna clase de complejidad , en particular NP-hard (pero a menudo también PSPACE-hard , PPAD-hard , etc.). Esto significa que son al menos tan difíciles como cualquier problema de la clase.. Si un problema es-duro (con respecto a las reducciones de tiempo polinomial), entonces no puede resolverse mediante un algoritmo de tiempo polinomial a menos que el supuesto de dureza computacional Es falso.
Hipótesis del tiempo exponencial (ETH) y variantes
La hipótesis del tiempo exponencial (ETH) es un fortalecimiento desuposición de dureza, que conjetura que el problema de satisfacibilidad booleano no solo no tiene un algoritmo de tiempo polinomial, sino que además requiere tiempo exponencial (). [17] Una suposición aún más fuerte, conocida como la Hipótesis del Tiempo Exponencial Fuerte (SETH) conjetura que k {\ Displaystyle k} -SAT requiere tiempo, donde . ETH, SETH y los supuestos de dureza computacional relacionados permiten deducir resultados de complejidad de grano fino, por ejemplo, resultados que distinguen el tiempo polinomial y el tiempo cuasi polinomial , [1] o incluso versus . [18] Estos supuestos también son útiles en la complejidad parametrizada . [19]
Supuestos de dureza de caja promedio
Se supone que algunos problemas de cálculo son difíciles en promedio sobre una distribución particular de instancias. Por ejemplo, en el problema de la camarilla plantada , la entrada es un gráfico aleatorio muestreado, muestreando un gráfico aleatorio Erdős-Rényi y luego "plantando" un gráfico aleatorio-clique, es decir, conectando nodos uniformemente aleatorios (donde ), y el objetivo es encontrar el plantado -clique (que es un whp único). [20] Otro ejemplo importante es la hipótesis de Feige , que es una suposición de dureza computacional sobre instancias aleatorias de 3-SAT (muestreadas para mantener una proporción específica de cláusulas y variables). [21] Los supuestos de dureza computacional de casos promedio son útiles para probar la dureza de casos promedio en aplicaciones como estadísticas, donde hay una distribución natural sobre las entradas. [22] Además, el supuesto de dureza de la camarilla plantada también se ha utilizado para distinguir entre la complejidad temporal del peor caso polinomial y cuasi-polinomial de otros problemas, [23] de manera similar a la hipótesis del tiempo exponencial .
Juegos únicos
El problema de la cubierta de etiqueta única es un problema de satisfacción de restricciones, donde cada restricción involucra dos variables , y para cada valor de hay un valor único de que satisface . Determinar si se pueden satisfacer todas las restricciones es fácil, pero la Conjetura del juego único (UGC) postula que determinar si casi todas las restricciones (-fracción, para cualquier constante ) puede estar satisfecho o casi ninguno de ellos (-fracción) puede satisfacerse es NP-duro. [16] A menudo se sabe que los problemas de aproximación son NP-hard asumiendo UGC; estos problemas se conocen como UG-hard. En particular, asumiendo UGC, existe un algoritmo de programación semidefinido que logra garantías de aproximación óptimas para muchos problemas importantes. [24]
Expansión de juego pequeño
Estrechamente relacionado con el problema de la cubierta de etiqueta única está el problema de expansión de conjuntos pequeños (SSE) : dado un gráfico, encuentra un pequeño conjunto de vértices (de tamaño ) cuya expansión de borde es mínima. Se sabe que si SSE es difícil de aproximar, también lo es Unique Label Cover. Por lo tanto, la hipótesis de expansión del conjunto pequeño , que postula que la SSE es difícil de aproximar, es una suposición más fuerte (pero estrechamente relacionada) que la conjetura del juego único. [25] Se sabe que algunos problemas de aproximación son SSE-hard [26] (es decir, al menos tan difíciles como aproximar SSE).
La conjetura de 3SUM
Dado un conjunto de números, el problema 3SUM pregunta si hay un triplete de números cuya suma es cero. Existe un algoritmo de tiempo cuadrático para 3SUM, y se ha conjeturado que ningún algoritmo puede resolver 3SUM en "tiempo verdaderamente subcuadrático": la conjetura de 3SUM es la suposición de dureza computacional de que no hay-algoritmos de tiempo para 3SUM (para cualquier constante ). Esta conjetura es útil para demostrar límites inferiores casi cuadráticos para varios problemas, principalmente de geometría computacional . [27]
Ver también
- Nivel de seguridad
Referencias
- ^ a b Braverman, Mark ; Ko, Young Kun; Weinstein, Omri (2015). "Aproximación del mejor equilibrio de Nash en-el tiempo rompe la hipótesis del tiempo exponencial ". Simposio sobre algoritmos discretos (SODA) . Sociedad de Matemáticas Industriales y Aplicadas . págs. 970–982. doi : 10.1137 / 1.9781611973730.66 . ISBN 978-1-61197-374-7.
- ^ J. Katz e Y. Lindell, Introducción a la criptografía moderna (serie de seguridad de red y criptografía de Chapman y Hall / Crc), Chapman y Hall / CRC, 2007.
- ^ Goldwasser, Shafi ; Kalai, Yael Tauman (2016). "Supuestos criptográficos: un documento de posición". Conferencia de Teoría de la Criptografía (TCC) 2016 . Saltador. págs. 505–522. doi : 10.1007 / 978-3-662-49096-9_21 .
- ^ Naor, Moni (2003). "Sobre supuestos y desafíos criptográficos". En Boneh, Dan (ed.). Advances in Cryptology - CRYPTO 2003: 23rd Annual International Cryptology Conference, Santa Barbara, California, EE. UU., 17-21 de agosto de 2003, Actas . Apuntes de conferencias en Ciencias de la Computación. 2729 . Berlín: Springer. págs. 96-109. doi : 10.1007 / 978-3-540-45146-4_6 . Señor 2093188 .
- ^ Cachin, Christian; Micali, Silvio; Stadler, Markus (1999). Stern, Jacques (ed.). "Recuperación de información privada computacionalmente con comunicación polilogarítmica". Apuntes de conferencias en informática . Saltador. 1592 : 402–414. doi : 10.1007 / 3-540-48910-X . ISBN 978-3-540-65889-4. S2CID 29690672 .
- ^ Boneh, Dan ; Silverberg, Alice (2002). "Aplicaciones de las formas multilineales a la criptografía" . Archivo ePrint de criptología .
- ^ Dutta, Ratna; Barua, Rana; Sarkar, Palash (2004). "Protocolos criptográficos basados en emparejamiento: una encuesta" . Archivo ePrint de criptología .
- ^ Albrecht, Martin R. "¿Ya se ha roto el esquema de codificación gradual?" . Consultado el 22 de marzo de 2018 .
- ^ Garg, Sanjam; Gentry, Craig; Halevi, Shai; Raykova, Mariana; Sahai, Amit; Aguas, Brent (2016). "Ofuscación de indistinguibilidad de candidatos y cifrado funcional para todos los circuitos" (PDF) . Revista SIAM de Computación . SIAM. 45 (3): 882–929. doi : 10.1137 / 14095772X .
- ^ Peikert, Chris (2009). "Criptosistemas de clave pública del problema del vector más corto del peor de los casos: resumen extendido". Actas del 41º Simposio Anual de ACM sobre Teoría de la Computación (STOC) . págs. 333–342. doi : 10.1145 / 1536414.1536461 .
- ^ Ajtai, Miklós ; Dwork, Cynthia (1997). "Un criptosistema de clave pública con equivalencia en el peor caso / caso medio". Actas del 29º Simposio Anual de ACM sobre Teoría de la Computación (STOC) . págs. 284-293. doi : 10.1145 / 258533.258604 .
- ^ Regev, Oded (2010). "El problema del aprendizaje con errores (encuesta invitada)". Conferencia sobre Complejidad Computacional (CCC) 2010 . págs. 191-204. doi : 10.1109 / CCC.2010.26 .
- ^ Peikert, Chris (2016). "Una década de criptografía de celosía" . Fundamentos y Tendencias en Informática Teórica . 10 (4): 283–424. doi : 10.1561 / 0400000074 .
- ^ Fortnow, Lance (2009). "El estado del problema P versus NP" (PDF) . Comunicaciones de la ACM . 52 (9): 78–86. doi : 10.1145 / 1562164.1562186 . S2CID 5969255 . Archivado desde el original (PDF) el 24 de febrero de 2011..
- ^ Woeginger, Gerhard (2003). "Algoritmos exactos para problemas NP-difíciles: una encuesta". Optimización combinatoria: ¡Eureka, te encoges! . 2570 . Springer-Verlag. págs. 185–207. doi : 10.1007 / 3-540-36478-1_17 ..
- ^ a b Khot, Subhash (2010). "Sobre la conjetura de los juegos únicos". Proc. 25th IEEE Conference on Computational Complexity (PDF) . págs. 99-121. doi : 10.1109 / CCC.2010.19 ..
- ^ Impagliazzo, Russell ; Paturi, Ramamohan (1999). "La complejidad de k-SAT". Proc. 14ª Conf. IEEE sobre Complejidad Computacional . págs. 237-240. doi : 10.1109 / CCC.1999.766282 .
- ^ Abboud, Amir; Vassilevska-Williams, Virginia ; Weimann, Oren (2014). "Consecuencias de una alineación más rápida de secuencias". Autómatas, lenguajes y programación - 41 ° Coloquio Internacional, ICALP 2014 . págs. 39–51. doi : 10.1007 / 978-3-662-43948-7_4 .
- ^ Lokshtanov, Daniel; Marx, Daniel; Saurabh, Saket (2011). "Límites inferiores basados en la hipótesis del tiempo exponencial" . Boletín de la EATCS . 105 : 41–72.
- ^ Arora, Sanjeev ; Barak, Boaz (2009). Complejidad computacional: un enfoque moderno . Prensa de la Universidad de Cambridge. págs. 362–363. ISBN 9780521424264..
- ^ Feige, Uriel (2002). "Relaciones entre la complejidad media del caso y la complejidad de la aproximación". Actas del 34º Simposio Anual de ACM sobre Teoría de la Computación (STOC) . págs. 534–543. doi : 10.1145 / 509907.509985 .
- ^ Berthet, Quentin; Rigollet, Philippe (2013). "Límites inferiores teóricos de la complejidad para la detección de componentes principales dispersos". COLT 2013 . págs. 1046–1066.
- ^ Hazan, Elad; Krauthgamer, Robert (2011). "¿Qué tan difícil es aproximar el mejor equilibrio de Nash?". Revista SIAM de Computación . 40 (1): 79–91. CiteSeerX 10.1.1.139.7326 . doi : 10.1137 / 090766991 .
- ^ Raghavendra, Prasad (2008). "¿Algoritmos óptimos y resultados inapropiados para cada CSP?". 40 ° Simposio anual de ACM sobre teoría de la computación (STOC) 2008 . págs. 245-254. doi : 10.1145 / 1374376.1374414 .
- ^ Raghavendra, Prasad; Steurer, David (2010). "Graph Expansion and the Unique Games Conjeture". 42o Simposio Anual de ACM sobre teoría de la Computación (STOC) 2010 . págs. 755–764. doi : 10.1145 / 1806689.1806792 .
- ^ Wu, Yu; Austrin, Per; Pitassi, Toniann; Liu, David (2014). "Inaproximación de Treewidth y problemas relacionados" . Revista de Investigación en Inteligencia Artificial . 49 : 569–600. doi : 10.1613 / jair.4030 .
- ^ Vassilevska Williams, Virginia (2018). "Sobre algunas cuestiones detalladas en algoritmos y complejidad". ICM 2018 (PDF) .