Post-Quanten-Kryptographie
# Post-Quanten-Kryptographie

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 entschlüsseln sind. Der Begriff post-quantum cryptography wurde von Daniel J. Bernstein eingeführt, der auch 2006 an der Organisation der ersten Fachkonferenz PQCrypto zu diesem Thema beteiligt war.

## Asymmetrische Verfahren

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.

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, 2012 gelang die Faktorisierung der Zahl 21.

## Symmetrische Verfahren

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.

## Zukunft

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. Darüber hinaus gibt es Forschung 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.

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, FALCON und SPHINCS+

