Unter Post-Quanten-Kryptografie versteht man kryptografische Verfahren, von denen angenommen wird, dass sie auch mit Hilfe eines Quantencomputers nicht zu brechen sind. Im Gegensatz zur Quantenkryptografie können diese Verfahren auf klassischer Hardware implementiert werden.

Hintergrund

Die Sicherheit digitaler Infrastrukturen beruht heute zu einem großen Teil auf Public-Key-Kryptografie. Die aktuell eingesetzte Public-Key-Kryptografie basiert auf der angenommenen Schwierigkeit bestimmter mathematischer Probleme, beispielsweise auf dem Problem, eine natürliche Zahl in ihre Primfaktoren zu zerlegen. Aus diesen mathematischen Problemen lassen sich Einwegfunktionen ableiten. Dies sind Funktionen, die leicht zu berechnen, aber schwer umzukehren sind. Im genannten Beispiel ist die Einwegfunktion die Multiplikation von zwei sehr großen (ungefähr 2000 Bit) Primzahlen, die mit einem Computer schnell durchführbar ist. Bisher ist kein effizienter klassischer Algorithmus bekannt, der eine 4000 Bit große Zahl wieder in ihre beiden Primfaktoren zerlegen kann. Dies ist die Basis für das nach seinen Entwicklern (Rivest, Shamir, Adleman) benannte RSA-Verfahren zur Verschlüsselung und für digitale Signaturen. Ein weiteres mathematisches Problem, auf dem heutige kryptografische Verfahren beruhen, ist das Diskrete Logarithmus Problem (DLP). Auf Basis des DLP lassen sich beispielsweise Verfahren zum Schlüsselaustausch und für digitale Signaturen konstruieren.

Zur Verschlüsselung werden üblicherweise mit einem Public-Key-Verfahren kryptografische Schlüssel vereinbart, um anschließend Nachrichten mit einem symmetrischen Algorithmus (wie AES) zu verschlüsseln. Mit klassischen Computern sind die gängigen Public-Key-Verfahren nach heutigem Kenntnisstand nicht zu brechen. Die Situation ändert sich grundlegend, wenn universelle Quantencomputer mit ausreichender Leistungsfähigkeit verfügbar sind. Denn bereits 1994 wurden von Peter Shor Quantenalgorithmen veröffentlicht, die die oben genannten mathematischen Probleme effizient lösen können. Mit Entwicklung eines Quantencomputers, auf dem die Algorithmen von Shor für ausreichend große Eingabegrößen implementiert werden können, würde somit der heutigen Public-Key-Kryptografie die Grundlage entzogen werden.

Kandidaten für Post-Quanten-Kryptografie

Die Sicherheit von Verfahren der Post-Quanten-Kryptografie basiert auf Problemen, bei denen nach heutigem Kenntnisstand davon ausgegangen wird, dass sie auch von Quantencomputern schwer zu lösen sind. Kandidaten für solche Verfahren basieren beispielsweise

• auf der Schwierigkeit, allgemeine fehlerkorrigierende Codes effizient zu dekodieren ("Codebasierte Kryptografie") oder
• auf der Schwierigkeit von bestimmten Problemen in mathematischen Gittern ("Gitterbasierte Kryptografie")
• auf Sicherheitseigenschaften kryptografischer Hashfunktionen ("Hashbasierte Kryptografie").

Standardisierung

Zurzeit gibt es einige Standardisierungsaktivitäten im Bereich quantensicherer Kryptografie, insbesondere das 2016 initiierte "Post-Quantum Cryptography Project" des US-amerikanischen National Institute of Standards and Technology (NIST). Über drei Runden wurden zahlreiche eingereichte Verfahren eingehend untersucht. Im Juli 2022 gab NIST am Ende der dritten Runde bekannt, dass es das Schlüsseleinigungsverfahren CRYSTALS-Kyber sowie die Signaturverfahren CRYSTALS-Dilithium, Falcon und SPHINCS+ standardisieren wird. Zusätzlich werden in einer vierten Runde die drei codebasierten Schlüsseleinigungsverfahren Classic McEliece, BIKE und HQC geprüft. Außerdem hat NIST zur Einreichung weiterer Signaturverfahren bis Juni 2023 aufgerufen. Ziel ist es, dass eine gewisse Auswahl von Signaturverfahren standardisiert wird, deren Sicherheit auf möglichst verschiedenen mathematischen Problemen basiert.

Bei der Internet Research Task Force (IRTF) wurden bereits zustandsbehaftete hashbasierte Signaturen spezifiziert (LMS im RFC 8554 und XMSS im RFC 8391) und vom NIST für bestimmte Parameterwahlen in NIST SP 800-208 empfohlen. Diese sind allerdings nicht für alle Einsatzzwecke geeignet, da sichergestellt werden muss, dass der Zustand vom Nutzer der Signatur sicher verwaltet werden kann.

Im Rahmen eines BSI-Projektes werden in der Open Source Kryptobibliothek Botan Post-Quanten-Verfahren implementiert.

Implementierungssicherheit

Des Weiteren hat das Fraunhofer-Institut AISEC im Auftrag des BSI die Studie Laser Fault Injection Attack on the eXtended Merkle Signature Scheme (XMSS) erstellt. Diese Studie beschreibt einen neuartigen Laser-Fehlerangriff auf das Winternitz One-Time Signature (WOTS) Verfahren, welches unter anderem in XMSS verwendet wird.