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

Das National Institute of Standards and Technology wählt seit 2017 Verfahren für Postquanten-Kryptographie aus und standardisiert sie. Der Grund ist konkret: Schätzungen zufolge könnte der verbreitete Algorithmus RSA schon etwa 2030 von einem Quantencomputer gebrochen werden. Das Verfahren des NIST gilt als das wichtigste gemeinsame Vorhaben zur Entwicklung und Bewertung von Algorithmen, die gegen Quantenangriffe widerstandsfähig sind. Es läuft in mehreren Runden ab, zu denen jeweils auch eine Konferenz gehört. In jeder Runde scheiden einige Algorithmen aus, andere werden genauer untersucht.

Die meisten symmetrischen kryptographischen Primitive lassen sich verhältnismäßig leicht auf Quantensicherheit umstellen, etwa durch Verdopplung der Schlüssellänge. Das neutralisiert die Beschleunigung durch den Grover-Algorithmus. Deshalb konzentrieren sich die Anstrengungen auf die asymmetrische Kryptographie, insbesondere auf 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 gelobt wurde. Akademische Untersuchungen zu möglichen Auswirkungen der Quanteninformatik reichen mindestens bis 2001 zurück. Im Jahr 2015 kündigten die amerikanischen Bundesbehörden Pläne an, alle staatlichen Systeme der Informationsverarbeitung, die Vertraulichkeitsanforderungen unterliegen, auf Kryptographie umzustellen, die gegen Quantencomputer resistent ist. Deshalb kündigte das NIST auf der Konferenz PQCrypto im Jahr 2016 die Standardisierung quantensicherer kryptographischer Primitive an. Im Dezember 2016 wurde das Standardisierungsverfahren mit einem Aufruf zur Einreichung von Vorschlägen eröffnet.

Bis zum Ende der Einreichungsfrist Ende 2017 gingen 23 Systeme für digitale Signaturen sowie 59 Verfahren zur Verschlüsselung und Schlüsselkapselung ein. Von dieser Zahl galten 69 als vollständig und für die Teilnahme an der ersten Runde geeignet. Aus dieser gingen 23 Kandidaturen in die weitere Arbeit über. 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 die Algorithmen 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. Im Jahr 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.