Criptografía basada en retículos
- Propuesto por
- Miklós Ajtai
- Año
- 1996
- Tipo
- public-key cryptosystem based on lattice hardness
- Familia
- Post-quantum cryptography
Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés
¿Qué hace?
La criptografía basada en retículos es una clase de criptosistemas cuya seguridad se deriva de la dificultad computacional de los problemas de retículos, en particular el problema del vector más corto (SVP) y el aprendizaje con errores (LWE).
Propuestos por primera vez por Miklós Ajtai en 1996, los enfoques basados en retículos han ganado prominencia como los principales candidatos para la criptografía postcuántica. A diferencia de RSA y ECC, que son vulnerables a las computadoras cuánticas, se cree que los problemas de retículos siguen siendo difíciles incluso frente a algoritmos cuánticos.
La intuición detrás del método
Un retículo es un subgrupo discreto del espacio euclidiano formado por combinaciones lineales enteras de vectores base. La criptografía basada en retículos explota la brecha entre dos problemas: encontrar un vector corto en un retículo es computacionalmente difícil, pero con información adicional (una base secreta), el vector corto se puede encontrar rápidamente. La criptografía de clave pública se construye publicando una base difícil y manteniendo en secreto una base fácil. Añadir un pequeño ruido aleatorio (el paradigma de aprendizaje con errores) fortalece aún más la seguridad al hacer que el problema se parezca a un sistema lineal ruidoso que es difícil de resolver.
Historia
El trabajo fundamental de Ajtai de 1996 conectó la dureza de los retículos con la criptografía. El marco de aprendizaje con errores (LWE) de Regev en 2005 proporcionó una base práctica y versátil para la criptografía de retículos. El campo se aceleró después de que las instituciones académicas y gubernamentales reconocieran la amenaza de la computación cuántica para la infraestructura criptográfica actual. En 2022, NIST estandarizó algoritmos criptográficos postcuánticos, seleccionando esquemas basados en retículos (CRYSTALS-Kyber para cifrado, CRYSTALS-Dilithium para firmas) como recomendaciones principales.
Cuándo usarlo
La criptografía basada en retículos es esencial para los sistemas diseñados para permanecer seguros frente a futuras computadoras cuánticas. Se recomienda para la confidencialidad a largo plazo de datos sensibles, comunicaciones gubernamentales y militares, e infraestructura que debe permanecer segura durante décadas. A medida que los algoritmos postcuánticos estandarizados maduran (NIST recientemente estandarizó ML-KEM y ML-DSA), los métodos de retículos se están convirtiendo en la corriente principal en los sistemas criptográficos modernos.
Limitaciones y consideraciones
- Tamaños de clave y texto cifrado más grandes en comparación con RSA o ECC tradicionales, lo que aumenta la sobrecarga de almacenamiento y transmisión
- Más reciente y menos desplegado extensamente que RSA o ECC, por lo que la experiencia de implementación en el mundo real es limitada
- Algunos esquemas basados en retículos tienen elecciones de parámetros sutiles que afectan significativamente la seguridad; parámetros incorrectos pueden ser catastróficos
Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.
Fortalezas
- Se cree que es resistente a los ataques de computadoras cuánticas, incluido el algoritmo de Shor
- Sólidas bases matemáticas basadas en problemas de retículos bien estudiados
- Soporta tanto cifrado como firmas digitales dentro del mismo marco
- Implementaciones prácticas disponibles con costos computacionales razonables para hardware moderno
Aplicaciones
- Seguridad de transporte postcuántico para proteger las comunicaciones contra futuras decodificaciones cuánticas
- Cifrado de archivo a largo plazo para documentos y datos que deben permanecer secretos durante décadas
- Sistemas de comunicaciones gubernamentales y militares resilientes a amenazas cuánticas
- Sistemas de blockchain y criptomonedas diseñados para seguridad resistente a cuántica
- Sistemas de IoT y embebidos donde la resistencia cuántica es un requisito de diseño
- Sistemas criptográficos híbridos que combinan algoritmos de retículo y tradicionales durante el período de transición criptográfica
Cómo funciona
Cómo funciona
Elegir las dimensiones del retículo n, el módulo q y la distribución de errores. Generar una base corta secreta y derivar una base pública a partir de ella utilizando transformaciones de retículos.
La clave pública se deriva de la base difícil del retículo; no proporciona información sobre la base secreta desde una perspectiva computacional.
Para cifrar, añadir el texto plano a una combinación lineal ruidosa de los vectores de la base pública, creando un punto de retículo más ruido.
Utilizando la base corta secreta, reducir el punto de retículo ruidoso y extraer el texto plano.
Errores comunes
- La selección de parámetros de retículo (dimensión, módulo, distribución de errores) no es trivial; se recomienda encarecidamente el uso de parámetros estándar aprobados por NIST
- Los ataques de canal lateral (temporización, análisis de potencia) en operaciones de retículo requieren una implementación cuidadosa; los algoritmos de tiempo constante son esenciales
- Mezclar algoritmos basados en retículos y clásicos incorrectamente puede crear sistemas híbridos con debilidades inesperadas
Preguntas frecuentes
¿Cuál es el problema de aprendizaje con errores (LWE)?
LWE es un problema computacional en el que se dan ecuaciones lineales ruidosas sobre un campo finito. Dadas ecuaciones de la forma a·x + e (mod q) donde a es aleatorio, x es secreto y e es un ruido pequeño, recuperar x sin conocer e es computacionalmente difícil.
¿Por qué las claves basadas en retículos son más grandes que las claves RSA?
Las bases de retículo y las matrices que las codifican contienen más información que un solo número compuesto. Codificar una base de retículo criptográficamente requiere más bits, aunque esquemas recientes han optimizado las representaciones.
¿Son los problemas de retículo resistentes a la cuántica?
No se conoce ningún algoritmo cuántico más rápido que los algoritmos clásicos para problemas de retículo como SVP o LWE, aunque esta sigue siendo un área de investigación activa. Se conjetura que la dureza de los retículos sobrevive a las computadoras cuánticas.
¿Cuál es la recomendación de NIST sobre criptografía de retículos?
NIST estandarizó ML-KEM (Mecanismo de encapsulación de clave basado en retículos modulares) para cifrado y ML-DSA (Algoritmo de firma digital basado en retículos modulares) para firmas como algoritmos postcuánticos primarios en FIPS 203 y FIPS 204.
¿Puedo usar criptografía basada en retículos hoy en día?
Sí. Muchas bibliotecas criptográficas modernas ahora admiten algoritmos de retículo estandarizados por NIST. Las organizaciones que manejan datos sensibles con largos períodos de retención deberían comenzar la planificación de la migración.
Métodos relacionados
Fuentes
Ajtai, M. (1996). Generating hard instances of the short basis problem. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 99-108.
Abrir referencia de la publicaciónCopiado.Regev, O. (2005). On lattices, learning with errors, hard instances, and public key cryptography. In Proceedings of STOC 2005, pp. 84-93.
Abrir referencia de la publicaciónCopiado.