Entwicklungsstand Quantencomputer
Das Ziel dieser Studie ist eine Beurteilung des Entwicklungsstands aktueller Technologien zur Realisierung eines kryptographisch relevanten Quantencomputers sowie von kryptografisch relevanten Quantenalgorithmen.
Ein hinreichend leistungsfähiger und fehlerkorrigierender Quantencomputer würde die gegenwärtig verwendete Public-Key-Kryptografie brechen, die auf dem Faktorisierungsproblem oder dem Diskreter-Logarithmus-Problem (auf elliptischen Kurven) basieren. Seit der Publikation von Shor (1994) existieren Quantenalgorithmen mit polynomieller Laufzeit zur Berechnung dieser Probleme. Weitere Quantenalgorithmen wie der Suchalgorithmus von Grover und der Algorithmus von Simon haben zudem Implikationen für die symmetrische Kryptografie, insbesondere für Schlüssellängen und Betriebsarten. Darüber hinaus wurden in den letzten Jahren einige Algorithmen zur Kryptoanalyse von (asymmetrischen) Verfahren vorgestellt, die auch auf sogenannten NISQ-Rechnern implementiert werden können, wobei NISQ für “Noisy Intermediate-Scale Quantum" steht.
Vor der Etablierung fehlerkorrigierender Quantencomputer steht die Ära der NISQ-Technologien, in der Fehler nicht korrigiert (nur ggf. durch hardwarenahe Methoden mitigiert) werden, weshalb nur eine begrenzte algorithmische Tiefe zur Verfügung steht, die durch die Fehlerwahrscheinlichkeit limitiert wird. Bei der Entwicklung von Algorithmen für NISQ-Rechner werden native Freiheitsgrade der Hardware und alternative Programmierparadigmen kreativ genutzt. Die entstehenden Lösungen sind im Allgemeinen von heuristischer Natur und haben keinen mathematischen Konvergenzbeweis oder eine daraus abgeleitete Ressourcenanalyse.
Bewertungsmodelle der Studie
In der ersten Version der Studie wurde ein Bewertungsmodell zur Einordnung von Quantencomputer-Technologien entwickelt, welches in dem folgenden Bild dargestellt ist.
Um das Gebiet der NISQ-Algorithmen weiter beobachten zu können, wird in der aktuellen Version der Studie zudem ein separates Bewertungsschema vorgestellt. NISQ-Algorithmen sind in unserer Algorithmus-Bewertung häufig Kandidaten für den “linken Zweig” in Abbildung 2. Hingegen fügen sich die bereits erwähnten Algorithmen von Shor in den "rechten Zweig" ein.
Eine Analyse des Entwicklungsstandes von kryptografisch relevantem Quantencomputing erfordert eine gemeinsame Betrachtung von Hardware und Algorithmen. Dies ist in der folgenden Grafik verdeutlicht:
Aktueller Stand
Die in der Studie identifizierten gegenwärtigen Technologien werden gemäß des Bewertungsmodells (Abbildung 1) wie folgt eingeordnet:
Bezüglich der NISQ-Algorithmen kommt die Studie zurzeit zu dem Schluss, dass die geringe vorliegende Evidenz bisher keine abschließende Bewertung zulässt, aber die vorsichtige Vermutung geringer Relevanz für die Kryptoanalyse erlaubt.