Wikipedia · einfach zusammengefasst · Stand
Post-Quanten-Kryptographie
Post-Quanten-Kryptographie (englisch post-quantum cryptography, PQC) bezeichnet ein Teilgebiet der Kryptographie, das sich mit kryptographischen Primitiven …
Inhalt4 Abschnitte
Grundidee der Post-Quanten-Kryptographie
Post-Quanten-Kryptographie (englisch post-quantum cryptography, PQC) ist ein Teilgebiet der Kryptographie. Sie untersucht kryptographische Primitive, also grundlegende Bausteine kryptographischer Verfahren, die auch mit Quantencomputern praktisch nicht zu entziffern sein sollen. Sie ist wichtig, weil viele heute verwendete asymmetrische Kryptosysteme auf mathematischen Problemen beruhen, die leistungsfähige Quantencomputer theoretisch lösen könnten.
Der Begriff „post-quantum cryptography“ wurde von Daniel J. Bernstein eingeführt. Er war 2006 auch an der Organisation der ersten Fachkonferenz PQCrypto zu diesem Thema beteiligt.
Gefährdung asymmetrischer Kryptosysteme
Die ersten asymmetrischen Kryptosysteme beruhen auf der Schwierigkeit der Primfaktorzerlegung und der Berechnung diskreter Logarithmen. Bei der Primfaktorzerlegung wird eine Zahl in ihre Primfaktoren zerlegt; diskrete Logarithmen sind ein weiteres schwieriges mathematisches Problem.
Mit ausreichend leistungsstarken Quantencomputern wären beide Probleme theoretisch durch den Shor-Algorithmus lösbar. Deshalb werden Verfahren gesucht, deren Sicherheit nicht von diesen Problemen abhängt.
Bisherige Quantencomputer reichen für solche Berechnungen bei weitem nicht aus. Wann ein wissenschaftlicher Durchbruch oder Meilenstein erreicht wird, ist kaum vorhersagbar. 2001 konnte IBM lediglich die Zahl 15 faktorisieren; 2012 gelang die Faktorisierung der Zahl 21.
Symmetrische Verschlüsselung und Quantencomputer
Für symmetrische Verschlüsselungsverfahren wie AES sind Quantencomputer eine vergleichsweise kleine Bedrohung. Bei diesen Verfahren würde der Grover-Algorithmus die in Bit gemessene Sicherheit eines Schlüssels um die Hälfte reduzieren.
Der erhöhten Rechenleistung kann man mit entsprechend längeren Schlüsseln begegnen. Anders als bei den genannten asymmetrischen Verfahren geht es daher nicht darum, dasselbe zugrunde liegende mathematische Problem vollständig lösbar wird, sondern um eine Verringerung der Schlüsselsicherheit.
Ansätze und Standardisierung
Als aussichtsreich gelten PQ-sichere Verschlüsselungsalgorithmen auf Basis mathematischer Gitter. Beispiele dafür sind Ring-LWE und NTRUEncrypt, das bis 2021 patentiert war. Weitere Forschungsansätze beruhen auf multivariaten Polynomen, etwa dem Unbalanced-Oil-and-Vinegar-Verfahren, auf kryptologischen Hashfunktionen wie dem Merkle-Signaturverfahren oder dem Lamport-Einmal-Signaturverfahren sowie auf fehlerkorrigierenden Codes wie dem McEliece-Kryptosystem. Außerdem werden supersinguläre elliptische Kurven, beispielsweise SIKE, und gitterbasierte Kryptografie, beispielsweise CRYSTALS DILITHIUM, erforscht.
Ein weiteres Forschungsgebiet betrifft Sicherheitsbeweise gegen Quantenangreifer. Ein klassisches Zero-Knowledge-Beweisverfahren kann die Technik Rewinding verwenden: Dabei wird der interne Zustand des Angreifers kopiert. Nach dem No-Cloning-Theorem kann der Zustand eines Quantenangreifers jedoch nicht immer kopiert werden. Deshalb müssen solche Beweistechniken angepasst werden.
Seit 2016 führt das US National Institute of Standards and Technology (NIST) einen Standardisierungsprozess durch. Getestet und standardisiert werden soll jeweils ein Algorithmus für Schlüsselaustausch/Verschlüsselung und für digitale Signaturen. Im Juli 2022 entschied das NIST, für allgemeine Verschlüsselungen die gitterbasierte CRYSTALS-Kyber-Technologie zu verwenden. Für digitale Signaturen wurden CRYSTALS-Dilithium, FALCON und SPHINCS+ ausgewählt.
