Post-Quanten-Kryptographie – Wikipedia

Post-Quanten-Kryptographie (englisch post-quantum cryptography, PQC) bezeichnet ein Teilgebiet der Kryptographie, das sich mit kryptographischen Primitiven befasst, die im Gegensatz zu den meisten aktuell verwendeten asymmetrischen Kryptosystemen selbst unter Verwendung von Quantencomputern praktisch nicht zu entziffern sind. Der Begriff post-quantum cryptography wurde von Daniel J. Bernstein eingeführt,^[1] der auch 2006 an der Organisation der ersten Fachkonferenz PQCrypto zu diesem Thema beteiligt war.^[2]

Der Begriff wurde geprägt, da die ersten asymmetrischen Kryptosysteme auf der Schwierigkeit der Primfaktorzerlegung und der Berechnung diskreter Logarithmen beruhten, zwei Probleme, die theoretisch – bei ausreichend leistungsstarken Quantencomputern – durch den Shor-Algorithmus zu lösen sind.^[3]

Die Leistungsfähigkeit bisheriger Quantencomputer ist für derartige Berechnungen bei weitem nicht ausreichend und ein wissenschaftlicher Durchbruch oder Meilenstein kaum vorhersagbar; 2001 war IBM lediglich in der Lage, die Zahl 15 zu faktorisieren,^[4] 2012 gelang die Faktorisierung der Zahl 21.^[5]

Für symmetrische Verschlüsselungsverfahren wie beispielsweise AES sind Quantencomputer eine relativ kleine Bedrohung, da hier mittels des Grover-Algorithmus die in Bit gemessene Sicherheit eines Schlüssels um die Hälfte reduziert würde. Der gestiegenen Rechenleistung ließe sich mit entsprechend längeren Schlüsseln entgegenwirken.^[4]

Aussichtsreich scheint die Entwicklung von PQ-sicheren Verschlüsselungsalgorithmen auf Basis mathematischer Gitter, die beispielsweise bei Ring-LWE oder beim bis 2021 patentierten NTRUEncrypt als Grundlage verwendet werden.^[4] Darüber hinaus gibt es Forschung^[6] auf Basis von

• multivariaten Polynomen, beispielsweise das Unbalanced-Oil-and-Vinegar-Verfahren
• kryptologischen Hashfunktionen, beispielsweise das Merkle-Signaturverfahren oder das Lamport-Einmal-Signaturverfahren
• fehlerkorrigierenden Codes, beispielsweise das McEliece-Kryptosystem
• supersingulären elliptischen Kurven, beispielsweise SIKE
• gitterbasierter Kryptografie, beispielsweise CRYSTALS DILITHIUM

Ein weiteres Forschungsgebiet ist die Anpassung kryptographischer Beweistechniken an Quantenangreifer. Beispielsweise benutzt der Sicherheitsbeweis eines klassischen Zero-Knowledge-Beweisverfahrens eine Technik namens Rewinding, bei der der interne Zustand des Angreifers kopiert wird. Der Zustand eines Quantenangreifers kann nach dem No-Cloning-Theorem aber nicht immer kopiert werden, die Beweistechnik muss entsprechend angepasst werden.^[7]

Seit 2016 läuft beim US National Institute of Standards and Technology (NIST) ein Standardisierungsprozess, um jeweils einen Algorithmus für Schlüsselaustausch/Verschlüsselung und Digitale Signaturen zu testen und zu standardisieren. Im Juli 2022 entschied das NIST, dass für allgemeine Verschlüsselungen die gitterbasierte CRYSTALS-Kyber Technologie verwendet werden wird und für digitale Signaturen die Algorithmen CRYSTALS-Dilithium^[8], FALCON^[9] und SPHINCS+^[10][11][12]

• PQCrypto – Post-Quantum-Kryptographie Konferenz

1. ↑ Johannes Buchmann, Carlos Coronado, Martin Döring, Daniela Engelbert, Christoph Ludwig, Raphael Overbeck, Arthur Schmidt, Ulrich Vollmer, Ralf-Philipp Weinmann: Post-Quantum Signatures. 2004, Abschnitt 1 Introduction, S. 1 (iacr.org [PDF]). 
2. ↑ Homepage der PQCrypto 2006
3. ↑ Daniel J. Bernstein: Introduction to post-quantum cryptography. 2009 (englisch, springer.com/cda [PDF] Einführungskapitel des Buchs Post-quantum cryptography). 
4. ↑ ^{a b c} Kryptographie nach dem Quantencomputer. In: Telepolis. Abgerufen am 18. September 2013.
5. ↑ Enrique Martín-López, Anthony Laing, Thomas Lawson, Roberto Alvarez, Xiao-Qi Zhou, Jeremy L. O’Brien: Experimental realization of Shor’s quantum factoring algorithm using qubit recycling (= Nature Photonics. Band 6). 2012, S. 773–776 (nature.com). 
6. ↑ Q&A With Post-Quantum Computing Cryptography Researcher Jintai Ding, IEEE Spectrum, 1. November 2008 (englisch). 
7. ↑ John Watrous: Zero-Knowledge against Quantum Attacks. In: SIAM J. Comput. 39. Jahrgang, Nr. 1, 2009, S. 25–58, doi:10.1137/060670997. 
8. ↑ CRYSTALS-Dilithium
9. ↑ FALCON
10. ↑ SPHINCS+.
11. ↑ NIST Announces First Four Quantum-Resistant Cryptographic Algorithms. In: NIST. 5. Juli 2022 (nist.gov [abgerufen am 25. Juli 2022]). 
12. ↑ Zukunftssichere Datenverschlüsselung, Horst Görtz Institut, Ruhr-Universität Bochum, 5. Juli 2022