💻 computer science

Time-Complexity Characterization of NIST Lightweight Cryptography Finalists

This paper introduces a symbolic model to formally derive the time complexity of all ten NIST lightweight cryptography finalists by decomposing them into initialization, data-processing, and finalization phases, thereby providing a unified theoretical framework to guide the selection of efficient primitives for resource-constrained environments.

Original authors: Najmul Hasan, Prashanth BusiReddyGari

Published 2026-02-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Najmul Hasan, Prashanth BusiReddyGari

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a fleet of tiny, battery-powered robots (like smart sensors or IoT devices) that need to send secret messages. These robots are very small and have very little energy, so they can't carry heavy backpacks or run complex marathons. They need a "lock and key" system (cryptography) that is super secure but also incredibly light and fast.

The National Institute of Standards and Technology (NIST) held a competition to find the best 10 "locks" for these tiny robots. They tested them in the real world, but they didn't have a single, unified math formula to explain why some were faster than others on paper.

This paper by Najmul Hasan and Prashanth BusiReddyGari fills that gap. Here is what they did, explained simply:

1. The Problem: Measuring the "Weight" of a Lock

Think of the 10 finalists as 10 different types of backpacks. Some are made of light foam, others of heavy steel. NIST already weighed them on a scale (empirical testing), but the authors wanted to write a recipe that predicts exactly how heavy a backpack will be based on how much stuff you put inside it, without actually having to pack it every time.

They wanted to create a "Time Complexity" map. In simple terms, this is a formula that tells you: "If you have a short message, how fast is the lock? If you have a long message, how much slower does it get?"

2. The Solution: The Three-Stage Assembly Line

The authors broke every single one of the 10 cryptographic algorithms down into three simple stages, like a factory assembly line:

Stage 1: Initialization (The Setup): Before you can pack anything, you have to set up the machine. You plug in the key and the "nonce" (a unique number for the session). This takes a fixed amount of time, no matter how big your message is. It's like warming up a car engine; it takes the same time whether you drive 1 mile or 100.
Stage 2: Data Processing (The Packing): This is where the actual message and extra data get encrypted. This is the heavy lifting. The time it takes here depends entirely on how much data you have. The authors created formulas to calculate exactly how many "steps" (mathematical operations) are needed per block of data.
Stage 3: Finalization (The Seal): Once everything is packed, you need to seal the box and attach a security tag to prove it hasn't been tampered with. This is another fixed amount of work, like putting a final sticker on a package.

3. The Results: Who is the Lightest?

By applying this three-stage model to all 10 finalists, the authors created a "menu" of formulas (shown in their Table I) that describes the "weight" of each algorithm.

Here are some of the interesting findings they uncovered using their new formulas:

The "Simple Linear" Runners: Algorithms like GIFT-COFB, Grain-128AEAD, and ISAP are like a straight highway. Their time grows perfectly in step with the message size. If you double the message, you double the time. They don't have extra "taxes" or complex multipliers. GIFT-COFB is particularly simple, making it very efficient for big messages.
The "Block" Runners: Algorithms like TinyJambu and Romulus work like a conveyor belt that only accepts items in specific-sized boxes. If your message doesn't fit perfectly into a box, they have to add "padding" (empty space) to fill it up. This adds a little extra overhead, especially for small messages, but they are very structured.
The "Permutation" Runners: Algorithms like ASCON (which NIST eventually picked as the winner) and Xoodyak use a "shuffling" method. They take the data and mix it around in a specific pattern. Their formulas show that they are very efficient, with the time cost mostly coming from how many times they have to shuffle the data.
The "Hybrid" Runner: ISAP is a mix of different techniques. It creates a temporary key for every session, which adds a tiny bit of setup time but makes it very secure against certain types of hacking.

4. Why This Matters

The paper doesn't just say "Algorithm A is faster." It explains why by looking at the math behind the design.

Design Choices: The authors show that the "shape" of the algorithm dictates its speed. Some are built like a single-lane road (stream ciphers), while others are built like a multi-lane highway with toll booths (block ciphers).
Predictability: Now, engineers designing these tiny devices can look at these formulas and predict exactly how much battery life an algorithm will eat up before they even build the device.

The Bottom Line

This paper provides a universal translator for cryptographic performance. Instead of guessing or running endless tests, engineers can now use these symbolic formulas to pick the perfect "lock" for their specific robot.

If you need the absolute simplest, lightest path for huge messages, the math points to GIFT-COFB.
If you need a balance of security and speed for general use, the math highlights ASCON.
If you need to process data bit-by-bit without waiting for full blocks, Grain-128AEAD is the clear choice.

The authors conclude that by understanding these theoretical "weights," we can better secure the Internet of Things, ensuring our tiny devices stay secure without running out of battery. They plan to test these formulas in real-world scenarios like digital ID cards to see if the math holds up in the real world.

Technical Summary: Time-Complexity Characterization of NIST Lightweight Cryptography Finalists

Problem Statement
As emerging technologies in digital identity systems and the Internet of Things (IoT) increasingly rely on devices with limited processing power, memory, and energy, the demand for lightweight cryptography (LWC) has become critical. While the National Institute of Standards and Technology (NIST) completed a standardization process evaluating ten finalist algorithms, the existing literature relies heavily on empirical benchmarks (execution time and throughput) rather than a unified theoretical understanding. Current documentation for finalists such as Ascon, ISAP, and TinyJAMBU focuses on implementation optimizations but lacks formal time-complexity expressions. This absence of a theoretical framework hinders the ability to systematically distinguish algorithmic efficiency and predict performance scaling across diverse constrained environments.

Methodology
The authors propose a symbolic model to decompose the time complexity of cryptographic schemes into three distinct phases: initialization, data processing, and finalization. This framework allows for the derivation of formal time-complexity expressions independent of specific hardware platforms.

The total time complexity ( $T_{total}$ ) is modeled as the sum of:

Initialization ( $T_{init}$ ): Fixed costs for key and nonce setup ($ck + cn$), independent of input size.
Data Processing ( $T_{process}$ ): Costs associated with processing associated data ( $A$ ) and message blocks ( $M$ ). This is decomposed into $T_A$ and $T_M$ , calculated based on block counts, permutation times ( $T_p$ ), and operation overheads.
Finalization ( $T_{finalize}$ ): Constant time costs ( $c_f$ ) for authentication tag generation or validation.

Using this three-phase decomposition, the authors derive symbolic complexity expressions for all ten NIST finalists (Ascon, Elephant, GIFT-COFB, Grain-128AEAD, ISAP, PHOTON-Beetle, Romulus, SPARKLE, TinyJAMBU, and Xoodyak) based on their algorithmic specifications, including state sizes, permutation designs, and modes of operation.

Key Contributions and Results
The paper provides a comparative analysis of the computational scaling of the ten finalists, categorizing them by their underlying architectural strategies:

Permutation-Based Algorithms: Five finalists (Ascon, Elephant, PHOTON-Beetle, SPARKLE, Xoodyak) utilize sponge-based or permutation-centered constructions. Their complexity is generally dominated by the permutation cost ( $b$ ) and the number of blocks processed. For instance, Ascon achieves efficient scaling ( $O(l_A \cdot b + l_P \cdot b)$ ) through a streamlined 12-round initialization, while SPARKLE includes additional constant terms to support both encryption and hashing functionalities.
Block Cipher-Based Algorithms: Three finalists (GIFT-COFB, Romulus-N, TinyJAMBU) employ block cipher or register-based constructions. GIFT-COFB is highlighted for its notably simple linear scaling ( $O(\ell_A + \ell_M)$ ) without multiplicative factors, making it highly efficient for large messages. TinyJAMBU utilizes dual permutations ( $P_{640}$ and $P_{1024}$ ) for different phases, introducing specific fixed initialization costs and separate processing costs for associated data and messages.
Stream Cipher and Hybrid Algorithms: Grain-128AEAD is the sole stream cipher finalist, offering complexity ($O(|M| + |AD|)$) that scales directly with bit count, thereby eliminating padding overhead. ISAP combines sponge-based encryption with session key derivation, achieving linear scaling ( $O(|A| + |M|)$ ) while providing resistance against side-channel attacks through key separation.

The analysis reveals that while all algorithms exhibit linear scaling with input lengths, the coefficients vary significantly based on design parameters such as block size, rate, and permutation complexity. No single algorithm dominates across all metrics; rather, trade-offs exist between simplicity, functionality, and security margins.

Significance
The paper claims that this unified symbolic framework provides a necessary theoretical foundation for evaluating lightweight cryptographic primitives. By clarifying how design parameters shape computational scaling, the model enables researchers and practitioners to distinguish algorithmic efficiency more rigorously than empirical benchmarks alone allow. The authors assert that this work guides the selection of primitives capable of supporting security systems in constrained environments, such as mobile and embedded devices. The paper concludes by noting that these theoretical results serve as a basis for future validation in specific real-world contexts, such as mobile driver's license environments, though the current work remains focused on the derivation of the symbolic models themselves.

1. The Problem: Measuring the "Weight" of a Lock

2. The Solution: The Three-Stage Assembly Line

3. The Results: Who is the Lightest?

4. Why This Matters

The Bottom Line

More like this