💻 computer science

Time-Complexity Characterization of NIST Lightweight Cryptography Finalists

Este artículo introduce un modelo simbólico para derivar formalmente la complejidad temporal de los diez finalistas de la criptografía ligera del NIST mediante la descomposición de estos en fases de inicialización, procesamiento de datos y finalización, proporcionando así un marco teórico unificado para guiar la selección de primitivas eficientes para entornos con recursos limitados.

Autores originales: Najmul Hasan, Prashanth BusiReddyGari

Publicado 2026-02-06

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Najmul Hasan, Prashanth BusiReddyGari

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que tienes una flota de diminutos robots impulsados por baterías (como sensores inteligentes o dispositivos IoT) que necesitan enviar mensajes secretos. Estos robots son muy pequeños y tienen muy poca energía, por lo que no pueden cargar mochilas pesadas ni correr maratones complejas. Necesitan un sistema de "cerradura y llave" (criptografía) que sea súper seguro pero también increíblemente ligero y rápido.

El Instituto Nacional de Estándares y Tecnología (NIST) organizó una competencia para encontrar los 10 mejores "candados" para estos diminutos robots. Probaron los 10 finalistas en el mundo real, pero no tenían una fórmula matemática unificada para explicar por qué algunos eran más rápidos que otros sobre el papel.

Este artículo de Najmul Hasan y Prashanth BusiReddyGari llena ese vacío. Esto es lo que hicieron, explicado de forma sencilla:

1. El Problema: Medir el "Peso" de una Cerradura

Piensa en los 10 finalistas como 10 tipos diferentes de mochilas. Algunas están hechas de espuma ligera, otras de acero pesado. El NIST ya las pesó en una báscula (pruebas empíricas), pero los autores querían escribir una receta que prediga exactamente qué tan pesada será una mochila basándose en cuántas cosas pongas dentro, sin tener que empacarla cada vez.

Querían crear un mapa de "Complejidad de Tiempo". En términos simples, esta es una fórmula que te dice: "Si tienes un mensaje corto, ¿qué tan rápida es la cerradura? Si tienes un mensaje largo, ¿qué tanto se ralentiza?"

2. La Solución: La Línea de Ensamblaje de Tres Etapas

Los autores desglosaron cada uno de los 10 algoritmos criptográficos en tres etapas simples, como una línea de ensamblaje de una fábrica:

Etapa 1: Inicialización (La Configuración): Antes de poder empacar cualquier cosa, tienes que configurar la máquina. Introduces la llave y el "nonce" (un número único para la sesión). Esto toma una cantidad de tiempo fija, sin importar cuán grande sea tu mensaje. Es como calentar el motor de un coche; toma el mismo tiempo ya sea que conduzcas 1 milla o 100.
Etapa 2: Procesamiento de Datos (El Empaque): Aquí es donde se encripta el mensaje real y los datos adicionales. Este es el trabajo pesado. El tiempo que toma aquí depende enteramente de cuántos datos tengas. Los autores crearon fórmulas para calcular exactamente cuántos "pasos" (operaciones matemáticas) se necesitan por cada bloque de datos.
Etapa 3: Finalización (El Sellado): Una vez que todo está empacado, necesitas sellar la caja y adjuntar una etiqueta de seguridad para demostrar que no ha sido manipulada. Este es otro trabajo de cantidad fija, como poner una pegatina final en un paquete.

3. Los Resultados: ¿Quién es el más Ligero?

Al aplicar este modelo de tres etapas a todos los 10 finalistas, los autores crearon un "menú" de fórmulas (mostrado en su Tabla I) que describe el "peso" de cada algoritmo.

Aquí están algunos de los hallazgos interesantes que descubrieron usando sus nuevas fórmulas:

Los Corredores de "Línea Recta Simple": Algoritmos como GIFT-COFB, Grain-128AEAD e ISAP son como una autopista recta. Su tiempo crece perfectamente al ritmo del tamaño del mensaje. Si duplicas el mensaje, duplicas el tiempo. No tienen "impuestos" adicionales o multiplicadores complejos. GIFT-COFB es particularmente simple, lo que lo hace muy eficiente para mensajes grandes.
Los Corredores de "Bloque": Algoritmos como TinyJambu y Romulus funcionan como una cinta transportadora que solo acepta artículos en cajas de tamaños específicos. Si tu mensaje no encaja perfectamente en una caja, tienen que añadir "relleno" (espacio vacío) para completarla. Esto añade un poco de sobrecarga, especialmente para mensajes pequeños, pero son muy estructurados.
Los Corredores de "Permutación": Algoritmos como ASCON (que el NIST terminó eligiendo como ganador) y Xoodyak usan un método de "mezcla". Toman los datos y los mezclan en un patrón específico. Sus fórmulas muestran que son muy eficientes, y el costo de tiempo proviene principalmente de cuántas veces tienen que mezclar los datos.
El Corredor "Híbrido": ISAP es una mezcla de diferentes técnicas. Crea una clave temporal para cada sesión, lo que añade un tiempo de configuración minúsculo pero lo hace muy seguro contra ciertos tipos de hackeo.

4. Por qué esto Importa

El artículo no solo dice "el Algoritmo A es más rápido". Explica por qué mirando la matemática detrás del diseño.

Elecciones de Diseño: Los autores muestran que la "forma" del algoritmo dicta su velocidad. Algunos están construidos como un camino de un solo carril (cifrados de flujo/stream ciphers), mientras que otros están construidos como una autopista de varios carriles con peajes (cifrados de bloque/block ciphers).
Predictibilidad: Ahora, los ingenieros que diseñan estos dispositivos diminutos pueden mirar estas fórmulas y predecir exactamente cuánta batería consumirá un algoritmo antes de que siquiera construyan el dispositivo.

La Conclusión

Este artículo proporciona un traductor universal para el rendimiento criptográfico. En lugar de adivinar o realizar pruebas interminables, los ingenieros ahora pueden usar estas fórmulas simbólicas para elegir la "cerradura" perfecta para su robot específico.

Si necesitas el camino más simple y ligero para mensajes enormes, las matemáticas apuntan a GIFT-COFB.
Si necesitas un equilibrio entre seguridad y velocidad para uso general, las matemáticas resaltan a ASCON.
Si necesitas procesar datos bit a bit sin esperar a bloques completos, Grain-128AEAD es la elección clara.

Los autores concluyen que, al comprender estos "pesos" teóricos, podemos asegurar mejor el Internet de las Cosas, garantizando que nuestros diminutos dispositivos se mantengan seguros sin quedarse sin batería. Planean probar estas fórmulas en escenarios del mundo real, como tarjetas de identificación digital, para ver si la matemática se sostiene en el mundo real.

Resumen Técnico: Caracterización de la Complejidad Temporal de los Finalistas de Criptografía Ligera del NIST

Planteamiento del Problema
A medida que las tecnologías emergentes en sistemas de identidad digital e Internet de las Cosas (IoT) dependen cada vez más de dispositivos con potencia de procesamiento, memoria y energía limitadas, la demanda de criptografía ligera (LWC) se ha vuelto crítica. Si bien el Instituto Nacional de Estándares y Tecnología (NIST) completó un proceso de estandarización evaluando diez algoritmos finalistas, la literatura existente se basa predominantemente en comparativas empíricas (tiempo de ejecución y rendimiento) en lugar de una comprensión teórica unificada. La documentación actual para finalistas como Ascon, ISAP y TinyJAMBU se centra en optimizaciones de implementación, pero carece de expresiones formales de complejidad temporal. Esta ausencia de un marco teórico dificulta la capacidad de distinguir sistemáticamente la eficiencia algorítmica y predecir el escalamiento del rendimiento en diversos entornos restringidos.

Metodología
Los autores proponen un modelo simbólico para descomponer la complejidad temporal de los esquemas criptográficos en tres fases distintas: inicialización, procesamiento de datos y finalización. Este marco permite la derivación de expresiones formales de complejidad temporal independientes de plataformas de hardware específicas.

La complejidad temporal total ( $T_{total}$ ) se modela como la suma de:

Inicialización ( $T_{init}$ ): Costos fijos para la configuración de clave y nonce ($ck + cn$), independientes del tamaño de la entrada.
Procesamiento de Datos ( $T_{process}$ ): Costos asociados con el procesamiento de datos asociados ( $A$ ) y bloques de mensajes ( $M$ ). Esto se descompone en $T_A$ y $T_M$ , calculados basándose en el conteo de bloques, tiempos de permutación ( $T_p$ ) y sobrecargas de operación.
Finalización ( $T_{finalize}$ ): Costos de tiempo constante ( $c_f$ ) para la generación o validación del tag de autenticación.

Utilizando esta descomposición de tres fases, los autores derivan expresiones de complejidad simbólica para los diez finalistas del NIST (Ascon, Elephant, GIFT-COFB, Grain-128AEAD, ISAP, PHOTON-Beetle, Romulus, SPARKLE, TinyJAMBU y Xoodyak) basadas en sus especificaciones algorítmicas, incluyendo tamaños de estado, diseños de permutación y modos de operación.

Contribuciones Clave y Resultados
El artículo proporciona un análisis comparativo del escalamiento computacional de los diez finalistas, categorizándolos según sus estrategias arquitectónicas subyacentes:

Algoritmos Basados en Permutaciones: Cinco finalistas (Ascon, Elephant, PHOTON-Beetle, SPARKLE, Xoodyak) utilizan construcciones basadas en esponjas o centradas en permutaciones. Su complejidad está generalmente dominada por el costo de la permutación ( $b$ ) y el número de bloques procesados. Por ejemplo, Ascon logra un escalamiento eficiente ( $O(l_A \cdot b + l_P \cdot b)$ ) mediante una inicialización simplificada de 12 rondas, mientras que SPARKLE incluye términos constantes adicionales para soportar tanto funcionalidades de cifrado como de hashing.
Algoritmos Basados en Cifrados de Bloque: Tres finalistas (GIFT-COFB, Romulus-N, TinyJAMBU) emplean construcciones de cifrado de bloque o basadas en registros. Se destaca a GIFT-COFB por su escalamiento lineal notablemente simple ( $O(\ell_A + \ell_M)$ ) sin factores multiplicativos, lo que lo hace altamente eficiente para mensajes grandes. TinyJAMBU utiliza permutaciones duales ( $P_{640}$ y $P_{1024}$ ) para diferentes fases, introduciendo costos de inicialización fijos específicos y costos de procesamiento separados para los datos asociados y los mensajes.
Algoritmos de Cifrado de Flujo e Híbridos: Grain-128AEAD es el único finalista de cifrado de flujo, ofreciendo una complejidad ($O(|M| + |AD|)$) que escala directamente con el conteo de bits, eliminando así la sobrecarga de relleno (padding). ISAP combina el cifrado basado en esponjas con la derivación de claves de sesión, logrando un escalamiento lineal ( $O(|A| + |M|)$ ) mientras proporciona resistencia contra ataques de canal lateral mediante la separación de claves.

El análisis revela que, si bien todos los algoritmos exhiben un escalamiento lineal con las longitudes de entrada, los coeficientes varían significamente según los parámetros de diseño como el tamaño de bloque, la tasa y la complejidad de la permutación. Ningún algoritmo domina en todas las métricas; más bien, existen compensaciones entre simplicidad, funcionalidad y márgenes de seguridad.

Significancia
El artículo sostiene que este marco simbólico unificado proporciona una base teórica necesaria para evaluar las primitivas criptográficas ligeras. Al clarificar cómo los parámetros de diseño moldean el escalamiento computacional, el modelo permite a investigadores y profesionales distinguir la eficiencia algorítmica de manera más rigurosa de lo que permiten las comparativas empíricas por sí solas. Los autores afirman que este trabajo guía la selección de primitivas capaces de soportar sistemas de seguridad en entornos restringidos, tales como dispositivos móviles y embebidos. El documento concluye señalando que estos resultados teóricos sirven como base para la validación futura en contextos específicos del mundo real, como entornos de licencias de conducir móviles, aunque el presente trabajo permanece enfocado en la derivación de los propios modelos simbólicos.

1. El Problema: Medir el "Peso" de una Cerradura

2. La Solución: La Línea de Ensamblaje de Tres Etapas

3. Los Resultados: ¿Quién es el más Ligero?

4. Por qué esto Importa

La Conclusión

Más como este