💻 computer science

Time-Complexity Characterization of NIST Lightweight Cryptography Finalists

Este artigo introduz um modelo simbólico para derivar formalmente a complexidade de tempo de todos os dez finalistas da criptografia leve do NIST ao decompô-los em fases de inicialização, processamento de dados e finalização, fornecendo, assim, um arcabouço teórico unificado para orientar a seleção de primitivas eficientes para ambientes com recursos limitados.

Autores originais: Najmul Hasan, Prashanth BusiReddyGari

Publicado 2026-02-06

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Najmul Hasan, Prashanth BusiReddyGari

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você tem uma frota de pequenos robôs, movidos a bateria (como sensores inteligentes ou dispositivos IoT), que precisam enviar mensagens secretas. Esses robôs são muito pequenos e têm pouquíssima energia, então não podem carregar mochilas pesadas ou correr maratonas complexas. Eles precisam de um sistema de "cadeado e chave" (criptografia) que seja super seguro, mas também incrivelmente leve e rápido.

O Instituto Nacional de Padrões e Tecnologia (NIST) realizou uma competição para encontrar os 10 melhores "cadeados" para esses pequenos robôs. Eles testaram os candidatos no mundo real, mas não tinham uma fórmula matemática única e unificada para explicar por que alguns eram mais rápidos que outros no papel.

Este artigo de Najmul Hasan e Prashanth BusiReddyGari preenche essa lacuna. Aqui está o que eles fizeram, explicado de forma simples:

1. O Problema: Medindo o "Peso" de um Cadeado

Pense nos 10 finalistas como 10 tipos diferentes de mochilas. Algumas são feitas de espuma leve, outras de aço pesado. O NIST já as pesou em uma balança (testes empíricos), mas os autores queriam escrever uma receita que previsse exatamente quão pesada uma mochila será com base em quanta coisa você coloca dentro dela, sem precisar embalá-la toda vez.

Eles queriam criar um mapa de "Complexidade de Tempo". Em termos simples, esta é uma fórmula que diz: "Se você tiver uma mensagem curta, quão rápido é o cadeado? Se você tiver uma mensagem longa, o quanto ele fica mais lento?"

2. A Solução: A Linha de Montagem de Três Estágios

Os autores decomporam cada um dos 10 algoritmos criptográficos em três estágios simples, como uma linha de montagem de fábrica:

Estágio 1: Inicialização (A Configuração): Antes de poder embalar qualquer coisa, você precisa configurar a máquina. Você insere a chave e o "nonce" (um número único para a sessão). Isso leva um tempo fixo, não importa o tamanho da sua mensagem. É como aquecer o motor de um carro; leva o mesmo tempo, quer você dirija 1 milha ou 100.
Estágio 2: Processamento de Dados (O Empacotamento): É aqui que a mensagem real e os dados extras são criptografados. Este é o trabalho pesado. O tempo gasto aqui depende inteiramente de quanta informação você tem. Os autores criaram fórmulas para calcular exatamente quantos "passos" (operações matemáticas) são necessários por bloco de dados.
Estágio 3: Finalização (O Selo): Depois de tudo embalado, você precisa selar a caixa e anexar uma etiqueta de segurança para provar que ela não foi adulterada. Este é outro trabalho de valor fixo, como colocar um adesivo final em um pacote.

3. Os Resultados: Quem é o Mais Leve?

Ao aplicar este modelo de três estágios a todos os 10 finalistas, os autores criaram um "menu" de fórmulas (mostrado em sua Tabela I) que descreve o "peso" de cada algoritmo.

Aqui estão algumas das descobertas interessantes que eles revelaram usando suas novas fórmulas:

Os Corredores "Lineares Simples": Algoritmos como GIFT-COFB, Grain-128AEAD e ISAP são como uma rodovia reta. Seu tempo cresce perfeitamente em sintonia com o tamanho da mensagem. Se você dobrar a mensagem, dobra o tempo. Eles não têm "taxas" extras ou multiplicadores complexos. O GIFT-COFB é particularmente simples, tornando-o muito eficiente para mensagens grandes.
Os Corredores de "Bloco": Algoritmos como TinyJambu e Romulus funcionam como uma esteira transportadora que só aceita itens em caixas de tamanhos específicos. Se sua mensagem não se encaixar perfeitamente em uma caixa, eles precisam adicionar "preenchimento" (espaço vazio) para completá-la. Isso adiciona um pouco de sobrecarga extra, especialmente para mensagens pequenas, mas eles são muito estruturados.
Os Corredores de "Permutação": Algoritmos como ASCON (que o NIST acabou escolhendendo como vencedor) e Xoodyak usam um método de "embaralhamento". Eles pegam os dados e os misturam em um padrão específico. Suas fórmulas mostram que eles são muito eficientes, e o custo de tempo vem principalmente de quantas vezes eles precisam embaralhar os dados.
O Corredor "Híbrido": O ISAP é uma mistura de diferentes técnicas. Ele cria uma chave temporária para cada sessão, o que adiciona um tempo de configuração minúsculo, mas o torna muito seguro contra certos tipos de ataques.

4. Por Que Isso Importa

O artigo não diz apenas que "Algoritmo A é mais rápido". Ele explica por que, olhando para a matemática por trás do design.

Escolhas de Design: Os autores mostram que a "forma" do algoritmo dita sua velocidade. Alguns são construídos como uma estrada de pista única (cifras de fluxo/stream ciphers), enquanto outros são construídos como uma rodovia de várias faixas com pedágios (cifras de bloco/block ciphers).
Previsibilidade: Agora, engenheiros projetando esses pequenos dispositivos podem olhar para essas fórmulas e prever exatamente quanta bateria um algoritmo consumirá antes mesmo de construírem o dispositivo.

A Conclusão

Este artigo fornece um tradutor universal para o desempenho criptográfico. Em vez de adivinhar ou realizar testes intermináveis, os engenheiros agora podem usar essas fórmulas simbólicas para escolher o "cadeado" perfeito para seu robô específico.

Se você precisa do caminho absolutamente mais simples e leve para mensagens enormes, a matemática aponta para o GIFT-COFB.
Se você precisa de um equilíbrio entre segurança e velocidade para uso geral, a matemática destaca o ASCON.
Se você precisa processar dados bit a bit sem esperar por blocos completos, o Grain-128AEAD é a escolha clara.

Os autores concluem que, ao compreender esses "pesos" teóricos, podemos proteger melhor a Internet das Coisas, garantindo que nossos pequenos dispositivos permaneçam seguros sem esgotar a bateria. Eles planejam testar essas fórmulas em cenários do mundo real, como cartões de identidade digitais, para ver se a matemática se sustenta na prática.

Resumo Técnico: Caracterização da Complexidade de Tempo dos Finalistas da Criptografia Leve do NIST

Declaração do Problema
À medida que as tecnologias emergentes em sistemas de identidade digital e na Internet das Coisas (IoT) dependem cada vez mais de dispositivos com poder de processamento, memória e energia limitados, a demanda por criptografia leve (LWC) tornou-se crítica. Embora o Instituto Nacional de Padrões e Tecnologia (NIST) tenha concluído um processo de padronização avaliando dez algoritmos finalistas, a literatura existente baseia-se fortemente em benchmarks empíricos (tempo de execução e vazão) em vez de uma compreensão teórica unificada. A documentação atual para finalistas como Ascon, ISAP e TinyJAMBU foca em otimizações de implementação, mas carece de expressões formais de complexidade de tempo. Essa ausência de um framework teórico dificulta a distinção sistemática da eficiência algorítmica e a previsão de escalonamento de desempenho em diversos ambientes restritos.

Metodologia
Os autores propõem um modelo simbólico para decompor a complexidade de tempo de esquemas criptográficos em três fases distintas: inicialização, processamento de dados e finalização. Este framework permite a derivação de expressões formais de complexidade de tempo independentes de plataformas de hardware específicas.

A complexidade de tempo total ( $T_{total}$ ) é modelada como a soma de:

Inicialização ( $T_{init}$ ): Custos fixos para configuração de chave e nonce ($ck + cn$), independentes do tamanho da entrada.
Processamento de Dados ( $T_{process}$ ): Custos associados ao processamento de dados associados ( $A$ ) e blocos de mensagem ( $M$ ). Isso é decomposto em $T_A$ e $T_M$ , calculados com base em contagens de blocos, tempos de permutação ( $T_p$ ) e sobrecargas de operação.
Finalização ( $T_{finalize}$ ): Custos de tempo constante ( $c_f$ ) para geração ou validação de tag de autenticação.

Usando esta decomposição de três fases, os autores derivam expressões de complexidade simbólica para todos os dez finalistas do NIST (Ascon, Elephant, GIFT-COFB, Grain-128AEAD, ISAP, PHOTON-Beetle, Romulus, SPARKLE, TinyJAMBU e Xoodyak) com base em suas especificações algorítmicas, incluindo tamanhos de estado, designs de permutação e modos de operação.

Contribuições Principais e Resultados
O artigo fornece uma análise comparativa do escalonamento computacional dos dez finalistas, categorizando-os por suas estratégias arquiteturais subjacentes:

Algoritmos Baseados em Permutação: Cinco finalistas (Ascon, Elephant, PHOTON-Beetle, SPARKLE, Xoodyak) utilizam construções baseadas em esponja ou centradas em permutação. Sua complexidade é geralmente dominada pelo custo da permutação ( $b$ ) e pelo número de blocos processados. Por exemplo, o Ascon alcança um escalonamento eficiente ( $O(l_A \cdot b + l_P \cdot b)$ ) através de uma inicialização simplificada de 12 rodadas, enquanto o SPARKLE inclui termos constantes adicionais para suportar tanto funcionalidades de criptografia quanto de hashing.
Algoritmos Baseados em Cifra de Bloco: Três finalistas (GIFT-COFB, Romulus-N, TinyJAMBU) empregam construções de cifra de bloco ou baseadas em registradores. O GIFT-COFB é destacado por seu escalonamento linear notavelmente simples ( $O(\ell_A + \ell_M)$ ) sem fatores multiplicativos, tornando-o altamente eficiente para mensagens grandes. O TinyJAMBU utiliza permutações duplas ( $P_{640}$ e $P_{1024}$ ) para diferentes fases, introduzindo custos de inicialização fixos específicos e custos de processamento separados para dados associados e mensagens.
Algoritmos de Cifra de Fluxo e Híbridos: O Grain-128AEAD é o único finalista de cifra de fluxo, oferecendo complexidade ($O(|M| + |AD|)$) que escala diretamente com a contagem de bits, eliminando assim o overhead de preenchimento (padding). O ISAP combina criptografia baseada em esponja com derivação de chave de sessão, alcançando escalonamento linear ( $O(|A| + |M|)$ ) enquanto provê resistência contra ataques de canal lateral através da separação de chaves.

A análise revela que, embora todos os algoritmos exibam escalonamento linear com comprimentos de entrada, os coeficientes variam significativamente com base em parâmetros de design como tamanho de bloco, taxa e complexidade de permutação. Nenhum algoritmo único domina em todas as métricas; em vez disso, existem trade-offs entre simplicidade, funcionalidade e margens de segurança.

Significância
O artigo afirma que este framework simbólico unificado fornece uma base teórica necessária para avaliar primitivas criptográficas leves. Ao esclarecer como os parâmetros de design moldam o escalonamento computacional, o modelo permite que pesquisadores e profissionais distingam a eficiência algorítmica de forma mais rigorosa do que os benchmarks empíricos sozinhos permitem. Os autores afirmam que este trabalho guia a seleção de primitivas capazes de suportar sistemas de segurança em ambientes restritos, como dispositivos móveis e embarcados. O artigo conclui observando que estes resultados teóricos servem como base para validação futura em contextos reais específicos, como ambientes de carteira de motorista móvel, embora o presente trabalho permaneça focado na derivação dos próprios modelos simbólicos.

1. O Problema: Medindo o "Peso" de um Cadeado

2. A Solução: A Linha de Montagem de Três Estágios

3. Os Resultados: Quem é o Mais Leve?

4. Por Que Isso Importa

A Conclusão

Mais como este