Könnte Quantencomputer irgendwann dazu verwendet werden, das moderne Hashing trivial zu machen?

Einfach ausgedrückt, wenn man ein Quantencomputergerät mit einer Leistung von beispielsweise 20 Qubits bauen würde, könnte ein solcher Computer verwendet werden, um irgendeine Art von modernem Hashing-Algorithmus unbrauchbar zu machen?

Wäre es überhaupt möglich, die Leistungsfähigkeit des Quantencomputers in einer herkömmlichen Computeranwendung zu nutzen?

Quantencomputer haben in einigen Fällen möglicherweise einen gewissen Vorteil gegenüber klassischen Computern. Das bemerkenswerteste Beispiel ist Shors Algorithmus, der eine große Anzahl an Polynomen berücksichtigt (während der bekannteste Algorithmus klassisch exponentielle Zeit benötigt). Dadurch werden Schemata wie RSA, die auf der Faktorisierungshärte basieren, vollständig durchbrochen.

Dies ist bei Hash-Funktionen nicht unbedingt der Fall. Zunächst müssen wir definieren, was es bedeutet, eine Hash-Funktion zu unterbrechen. Eine Möglichkeit, dies zu unterbrechen, wird als Pre-Image-Angriff bezeichnet : Sie geben mir den Hash-Wert und ich muss eine Nachricht , die lautet . Ein weiterer Angriff ist der Kollisionsangriff , bei dem Sie mir nichts geben und ich zwei verschiedene Nachrichten mit demselben Hash . Dies ist einfacher als ein Vorbild zu finden, da ich nicht an ein bestimmtes gebunden bin .m Hash ( m ) = $v$$m$$\operatorname{hash}(m)=v$$m_1, m_2$$\operatorname{hash}(m_1)=\operatorname{hash}(m_2)$$v$

Was können Quantencomputer? Das Hauptergebnis ist der Suchalgorithmus von Grover : eine Methode, mit der ein Quantencomputer in einer unsortierten Datenbank der Größe mit der Zeit sucht (während es klassisch eine erwartete Zeit von ).$N$$O(\sqrt{N})$$N/2$

Mit dem Algorithmus von Grover dauert das Finden eines Vorabbilds einer Hash-Funktion, deren Ausgabe Bit ist, und nicht .$k$$O(2^{k/2})$$O(2^k)$

Ist das ein Problem ? Nicht unbedingt. Hash-Funktionen sind so konzipiert , dass die Zeit als "sicher" gilt (mit anderen Worten, die Hash-Designer verdoppeln immer ). Dies ist auf das Geburtstagsparadox zurückzuführen, mit dem das Auffinden einer Kollision mit der Zeit durch einen klassischen Computer möglich ist.$2^{k/2}$$k$$O(2^{k/2})$

Das Schöne an Grovers Algorithmus ist, dass er optimal ist - jeder andere Quantenalgorithmus, der ein Element in einer unsortierten Datenbank findet, wird in der Zeit .$\Omega(\sqrt{N})$

Können Quantencomputer bessere Kollisionsangriffe ausführen ? Eigentlich bin ich mir nicht sicher. Der Algorithmus von Grover kann so erweitert werden, dass bei Elementen (dh Vorabbildungen) die Zeit zum Auffinden eines Elements auf reduziert wird . Dies führt jedoch zu keiner Kollision. Wenn Sie den Algorithmus erneut ausführen, wird möglicherweise dasselbe Vorbild zurückgegeben. Wenn wir andererseits zufällig auswählen und dann den Algorithmus von Grover verwenden, ist es wahrscheinlich, dass er eine andere Nachricht zurückgibt. Ich bin nicht sicher, ob dies bessere Angriffe gibt.$t$m$O(\sqrt{N/t})$$m_1$

_{(Dies beantwortet die allgemeinere Frage, ohne den Computer auf 20 Qubits zu beschränken, was nicht ausreicht, um die aktuellen 1024-Bit-Hashes zu knacken.)}

Soweit ich weiß, kann Quantencomputing die heutigen Hashing-Algorithmen auf einfache Weise durchbrechen. Langfristig werden wir jedoch auch komplexere Hashing-Algorithmen verwenden können, und im Allgemeinen ist es einfacher, etwas zu verschlüsseln als zu entschlüsseln. Ich denke, die größten Probleme, die zu berücksichtigen sind, sind, wenn Quantencomputer nur wenigen zur Verfügung stehen und ihnen einen einfachen Zugang zu Dingen ermöglichen, die durch die heutigen Algorithmen geschützt sind, lange bevor fortgeschrittenere Algorithmen oder sogar das Bewusstsein für die Bedrohung weit verbreitet sind.

Sehen Sie hier für eine tatsächlich technische Antwort auf die Frage auf Stack - Überlauf.