Supuestos de Dificultad Computacional

Los supuestos de dificultad computacional son conjeturas no probadas pero bien estudiadas —como la dificultad de la factorización, los logaritmos discretos y los problemas de retículos— en las que, en última instancia, se basa la seguridad de los esquemas criptográficos.

Definition

Un supuesto de dificultad computacional es una conjetura de que un problema computacional particular no puede ser resuelto eficientemente (en tiempo polinómico) por ningún adversario realista, sirviendo como la base sobre la cual se construye la seguridad demostrable.

Scope

Este tema cubre los supuestos en los que se basa la criptografía: la existencia de funciones unidireccionales, problemas de teoría de números (factorización, RSA, logaritmo discreto) y los problemas de retículos y códigos utilizados en la criptografía postcuántica. Aborda la jerarquía entre los supuestos, la distinción entre la dificultad en el peor caso y en el caso promedio, y cómo se verifican los supuestos. Excluye la maquinaria de reducción que conecta los supuestos con los esquemas y las propias definiciones de seguridad, tratados en temas relacionados.

Core questions

• ¿Por qué la seguridad criptográfica debe basarse en supuestos de dificultad no probados?
• ¿Cuáles son los principales supuestos (funciones unidireccionales, factorización, logaritmo discreto, retículos)?
• ¿Cómo se relacionan los supuestos entre sí en términos de fortaleza?
• ¿Cuál es la diferencia entre la dificultad en el peor caso y en el caso promedio?
• ¿Cómo se verifican los problemas difíciles candidatos y qué sucede cuando uno falla?

Key concepts

• función unidireccional
• función de trampa
• supuesto de factorización de enteros
• supuesto de logaritmo discreto
• supuestos de RSA y Diffie-Hellman
• aprendizaje con errores (LWE)
• dificultad en el peor caso vs. en el caso promedio
• P versus NP
• jerarquía de supuestos

Key theories

Funciones unidireccionales como supuesto mínimo

La existencia de funciones unidireccionales —fáciles de calcular, difíciles de invertir— es necesaria y suficiente para gran parte de la criptografía simétrica y es el supuesto más básico; casi toda la criptografía presupone al menos esto.

Supuestos de teoría de números y de retículos

La criptografía de clave pública se basa en problemas estructurados —factorización de enteros, el problema RSA y logaritmos discretos (clásicamente), y problemas de aprendizaje con errores y de vector más corto en retículos (postcuánticos)— cada uno respaldado por décadas de escrutinio criptoanalítico.

Mechanisms

La criptografía necesita problemas que sean difíciles en promedio (sobre instancias aleatorias), no meramente en el peor caso, ya que las claves se eligen aleatoriamente. Los supuestos se organizan en una jerarquía aproximada: una ruptura de un supuesto más débil (por ejemplo, la factorización) a menudo rompe los esquemas construidos sobre él, mientras que las reducciones relacionan los supuestos entre sí. Los supuestos de retículos son notables por las reducciones del peor caso al caso promedio, lo que da una mayor confianza. La confianza en cualquier supuesto proviene de un esfuerzo criptoanalítico sostenido y fallido, más que de una prueba.

Clinical relevance

Los supuestos de dificultad determinan qué es seguro y qué no lo es para implementar. El descubrimiento de que las computadoras cuánticas romperían la factorización y los logaritmos discretos (mediante el algoritmo de Shor) invalidó los supuestos detrás de RSA y la criptografía de curva elíptica frente a adversarios cuánticos, impulsando directamente el paso a los estándares postcuánticos basados en retículos. Elegir esquemas construidos sobre supuestos bien estudiados y seguir su estado es esencial para la seguridad a largo plazo.

Evidence & guidelines

Los organismos de estandarización favorecen los supuestos con largos historiales criptoanalíticos; el proceso postcuántico del NIST evaluó explícitamente la madurez y la confianza de los supuestos subyacentes de retículos, códigos y hash. La mejor práctica evita supuestos exóticos o recién propuestos para sistemas de alta seguridad y prefiere problemas conservadores y bien verificados, con tamaños de clave establecidos frente a los mejores ataques conocidos.

History

La dependencia de la dificultad surgió con la criptografía de clave pública en 1976, cuando Diffie y Hellman vincularon la seguridad al logaritmo discreto, y RSA a la factorización. La década de 1980 formalizó las funciones unidireccionales y la distinción entre el peor caso y el caso promedio. Las reducciones del peor caso al caso promedio de Ajtai (1996) y el problema de aprendizaje con errores (LWE) de Regev (2005) establecieron los supuestos de retículos, que ganaron prominencia como fundamentos resistentes a la computación cuántica y sustentan los nuevos estándares postcuánticos.

Key figures

• Whitfield Diffie
• Martin Hellman
• Oded Goldreich
• Oded Regev
• Andrew Yao

Seminal works

• diffie1976
• goldreich2001
• katz2020

Frequently asked questions

¿Por qué no podemos simplemente probar que estos problemas son difíciles?

Probar que un problema requiere un tiempo superpolinómico resolvería preguntas abiertas profundas en la teoría de la complejidad (especialmente P versus NP), que siguen sin resolverse. Por lo tanto, la criptografía se basa en supuestos cuya plausibilidad proviene de décadas de intentos fallidos de resolverlos eficientemente.

¿Qué sucede si se rompe un supuesto de dificultad?

Cada esquema cuya seguridad se reduce a ese supuesto se vuelve potencialmente inseguro y debe ser reemplazado. Por eso, la amenaza cuántica a la factorización y los logaritmos discretos impulsó una migración global a esquemas basados en supuestos diferentes y resistentes a la computación cuántica.