Supuesto de dureza computacional
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) de prácticamente ningún 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 . Uno de los principales objetivos de la criptografía es crear primitivas criptográficas con seguridad demostrable . En algunos casos, se encuentra que 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 .
Decimos que la suposición es más fuerte que la suposición cuando implica (y lo contrario es falso o no conocido). En otras palabras, incluso si la suposición fuera falsa, la suposición puede seguir siendo cierta y los protocolos criptográficos basados en suposiciones pueden seguir siendo seguros 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.
Un supuesto 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 un supuesto del peor de los casos solo dice que el problema es difícil en algunos casos. Para un problema dado, la dureza de caso promedio implica dureza de caso peor, por lo que una suposición de dureza de caso promedio es más fuerte que una suposición de dureza de caso peor 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]Sin embargo, tenga en cuenta 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]
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.