Neue Angriffsflächen für Post-Quantum-Kryptographie
Das Linear Equivalence Problem (LEP) und sein Spezialfall, das Permutation Equivalence Problem (PEP), spielen eine wichtige Rolle in modernen Post-Quantum-Kryptosystemen wie LESS. Sie beschäftigen sich mit der Frage, ob zwischen zwei linearen Codes eine lineare Isometrie existiert und wie diese gefunden werden kann.
Eine neue arXiv-Publikation zeigt nun, dass diese Probleme erhebliche algebraische Schwächen aufweisen können. Während bisherige Forschung das PEP über das Schur-Produkt angriff, erweitern die Autoren diesen Ansatz nun auf das allgemeinere LEP.
Power Codes als neuer Angriffspunkt
Der Schlüssel liegt in der Verwendung von Power Codes – einer verallgemeinerten Klasse von linearen Codes. Kombiniert mit Frobenius-Automorphismen und Hermitian Hulls können damit viele LEP-Instanzen signifikant schneller gelöst werden. Dies ist nach Aussage der Autoren die erste Arbeit, die systematisch algebraische Schwächen des LEP ausnutzt.
Die Implikationen sind erheblich: Wenn sich große Klassen von LEP-Instanzen effizient lösen lassen, sinkt der praktische Sicherheitslevel von kryptografischen Systemen, die darauf basieren.
Praktische Konsequenzen
Besonders interessant ist die verbesserte Reduktion zum PEP, wenn die Koeffizienten der Monomial-Matrix in einer Untergruppe der multiplikativen Gruppe des endlichen Feldes liegen. Das bedeutet, dass unter bestimmten algebraischen Bedingungen die Komplexität des LEP weiter sinkt.
Für Implementierer von LESS und ähnlichen Systemen ist dies ein Weckruf: Die bisherige Annahme, dass zufällig gewählte Parameter ausreichend Sicherheit bieten, muss überprüft werden. Es reicht nicht, beliebige Codes zu verwenden – man muss gezielt solche auswählen, die nicht zu den neu identifizierten easy instances gehören.
Relevanz für die Post-Quantum-Standardisierung
Diese Erkenntnis fällt in eine kritische Phase: Post-Quantum-Kryptografie wird gerade standardisiert und in Produktionsumgebungen eingeführt. Während LESS selbst noch nicht in den finalen NIST-Standards vertreten ist, zeigt diese Arbeit, dass algebraische Angriffswege auf lattice-freie PQC-Ansätze realistisch sind.
Die Arbeit unterstreicht, wie wichtig es ist, nicht nur asymptotische Komplexität zu betrachten, sondern auch die Struktur der verwendeten mathematischen Objekte zu verstehen. Power Codes und ihre algebraischen Eigenschaften waren bislang nicht als primärer Fokus kryptanalytischer Arbeiten im Blickfeld.
Für zukünftige Designs post-quantensicherer Systeme gilt: Eine theoretische Komplexitätsannahme schützt nicht vor strukturellen Schwächen, die durch vertiefte mathematische Analyse offengelegt werden können.
