Das Ziel dieser Studie ist eine Beurteilung des Entwicklungsstands aktueller Technologien zur Realisierung eines kryptographisch relevanten Quantencomputers sowie von kryptografisch relevanten Quantenalgorithmen.

Die Sicherheit digitaler Infrastrukturen beruht heute zu einem großen Teil auf Public-Key-Kryptografie (auch „asymmetrische Kryptografie“). Diese wiederum beruht wesentlich auf der angenommenen Schwierigkeit bestimmter mathematischer Probleme, beispielsweise auf dem Faktorisierungsproblem oder dem Diskreter-Logarithmus-Problem (auf elliptischen Kurven). Mit klassischer Hardware sind die gängigen Public-Key-Verfahren nach heutigem Kenntnisstand nicht zu brechen. Die Situation ändert sich allerdings grundlegend, wenn universelle Quantencomputer ausreichender Leistungsfähigkeit verfügbar sind. Denn bereits 1994 wurden von Peter Shor Quantenalgorithmen vorgestellt, die die oben genannten mathematischen Probleme effizient lösen können. 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.

Die zentrale Herausforderung bei der Realisierung von Quantencomputern ist die Fehleranfälligkeit. Quantensysteme sind sehr empfindlich gegenüber Störungen und bedürfen daher einer aufwendigen Fehlerkorrektur, die als Quantenfehlerkorrektur bezeichnet wird. Als Zwischenstation auf dem Weg zu fehlerkorrigierenden Quantencomputern steht die Ära der Noisy Intermediate-Scale Quantum (NISQ)-Technologien, in der Fehler nicht korrigiert (und 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 in den letzten Jahren vorgestellten Algorithmen in diesem Kontext sind im Allgemeinen von heuristischer Natur und haben keinen mathematischen Konvergenzbeweis oder eine daraus abgeleitete Ressourcenanalyse. Dies gilt insbesondere für die Algorithmen zur Kryptoanalyse von (asymmetrischen) Verfahren.

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, wurde für die Version 2.0 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 (Version 2.1)

Die in der Studie identifizierten gegenwärtigen Technologien werden gemäß des Bewertungsmodells (Abbildung 1) wie folgt eingeordnet:

Mit Blick auf die Zukunft lautet die Schlussfolgerung der Studie, dass die Quanteninformatik stetige Fortschritte in Richtung kryptoanalytische Relevanz macht. Es gibt einen etablierten Mainstream: fehlertoleranter (verbesserter) Shor-Algorithmus, der entweder auf einem supraleitenden System mit dem Surface-Code oder einem ionenbasierten System mit dem Color-Code ausgeführt wird. Die Grundannahmen der Quantenfehlerkorrektur wurden im Jahr 2024 endlich vollständig verifiziert. So wurden Verzögerungen der letzten Jahre überwunden. Damit ist es wahrscheinlich, dass selbst ohne Disruptionen ein krypotanalytisch relevanter Quantencomputer in höchstens 16 Jahren realisierbar ist.

Zudem gibt es inzwischen eine Fülle neuer Entwicklungen bei der Fehlerkorrektur und -mitigation sowie der Hardware, die dies deutlich auf knapp zehn Jahre beschleunigen könnten, aber noch nicht durchgängig verifiziert sind. 

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.