Von 2016 bis FIPS 203: Wie das NIST die Postquanten-Kryptographie auswählte

Das National Institute of Standards and Technology (NIST) führt seit 2017 einen Auswahl- und Standardisierungsprozess für Postquanten-Kryptographie durch. Der Grund ist konkret: Schätzungen zufolge könnte ein Quantencomputer den weit verbreiteten RSA-Algorithmus bereits um 2030 brechen. Das NIST-Verfahren gilt als das wichtigste gemeinsame Vorhaben zur Entwicklung und Bewertung von Algorithmen, die gegen Quantenangriffe resistent sind. Es läuft in mehreren Runden ab, die jeweils von einer Konferenz begleitet werden. In jeder Runde fallen einige Algorithmen heraus, andere werden genauer untersucht.

Da sich die meisten symmetrischen kryptographischen Primitive relativ leicht auf Quantensicherheit umstellen lassen, etwa durch Verdopplung der Schlüssellänge, konzentrieren sich die Anstrengungen auf die asymmetrische Kryptographie. Die Verdopplung neutralisiert die Beschleunigung durch den Grover-Algorithmus. Im Fokus stehen digitale Signaturen und Mechanismen der Schlüsselkapselung. Die künftigen Standards erscheinen als Federal Information Processing Standard, darunter FIPS 203, FIPS 204 und FIPS 205.

Das Vorbild AES

Das bewährte, offene und transparente Format des Vorhabens orientierte sich am Standardisierungsprozess für AES aus den Jahren 1997 bis 2000, der in der kryptologischen Gemeinschaft gut ankam. Akademische Untersuchungen zu möglichen Auswirkungen der Quanteninformatik reichen mindestens bis 2001 zurück. 2015 kündigten die US-Bundesbehörden an, alle staatlichen Informationssysteme mit Vertraulichkeitsanforderungen auf Kryptographie umzustellen, die gegen Quantencomputer resistent ist. Deshalb kündigte das NIST auf der Konferenz PQCrypto 2016 die Standardisierung quantensicherer kryptographischer Primitive an. Im Dezember 2016 startete der Prozess mit einem Aufruf zur Einreichung von Vorschlägen.

Bis zum Ende der Einreichungsfrist Ende 2017 gingen 23 Systeme für digitale Signaturen sowie 59 Verfahren zur Verschlüsselung und Schlüsselkapselung ein. 69 dieser Einreichungen galten als vollständig und für die erste Runde geeignet. 23 Kandidaturen schafften es in die weitere Arbeit. In die zweite Runde kamen sieben Algorithmen sowie acht alternative Kandidaturen. Am 22. Juli 2020 gab das NIST sieben Finalisten bekannt, darunter drei Signatursysteme, sowie acht alternative Lösungen.

Wer gewann, wer fiel

In der dritten Runde siegten CRYSTALS-Kyber als Mechanismus der Schlüsselkapselung sowie CRYSTALS-Dilithium, FALCON und SPHINCS+ als Systeme für digitale Signaturen. Diese werden derzeit vom NIST standardisiert. Die im Juli 2022 angekündigte vierte Runde, in der vier weitere Algorithmen geprüft werden, lief im März 2024 noch. 2024 veröffentlichte das NIST die endgültigen Fassungen seiner ersten drei Standards für Postquanten-Kryptographie. Zwei gitterbasierte Algorithmen, ML-KEM (allgemein bekannt als Kyber) und ML-DSA (bekannt als Dilithium), gehörten zu den ersten standardisierten Postquanten-Lösungen. Nicht alle Konstruktionen überstanden das Verfahren: Die viel diskutierte Konstruktion SIDH/SIKE wurde 2022 spektakulär gebrochen. Der Angriff betraf ausschließlich diese Familie von Schemata und lässt sich nicht auf andere isogeniebasierte Konstruktionen verallgemeinern.