💻 computer science

Time-Complexity Characterization of NIST Lightweight Cryptography Finalists

Dit artikel introduceert een symbolisch model om de tijdcomplexiteit van alle tien de NIST-finalisten voor lichte cryptografie formeel af te leiden door deze te ontbinden in initialisatie-, gegevensverwerkings- en finalisatiefasen, waardoor een verenigd theoretisch kader wordt geboden om de selectie van efficiënte primitieven voor omgevingen met beperkte middelen te begeleiden.

Oorspronkelijke auteurs: Najmul Hasan, Prashanth BusiReddyGari

Gepubliceerd 2026-02-06

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Najmul Hasan, Prashanth BusiReddyGari

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een vloot kleine, batterijgestuurde robots hebt (zoals slimme sensoren of IoT-apparaten) die geheime berichten moeten versturen. Deze robots zijn erg klein en hebben heel weinig energie, dus ze kunnen geen zware rugzakken dragen of complexe marathons lopen. Ze hebben een "slot en sleutel"-systeem (cryptografie) nodig dat super beveiligd is, maar ook ongelooflijk licht en snel.

De National Institute of Standards and Technology (NIST) hield een wedstrijd om de 10 beste "sloten" voor deze kleine robots te vinden. Ze testten ze in de echte wereld, maar hadden geen enkele verenigde wiskundige formule om uit te leggen waarom sommige sneller waren dan andere op papier.

Dit artikel van Najmul Hasan en Prashanth BusiReddyGari vult die kloof op. Dit is wat zij deden, eenvoudig uitgelegd:

1. Het Probleem: Het "Gewicht" van een Slot Meten

Beschouw de 10 finalisten als 10 verschillende soorten rugzakken. Sommige zijn gemaakt van licht schuim, andere van zwaar staal. NIST heeft ze al gewogen op een weegschaal (empirische testen), maar de auteurs wilden een recept schrijven dat voorspelt hoe zwaar een rugzak zal zijn op basis van hoeveel spullen je erin stopt, zonder dat je hem telkens echt hoeft in te pakken.

Ze wilden een "Tijdcomplexiteit"-kaart maken. In eenvoudige termen is dit een formule die vertelt: "Als je een kort bericht hebt, hoe snel is het slot? Als je een lang bericht hebt, hoe veel langzamer wordt het?"

2. De Oplossing: De Drie-fasen Assemblagelijn

De auteurs braken elk van de 10 cryptografische algoritmen af in drie eenvoudige fasen, zoals een fabriekslijn:

Fase 1: Initialisatie (De Opstelling): Voordat je iets kunt inpakken, moet je de machine instellen. Je voert de sleutel en de "nonce" (een uniek nummer voor de sessie) in. Dit kost een vaste hoeveelheid tijd, ongeacht hoe groot je bericht is. Het is als het opwarmen van een automotor; dat kost evenveel tijd of je nu 1 mijl of 100 mijl rijdt.
Fase 2: Dataverwerking (Het Inpakken): Dit is waar het eigenlijke bericht en extra gegevens worden versleuteld. Dit is het zware werk. De tijd die hieraan wordt besteed, hangt volledig af van hoeveel data je hebt. De auteurs creëerden formules om precies te berekenen hoeveel "stappen" (wiskundige operaties) nodig zijn per blok data.
Fase 3: Finalisatie (Het Verzegelen): Zodra alles is ingepakt, moet je de doos verzegelen en een beveiligingstag bevestigen om te bewijzen dat er niet mee is geknoeid. Dit is een andere vaste hoeveelheid werk, zoals het plakken van een definitieve sticker op een pakketje.

3. De Resultaten: Wie is het Lichtst?

Door dit drie-fasen model toe te passen op alle 10 de finalisten, creëerden de auteurs een "menu" van formules (getoond in hun Tabel I) die het "gewicht" van elk algoritme beschrijft.

Hier zijn enkele van de interessante bevindingen die zij met hun nieuwe formules hebben ontdekt:

De "Eenvoudige Lineaire" Lopers: Algoritmen zoals GIFT-COFB, Grain-128AEAD en ISAP zijn als een rechte snelweg. Hun tijd groeit perfect in stap met de grootte van het bericht. Als je het bericht verdubbelt, verdubbel je de tijd. Ze hebben geen extra "belastingen" of complexe vermenigvuldigers. GIFT-COFB is bijzonder eenvoudig, wat het zeer efficiënt maakt voor grote berichten.
De "Blok" Lopers: Algoritmen zoals TinyJambu en Romulus werken als een lopende band die alleen items accepteert in specifieke formaten dozen. Als je bericht niet perfect in een doos past, moeten ze "padding" (lege ruimte) toevoegen om de doos op te vullen. Dit voegt een beetje extra overhead toe, vooral voor kleine berichten, maar ze zijn zeer gestructureerd.
De "Permutatie" Lopers: Algoritmen zoals ASCON (die NIST uiteindelijk als winnaar koos) en Xoodyak gebruiken een "husselmethode". Ze nemen de data en mengen deze in een specif으로 patroon. Hun formules laten zien dat ze zeer efficiënt zijn, waarbij de tijdkosten vooral komen door hoe vaak ze de data moeten husselen.
De "Hybride" Loper: ISAP is een mix van verschillende technieken. Het creëert een tijdelijke sleutel voor elke sessie, wat een klein beetje opstarttijd toevoegt, maar het maakt het ook zeer veilig tegen bepaalde soorten hacking.

4. Waarom Dit Belangrijk Is

Het artikel zegt niet alleen "Algoritme A is sneller." Het legt uit waarom door te kijken naar de wiskunde achter het ontwerp.

Ontwerpkeuzes: De auteurs laten zien dat de "vorm" van het algoritme de snelheid bepaelt. Sommige zijn gebouwd als een enkelbaansweg (stream ciphers), terwijl andere zijn gebouwd als een snelweg met meerdere rijstroken en tolhuisjes (block ciphers).
Voorspelbaarheid: Nu kunnen ingenieurs die deze kleine apparaten ontwerpen deze formules gebruiken om exact te voorspellen hoeveel batterijduur een algoritme zal verbruiken voordat ze het apparaat zelfs maar bouwen.

De Kernboodschap

Dit artikel biedt een universele vertaler voor cryptografische prestaties. In plaats van te gokken of eindeloze tests uit te voeren, kunnen ingenieurs nu deze symbolische formules gebruiken om het perfecte "slot" te kiezen voor hun specifieke robot.

Als je de absoluut eenvoudigste, lichtste route nodig hebt voor enorme berichten, wijst de wiskunde naar GIFT-COFB.
Als je een balans nodig hebt tussen beveiliging en snelheid voor algemeen gebruik, benadrukt de wiskunde ASCON.
Als je data bit voor bit wilt verwerken zonder te wachten op volledige blokken, is Grain-128AEAD de duidelijke keuze.

De auteurs concluderen dat door het begrijpen van deze theoretische "gewichten", we het Internet of Things beter kunnen beveiligen, waardoor we ervoor zorgen dat onze kleine apparaten veilig blijven zonder dat de batterij leegloopt. Ze zijn van plan om deze formules te testen in real-world scenario's zoals digitale identiteitskaarten om te zien of de wiskunde standhoudt in de echte wereld.

Technische Samenvatting: Tijdcomplexiteitskarakterisering van NIST Lightweight Cryptography Finalisten

Probleemstelling
Naarmate opkomende technologieën in digitale identiteitssystemen en het Internet of Things (IoT) steeds vaker afhankelijk worden van apparaten met beperkte rekenkracht, geheugen en energie, wordt de vraag naar lichtgewicht cryptografie (LWC) cruciaal. Hoewel het National Institute of Standards and Technology (NIST) een standaardisatieproces heeft voltooid waarbij tien finalist-algoritmen zijn geëvalueerd, leunt de bestaande literatuur zwaar op empirische benchmarks (uitvoeringstijd en doorvoer) in plaats van op een verenigd theoretisch begrip. De huidige documentatie voor finalisten zoals Ascon, ISAP en TinyJAMBU richt zich voornamelijk op implementatie-optimalisaties, maar mist formele tijdcomplexiteitsuitdrukkingen. Dit gebrek aan een theoretisch kader belemmert het vermogen om algoritmische efficiëntie systematisch te onderscheiden en de prestatieschaalbaarheid over diverse beperkte omgevingen te voorspellen.

Methodologie
De auteurs stellen een symbolisch model voor om de tijdcomplexiteit van cryptografische schema's te deconstrueren in drie afzonderlijke fasen: initialisatie, gegevensverwerking en finalisatie. Dit kader maakt het mogelijk om formele tijdcomplexiteitsuitdrukkingen af te leiden die onafhankelijk zijn van specifieke hardwareplatforms.

De totale tijdcomplexiteit ( $T_{total}$ ) wordt gemodelleerd als de som van:

Initialisatie ( $T_{init}$ ): Vaste kosten voor de setup van sleutel en nonce ($ck + cn$), onafhankelijk van de invoergrootte.
Gegevensverwerking ( $T_{process}$ ): Kosten verbonden aan het verwerken van geassocieerde gegevens ( $A$ ) en berichtenblokken ( $M$ ). Dit wordt gedecomponeerd in $T_A$ en $T_M$ , berekend op basis van blokaantallen, permutatietijden ( $T_p$ ) en operationele overheads.
Finalisatie ( $T_{finalize}$ ): Constante tijdkosten ( $c_f$ ) voor de generatie of validatie van de authenticatietag.

Met behulp van deze driedelige decompositie leiden de auteurs symbolische complexiteitsuitdrukkingen af voor alle tien de NIST-finalisten (Ascon, Elephant, GIFT-COFB, Grain-128AEAD, ISAP, PHOTON-Beetle, Romulus, SPARKLE, TinyJAMBU en Xoodyak) op basis van hun algoritmische specificaties, inclusief staatgroottes, permutatieontwerpen en modus van operatie.

Belangrijkste Bijdragen en Resultaten
Het artikel biedt een vergelijkende analyse van de computationele schaling van de tien finalisten, waarbij ze worden gecategoriseerd op basis van hun onderliggende architecturale strategieën:

Permutatiegebaseerde Algoritmen: Vijf finalisten (Ascon, Elephant, PHOTON-Beetle, SPARKLE, Xoodyak) maken gebruik van sponge-gebaseerde of permutatie-gecentreerde constructies. Hun complexiteit wordt over het algemeen gedomineerd door de permutatiekosten ( $b$ ) en het aantal verwerkte blokken. Zo bereikt Ascon bijvoorbeeld een efficiënte schaling ( $O(l_A \cdot b + l_P \cdot b)$ ) door een gestroomlijnde 12-ronde initialisatie, terwijl SPARKLE extra constante termen bevat om zowel encryptie- als hashing-functionaliteiten te ondersteunen.
Blokcijfergebaseerde Algoritmen: Drie finalisten (GIFT-COFB, Romulus-N, TinyJAMBU) maken gebruik van blokcijfer- of registergebaseerde constructies. GIFT-COFB wordt uitgelicht vanwege de opvallend eenvoudige lineaire schaling ( $O(\ell_A + \ell_M)$ ) zonder multiplicatieve factoren, wat het zeer efficiënt maakt voor grote berichten. TinyJAMBU maakt gebruik van duale permutaties ( $P_{640}$ en $P_{1024}$ ) voor verschillende fasen, wat specifieke vaste initialisatiekosten en aparte verwerkingskosten voor geassocieerde gegevens en berichten introduceert.
Stream Cipher en Hybride Algoritmen: Grain-128AEAD is de enige stream cipher finalist, die een complexiteit ($O(|M| + |AD|)$) biedt die direct schaalt met het aantal bits, waardoor padding-overhead wordt geëlimineerd. ISAP combineert sponge-gebaseerde encryptie met sessiesleutelafleiding, wat een lineaire schaling ( $O(|A| + |M|)$ ) bereikt terwijl het weerstand biedt tegen zijkanaalaanvallen door middel van sleutelseparatie.

De analyse laat zien dat hoewel alle algoritmen een lineaire schaling vertonen met de invoerlengtes, de coëfficiënten aanzienlijk variëren op basis van ontwerpparameters zoals blokgrootte, rate en permutatiecomplexiteit. Geen enkel algoritme domineert over alle metrieken heen; er bestaan in plaats daarvan afwegingen tussen eenvoud, functionaliteit en beveiligingsmarges.

Betekenis
Het artikel stelt dat dit verenigde symbolische kader een noodzakelijke theoretische basis biedt voor het evalueren van lichtgewicht cryptografische primitieven. Door te verduidelijken hoe ontwerpparameters de computationele schaling vormgeven, stelt het model onderzoekers en praktijkgebruikers in staat om algoritmische efficiëntie rigoureuzer te onderscheiden dan empirische benchmarks alleen dat toelaten. De auteurs beweren dat dit werk helpt bij de selectie van primitieven die in staat zijn om beveiligingssystemen in beperkte omgevingen, zoals mobiele en embedded apparaten, te ondersteunen. Het artikel concludeert door op te merken dat deze theoretische resultaten dienen als basis voor toekomstige validatie in specifieke real-world contexten, zoals omgevingen voor mobiele rijbewijzen, hoewel het huidige werk gericht blijft op de afleiding van de symbolische modellen zelf.

1. Het Probleem: Het "Gewicht" van een Slot Meten

2. De Oplossing: De Drie-fasen Assemblagelijn

3. De Resultaten: Wie is het Lichtst?

4. Waarom Dit Belangrijk Is

De Kernboodschap

Meer zoals dit