💻 computer science

Time-Complexity Characterization of NIST Lightweight Cryptography Finalists

Dieses Paper führt ein symbolisches Modell ein, um die Zeitkomplexität aller zehn NIST-Finalisten für leichte Kryptographie formal abzuleiten, indem es diese in Initialisierungs-, Datenverarbeitungs- und Finalisierungsphasen zerlegt, und stellt damit einen einheitlichen theoretischen Rahmen bereit, der die Auswahl effizienter Primitiven für ressourcenbeschränkte Umgebungen leitet.

Ursprüngliche Autoren: Najmul Hasan, Prashanth BusiReddyGari

Veröffentlicht 2026-02-06

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Najmul Hasan, Prashanth BusiReddyGari

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie haben eine Flotte winziger, batteriebetriebener Roboter (wie intelligente Sensoren oder IoT-Geräte), die geheime Nachrichten senden müssen. Diese Roboter sind sehr klein und verfügen über nur sehr wenig Energie, daher können sie keine schweren Rucksäcke tragen oder komplexe Marathons laufen. Sie benötigen ein „Schloss-und-Schlüssel“-System (Kryptografie), das super sicher, aber auch unglaublich leicht und schnell ist.

Das National Institute of Standards and Technology (NIST) hat einen Wettbewerb veranstaltet, um die 10 besten „Schlösser“ für diese winzigen Roboter zu finden. Sie haben diese in der realen Welt getestet, aber sie hatten keine einzige, einheitliche mathematische Formel, um zu erklären, warum einige auf dem Papier schneller waren als andere.

Dieses Paper von Najmul Hasan und Prashanth BusiReddyGari schließt diese Lücke. Hier ist das, was sie getan haben, einfach erklärt:

1. Das Problem: Das „Gewicht“ eines Schlosses messen

Betrachten Sie die 10 Finalisten als 10 verschiedene Arten von Rucksäcken. Einige sind aus leichtem Schaumstoff, andere aus schwerem Stahl. Das NIST hat sie bereits auf einer Waage gewogen (empirische Tests), aber die Autoren wollten ein Rezept schreiben, das vorhersagt, wie schwer ein Rucksack sein wird, basof dem man hineinlegt, ohne ihn jedes Mal tatsächlich packen zu müssen.

Sie wollten eine „Zeitkomplexitäts“-Karte erstellen. Vereinfacht gesagt ist dies eine Formel, die sagt: „Wenn Sie eine kurze Nachricht haben, wie schnell ist das Schloss? Wenn Sie eine lange Nachricht haben, wie viel langsamer wird es?“

2. Die Lösung: Das Drei-Stufen-Fließband

Die Autoren haben jeden der 10 kryptografischen Algorithmen in drei einfache Stufen zerlegt, wie eine Fabrik-Montageleitung:

Stufe 1: Initialisierung (Das Setup): Bevor man etwas packen kann, muss man die Maschine einrichten. Man steckt den Schlüssel und die „Nonce“ (eine eindeutige Zahl für die Sitzung) ein. Dies nimmt eine feste Zeit in Anspruch, unabhängig davon, wie groß die Nachricht ist. Es ist wie das Warmlaufen eines Automotors; es dauert die gleiche Zeit, egal ob man 1 Meile oder 100 Meilen fährt.
Stufe 2: Datenverarbeitung (Das Packen): Hier findet die eigentliche Verschlüsselung der Nachricht und der Zusatzdaten statt. Das ist die schwere Arbeit. Die Zeit, die hier benötigt wird, hängt vollständig davon ab, wie viele Daten man hat. Die Autoren haben Formeln erstellt, um genau zu berechnen, wie viele „Schritte“ (mathematische Operationen) pro Datenblock erforderlich sind.
Stufe 3: Finalisierung (Das Versiegeln): Sobald alles verpackt ist, muss man die Box versiegeln und ein Sicherheitsetikett anbringen, um zu beweisen, dass sie nicht manipuliert wurde. Dies ist eine weitere feste Arbeit, wie das Aufkleben eines finalen Aufklebers auf ein Paket.

3. Die Ergebnisse: Wer ist am leichtesten?

Durch die Anwendung dieses Drei-Stufen-Modells auf alle 10 Finalisten haben die Autoren ein „Menü“ von Formeln (gezeigt in ihrer Tabelle I) erstellt, das das „Gewicht“ jedes Algorithmus beschreibt.

Hier sind einige der interessanten Erkenntnisse, die sie mit ihren neuen Formeln gewonnen haben:

Die „Einfachen Linearen“ Läufer: Algorithmen wie GIFT-COFB, Grain-128AEAD und ISAP sind wie eine gerade Autobahn. Ihre Zeit wächst perfekt im Schritt mit der Nachrichtengröße. Wenn man die Nachricht verdoppelt, verdoppelt man auch die Zeit. Sie haben keine zusätzlichen „Steuern“ oder komplexen Multiplikatoren. GIFT-COFB ist besonders einfach, was es sehr effizient für große Nachrichten macht.
Die „Block“-Läufer: Algorithmen wie TinyJambu und Romulus arbeiten wie ein Förderband, das nur Artikel in bestimmten Größen der Boxen akzeptiert. Wenn eine Nachricht nicht perfekt in eine Box passt, müssen sie „Padding“ (Leerraum) hinzufügen, um sie aufzufüllen. Dies verursacht einen kleinen zusätzlichen Overhead, besonders bei kleinen Nachrichten, aber sie sind sehr strukturiert.
Die „Permutations“-Läufer: Algorithmen wie ASCON (den das NIST schließlich als Gewinner auswählte) und Xoodyak verwenden eine „Mischmethode“. Sie nehmen die Daten und mischen sie in einem bestimmten Muster um. Ihre Formeln zeigen, dass sie sehr effizient sind; die Zeitkosten entstehen hauptsächlich dadurch, wie oft sie die Daten mischen müssen.
Der „Hybride“ Läufer: ISAP ist eine Mischung aus verschiedenen Techniken. Es erstellt für jede Sitzung einen temporären Schlüssel, was eine winzige Menge an Setup-Zeit hinzufügt, aber es macht es sehr sicher gegen bestimmte Arten von Hacking.

4. Warum das wichtig ist

Das Paper sagt nicht nur „Algorithmus A ist schneller“. Es erklärt, warum, indem es sich die Mathematik hinter dem Design ansieht.

Design-Entscheidungen: Die Autoren zeigen, dass die „Form“ des Algorithmus dessen Geschwindigkeit bestimmt. Einige sind wie eine einspurige Straße gebaut (Stream Ciphers), andere wie eine Autobahn mit mehreren Spuren und Mautstellen (Block Ciphers).
Vorhersehbarkeit: Jetzt können Ingenieure, die diese winzigen Geräte entwerfen, diese Formeln nutzen, um exakt vorherzusagen, wie viel Batterieleistung ein Algorithmus verbrauchen wird, noch bevor sie das Gerät bauen.

Das Fazit

Dieses Paper liefert einen universellen Übersetzer für die kryptografische Leistung. Anstatt zu raten oder endlose Tests durchzuführen, können Ingenieure nun diese symbolischen Formeln verwenden, um den perfekten „Schlüssel“ für ihr spezifisches Robotermodell auszuwählen.

Wenn Sie den absolut einfachsten, leichtesten Pfad für riesige Nachrichten benötigen, deutet die Mathematik auf GIFT-COFB hin.
Wenn Sie ein Gleichgewicht zwischen Sicherheit und Geschwindigkeit für den allgemeinen Gebrauch benötigen, hebt die Mathematik ASCON hervor.
Wenn Sie Daten Bit für Bit verarbeiten müssen, ohne auf volle Blöcke zu warten, ist Grain-128AEAD die klare Wahl.

Die Autoren kommen zu dem Schluss, dass wir durch das Verständnis dieser theoretischen „Gewichte“ das Internet der Dinge besser absichern können, um sicherzustellen, dass unsere winzigen Geräte sicher bleiben, ohne dass ihnen der Strom ausgeht. Sie planen, diese Formeln in realen Szenarien wie digitalen Ausweisen zu testen, um zu sehen, ob die Mathematik auch in der realen Welt standhält.

Technische Zusammenfassung: Zeitkomplexitätscharakterisierung der NIST-Finalisten für leichte Kryptographie

Problemstellung
Da aufstrebende Technologien in digitalen Identitätssystemen und dem Internet der Dinge (IoT) zunehmend auf Geräte mit begrenzter Rechenleistung, Speicher und Energie angewiesen sind, ist der Bedarf an leichter Kryptographie (Lightweight Cryptography, LWC) kritisch geworden. Während das National Institute of Standards and Technology (NIST) einen Standardisierungsprozess zur Bewertung von zehn Finalisten-Algorithmen abgeschlossen hat, stützt sich die bestehende Literatur stark auf empirische Benchmarks (Ausführungszeit und Durchsatz) anstatt auf ein einheitliches theoretisches Verständnis. Die aktuelle Dokumentation für Finalisten wie Ascon, ISAP und TinyJAMBU konzentriert sich primend auf Implementierungsoptimierungen, lässt jedoch formale Zeitkomplexitätsausdrücke vermissen. Das Fehlen eines solchen theoretischen Rahmens erschwert die systematische Unterscheidung der algorithmischen Effizienz und die Vorhersage der Leistungssteigerung in verschiedenen eingeschränkten Umgebungen.

Methodik
Die Autoren schlagen ein symbolisches Modell vor, das die Zeitkomplexität kryptographischer Schemata in drei distinkte Phasen zerlegt: Initialisierung, Datenverarbeitung und Finalisierung. Dieser Rahmen ermöglicht die Ableitung formaler Zeitkomplexitätsausdrücke, die unabhängig von spezifischen Hardwareplattformen sind.

Die Gesamttzeitkomplexität ( $T_{total}$ ) wird als Summe modelliert aus:

Initialisierung ( $T_{init}$ ): Fixkosten für die Schlüssel- und Nonce-Konfiguration ($ck + cn$), unabhängig von der Eingabegröße.
Datenverarbeitung ( $T_{process}$ ): Kosten im Zusammenhang mit der Verarbeitung assoziierter Daten ( $A$ ) und Nachrichtenblöcke ( $M$ ). Dies wird in $T_A$ und $T_M$ unterteilt, berechnet basierend auf Blockanzahlen, Permutationszeiten ( $T_p$ ) und Prozess-Overheads.
Finalisierung ( $T_{finalize}$ ): Konstante Zeitkosten ( $c_f$ ) für die Generierung oder Validierung des Authentifizierungs-Tags.

Unter Verwendung dieser Drei-Phasen-Zerlegung leiten die Autoren symbolische Komplexitätsausdrücke für alle zehn NIST-Finalisten (Ascon, Elephant, GIFT-COFB, Grain-128AEAD, ISAP, PHOTON-Beetle, Romulus, SPARKLE, TinyJAMBU und Xoodyak) basierend auf deren algorithmischen Spezifikationen ab, einschließlich Zustandsgrößen, Permutationsdesigns und Betriebsmodi.

Wesentliche Beiträge und Ergebnisse
Die Arbeit liefert eine vergleichende Analyse der rechnerischen Skalierung der zehn Finalisten, wobei diese nach ihren zugrunde liegenden architektonischen Strategien kategorisiert werden:

Permutationsbasierte Algorithmen: Fünf Finalisten (Ascon, Elephant, PHOTON-Beetle, SPARKLE, Xoodyak) nutzen Schwamm-basierte oder permutationszentrierte Konstruktionen. Ihre Komplexität wird im Allgemeinen durch die Permutationskosten ( $b$ ) und die Anzahl der verarbeiteten Blöcke dominiert. Beispielsweise erreicht Ascon eine effiziente Skalierung ( $O(l_A \cdot b + l_P \cdot b)$ ) durch eine gestraffte 12-Runden-Initialisierung, während SPARKLE zusätzliche Konstanten enthält, um sowohl Verschlüsselungs- als auch Hashing-Funktionalitäten zu unterstützen.
Blockchiffren-basierte Algorithmen: Drei Finalisten (GIFT-COFB, Romulus-N, TinyJAMBU) verwenden Blockchiffren- oder registerbasierte Konstruktionen. GIFT-COFB wird für seine bemerkenswert einfache lineare Skalierung ( $O(\ell_A + \ell_M)$ ) ohne multiplikative Faktoren hervorgehoben, was es für große Nachrichten hocheffizient macht. TinyJAMBU nutzt duale Permutationen ( $P_{6440}$ und $P_{1024}$ ) für unterschiedliche Phasen, was spezifische Fixkosten für die Initialisierung und separate Prozesskosten für assoziierte Daten und Nachrichten einführt.
Stromchiffren- und Hybrid-Algorithmen: Grain-128AEAD ist der einzige Stromchiffren-Finalist, der eine Komplexität ($O(|M| + |AD|)$) bietet, die direkt mit der Bitanzahl skaliert, wodurch Padding-Overhead eliminiert wird. ISAP kombiniert Schwamm-basierte Verschlüsselung mit Sitzungsschlüsselableitung und erreicht eine lineare Skalierung ( $O(|A| + |M|)$ ), während es gleichzeitig durch Schlüsseltrennung Resistenz gegen Seitenkanalangriffe bietet.

Die Analyse zeigt, dass zwar alle Algorithmen eine lineare Skalierung mit der Eingabelänge aufweisen, die Koeffizienten jedoch je nach Designparametern wie Blockgröße, Rate und Permutationskomplexität signifikant variieren. Kein einzelner Algorithmus dominiert über alle Metriken hinweg; vielmehr bestehen Trade-offs zwischen Einfachheit, Funktionalität und Sicherheitsmargen.

Bedeutung
Die Arbeit behauptet, dass dieser einheitliche symbolische Rahmen eine notwendige theoretische Grundlage für die Evaluierung leichter kryptographischer Primitive bietet. Durch die Klärung, wie Designparameter die rechnerische Skalierung formen, ermöglicht das Modell Forschern und Praktikern, die algorithmische Effizienz rigoroser zu unterscheiden, als dies durch empirische Benchmarks allein möglich wäre. Die Autoren führen aus, dass diese Arbeit bei der Auswahl von Primitiven hilft, die in der Lage sind, Sicherheitssysteme in eingeschränkten Umgebungen, wie etwa mobilen und eingebetteten Geräten, zu unterstützen. Die Arbeit schließt mit dem Hinweis, dass diese theoretischen Ergebnisse als Basis für eine zukünftige Validierung in spezifischen realen Kontexten dienen, wie etwa bei mobilen Führerschein-Umgebungen, wenngleich die vorliegende Arbeit auf der Ableitung der symbolischen Modelle selbst fokussiert bleibt.

1. Das Problem: Das „Gewicht“ eines Schlosses messen

2. Die Lösung: Das Drei-Stufen-Fließband

3. Die Ergebnisse: Wer ist am leichtesten?

4. Warum das wichtig ist

Das Fazit

Mehr davon