Ein Forscherteam in China hat eine Technik vorgestellt, die – theoretisch – die gebräuchlichsten Methoden zur Gewährleistung der digitalen Privatsphäre knacken könnte, indem ein rudimentärer Quantencomputer verwendet wird.
Die Technik funktionierte in einer Demonstration im kleinen Maßstab, berichten die Forscher, aber andere Spezialisten sind skeptisch, dass das Verfahren skaliert werden könnte, um gewöhnliche Computer bei dieser Aufgabe zu schlagen. Dennoch warnen sie davor, dass das Papier, das Ende letzten Monats im arXiv-Repository veröffentlicht wurde, eine Erinnerung an die Verwundbarkeit des Online-Datenschutzes ist.
Quantencomputer sind bekanntermaßen eine potenzielle Bedrohung für aktuelle Verschlüsselungssysteme, aber die Technologie steckt noch in den Kinderschuhen. Forscher schätzen in der Regel, dass es viele Jahre dauern wird, bis Quantencomputer kryptografische Schlüssel – die Zeichenfolgen, die in einem Verschlüsselungsalgorithmus zum Schutz von Daten verwendet werden – schneller als gewöhnliche Computer knacken können.
Forscher erkannten in den 1990er Jahren, dass Quantencomputer Besonderheiten der Physik ausnutzen könnten, um Aufgaben auszuführen, die außerhalb der Reichweite „klassischer“ Computer zu liegen scheinen. Peter Schorein Mathematiker, der jetzt am Massachusetts Institute of Technology in Cambridge arbeitet, zeigte 1994, wie man das Phänomen der Quantenüberlagerung anwendet – das die Fähigkeit atomarer Objekte beschreibt, gleichzeitig in einer Kombination mehrerer Zustände zu existieren – und Quanteninterferenz, die analog dazu ist, wie sich Wellen auf einem Teich addieren oder aufheben können, bis hin zur Faktorisierung ganzer Zahlen in Primzahlen, die ganzen Zahlen, die nicht ohne Rest weiter geteilt werden können.
Shors Algorithmus würde einen Quantencomputer exponentiell schneller als einen klassischen machen, wenn es darum geht, ein Verschlüsselungssystem zu knacken, das auf großen Primzahlen basiert – Rivest-Shamir-Adleman oder RSA genannt, nach den Initialen seiner Erfinder – sowie einige andere beliebte Kryptografietechniken. die derzeit die Privatsphäre und Sicherheit im Internet schützen. Aber die Implementierung von Shors Technik würde einen Quantencomputer erfordern, der viel größer ist als die verfügbaren Prototypen. Die Größe eines Quantencomputers wird in Quantenbits oder Qubits gemessen. Forscher sagen, dass es eine Million oder mehr Qubits brauchen könnte, um RSA zu knacken. Die größte heute erhältliche Quantenmaschine – der Osprey-Chip, angekündigt im November von IBM– hat 433 Qubits.
Ein frischer Ansatz
Shijie Wei von der Pekinger Akademie für Quanteninformationswissenschaften und Mitarbeiter gingen einen anderen Weg, um RSA zu schlagen, und zwar nicht auf der Grundlage von Shors, sondern von Schnorrs Algorithmus – einem Prozess zur Faktorisierung ganzer Zahlen, der von dem Mathematiker Claus Schnorr an der Goethe-Universität in Frankfurt, Deutschland, ebenfalls entwickelt wurde die 1990er. Der Algorithmus von Schnorr wurde entwickelt, um auf einem klassischen Computer ausgeführt zu werden, aber das Team von Wei implementierte einen Teil des Prozesses auf einem Quantencomputer, wobei ein Verfahren verwendet wurde, das als quantennaher Optimierungsalgorithmus oder QAOA bezeichnet wird.
In dem noch nicht begutachteten Papier behaupten die Autoren, dass ihr Algorithmus starke RSA-Schlüssel – Zahlen mit mehr als 600 Dezimalstellen – mit nur 372 Qubits knacken könnte. In einer E-Mail an Natur Im Namen aller Autoren warnte Guilu Long, Physiker an der Tsinghua-Universität in China, davor, dass es nicht ausreicht, viele Qubits zu haben, und dass aktuelle Quantenmaschinen immer noch zu fehleranfällig sind, um eine so große Berechnung erfolgreich durchzuführen. „Einfach die Qubit-Zahl zu erhöhen, ohne die Fehlerrate zu senken, hilft nicht.“
Chao-Yang Lu, ein Physiker, der Quantencomputer an der University of Science and Technology of China in Hefei baut und nicht an dem Projekt beteiligt war, sagt, dass jeder der 372 Qubits erforderlich wäre, um den QAOA-Algorithmus auf einer so kleinen Maschine auszuführen arbeiten zu 99,9999 % fehlerfrei. Modernste Qubits haben kaum eine Genauigkeit von 99,9 % erreicht.
Das Team demonstrierte die Technik auf einem 10-Qubit-Quantencomputer, um die handlichere, 15-stellige Zahl 261.980.999.226.229 zu faktorisieren. (Es teilt sich in zwei Primzahlen auf, nämlich 15.538.213 × 16.860.433.) Die Forscher sagen, dass dies die größte Zahl ist, die bisher mit Hilfe eines Quantencomputers faktorisiert wurde – obwohl sie viel kleiner ist als die Verschlüsselungsschlüssel, die von modernen Webbrowsern verwendet werden.
Umstrittenes Papier
Das Problem ist, dass niemand weiß, ob die QAOA das Faktorisieren großer Zahlen schneller macht, als einfach den klassischen Algorithmus von Schnorr auf einem Laptop auszuführen. „Es sollte darauf hingewiesen werden, dass die Quantenbeschleunigung des Algorithmus unklar ist“, schreiben die Autoren. Mit anderen Worten, obwohl Shors Algorithmus die Verschlüsselung garantiert effizient bricht, wenn (und falls) ein ausreichend großer Quantencomputer verfügbar wird, könnte die optimierungsbasierte Technik auf einem viel kleineren Computer laufen, aber sie könnte die Aufgabe nie beenden.
Michele Mosca, Mathematiker an der University of Waterloo in Kanada, weist auch darauf hin, dass der QAOA nicht der erste bekannte Quantenalgorithmus ist, der ganze Zahlen mit einer kleinen Anzahl von Qubits faktorisieren kann. Er und seine Mitarbeiter haben 2017 einen beschrieben. Forscher wussten also bereits, dass es nichts Grundlegendes gibt, das Quantencomputer sehr groß machen muss, um Zahlen zu faktorisieren.
Andere Forscher haben sich darüber beschwert, dass, obwohl das neueste Papier richtig sein könnte, der Vorbehalt bezüglich der Geschwindigkeit erst ganz am Ende kommt. „Alles in allem ist dies eine der irreführendsten Veröffentlichungen zu Quantencomputern, die ich seit 25 Jahren gesehen habe.“ gebloggt Quantencomputing-Theoretiker Scott Aaronson von der University of Texas in Austin.
In seiner E-Mail sagt Long, dass er und seine Mitarbeiter planen, das Papier zu ändern und den Vorbehalt weiter nach oben zu verschieben. „Wir begrüßen die Peer-Review und die Kommunikation mit Wissenschaftlern auf der ganzen Welt“, fügte die Erklärung hinzu.
Selbst wenn die auf Schnorr basierende Technik das Internet nicht brechen wird, könnten Quantencomputer dies schließlich tun, indem sie Shors Algorithmus ausführen. Sicherheitsforscher waren damit beschäftigt, eine Reihe alternativer kryptografischer Systeme zu entwickeln, die als weniger wahrscheinlich einem Quantenangriff unterliegen, genannt Post-Quantum oder quantensicher. Aber Forscher könnten in Zukunft auch bessere Quantenalgorithmen entdecken, die diese Systeme schlagen können, mit katastrophalen Folgen.
„Das Vertrauen in digitale Infrastrukturen würde zusammenbrechen“, sagt Mosca. „Wir wechselten plötzlich von der Verwaltung der quantensicheren Migration über das Technologielebenszyklusmanagement zum Krisenmanagement“, fügt er hinzu. “Es wird nicht schön sein, egal wie du es schneidest.”
Dieser Artikel wird mit Genehmigung reproduziert und wurde erstmals veröffentlicht am 6. Januar 2023.